Dispatching and conflict-free routing of automated guided vehicles with varying speeds

Automated Guided Vehicles (AGVs) are a highly sophisticated and increasingly popular type of material handling device in flexible manufacturing systems. An Automated Guided Vehicle System (AGVS) is typically controlled by a host computer, which is responsible for making dispatching and routing decisions. This paper will sketch results from an ongoing research project while addressing an important issue, that of handling different vehicle speeds. Formulation and solution methodologies for the static routing problem in which demand assignment of the AGVs are known are presented. The objective is to minimize the makespan, while routing AGVs on a bi-directional network in a conflict-free manner. 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. In prior work, the authors have tested a column generation scheme for a similar problem, but with AGVs traveling at a constant speed - see Krishnamurthy et al. (1993).