IngentaConnect Developing exact and Tabu search algorithms for simultaneously de...

Authors: Z.-Farahani, R.¹; Pourakbar, M.²; Miandoabchi, E.¹

Source: International Journal of Production Research, Volume 45, Number 22, November 2007 , pp. 5199-5222(24)

Purchase options

The full text electronic article is available for purchase. You will be able to download the full text electronic article after payment.

$42.75 plus tax Refund Policy

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

Document Type: Research article

DOI: 10.1080/00207540600824912

Affiliations: 1: Department of Industrial Engineering, Amirkabir University of Technology, Tehran, Iran,Supply Chain Management Research Group, Tehran, Iran 2: Department of Industrial Engineering, Amirkabir University of Technology, Tehran, Iran

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