Developing Conflict-Free Routes for Automated Guided Vehicles

TLDR

Automated guided vehicles are increasingly popular material handling devices in flexible manufacturing systems. The study aims to minimize makespan while routing AGVs conflict‑free on a bidirectional network, providing implementable solutions within reasonable computer time. The authors solve the problem using column generation, where a master problem with makespan and interference constraints iteratively generates AGV routes and a time‑dependent constrained shortest‑path subproblem, supplemented by an improvement procedure and various iteration strategies. Empirical results show the method produces solutions within a few percent of a proposed bound in reasonable computer time.

Abstract

Automated guided vehicles (AGVs) are a highly sophisticated and increasingly popular type of material handling device in flexible manufacturing systems. This paper details solution methodologies for the static routing problem in which demand assignment of the AGVs are known; the focus is to obtain an implementable solution within a reasonable amount of computer time. The objective is to minimize the makespan, while routing AGVs on a bidirectional network in a conflict-free manner. This problem is solved via column generation. The master problem in this column generation procedure has the makespan and vehicle interference constraints. Columns in the master problem are routes iteratively generated for each AGV. The subproblem is a constrained shortest path problem with time-dependent costs on the edges. An improvement procedure is developed to better the solution obtained at the end of the master-subproblem interactions. Several methods of iterating between the master and subproblem are experimented with in-depth computational experiments. Our empirical results indicate that the procedure as a whole usually generates solutions that are within a few percent of a proposed bound, within reasonable computer time.