Developing exact and Tabu search algorithms for simultaneously determining AGV loop and P/D stations in single loop systems

Abstract

There are some issues which have to be addressed when designing an automated guided vehicles system (AGVS) such as flow-path layout, traffic management, the number and the location of pick up and delivery points, vehicle routing and so on. One of the AGVS guide path configurations discussed in the previous researches includes a single-loop which is the subject of this paper. In unidirectional single loop systems, determining the loop for the motion of an AGV, and the location of pick up and delivery (P/D) stations in the cells, are prominent points which, when considered simultaneously, lead to better results than determining each one independently. However, in the literature it is proved that the problem of separately determining the shortest feasible loop is a NP-complete problem. In this paper, by considering a from-to chart and a block layout as the input of problem, we try to determine: (1) a single loop, with at least one shared edge with each cell, (2) the direction of the flow and (3) the location of P/D stations on the loop, all at the same time, in a way that the total travel distance on the loop be minimised. In this regard, first a new exact algorithm is presented and then three heuristic algorithms are developed utilising a Tabu search (TS) method. Solving randomly generated test problems shows that our exact algorithm is capable of solving small size problems; also all three TS algorithms work efficiently in solving problems that could not be solved by exact algorithms.

Keywords:

• AGV routing
• P/D station
• Single loop
• Tabu search