Conflict-free scheduling and routing of automated guided vehicles in mesh topologies

Many storing and manufacturing systems tend to use automated guided vehicles (AGV) for speed, quality and safety as transporting objects. In this paper an integrated algorithm for scheduling and routing of AGVs in mesh-like systems is presented. The main characteristics of the scheduling algorithm are as follows: (1) prediction and prevention of conflicts, (2) arbitrary choice for AGVs to traverse shortest path from source to destination, (3) effect of priority policies to the scheduling result, and (4) no theoretical limitation on the number of participated AGVs. The proposed greedy algorithm for routing reduces the average number of conflicts and is closely related to the scheduling algorithm. We will also present mathematical and statistical models for the analysis of the algorithms. (C) 2008 Elsevier B.V. All rights reserved.