Conflict-free shortest-time bidirectional AGV roueting.

This paper presents an efficient algorithm for finding conflict-free shortest-time routes for automated guided vehicles moving in a bidirectional flow path network. The proposed algorithm is based on Dijkstra's shortest-path method. It maintains, for each node, a list of time windows reserved by scheduled vehicles and a list of free time windows available for vehicles to be scheduled We introduce the concept of time window graph in which the node set represents the free time windows and the arc set represents the reachability between the free time windows. Then the algorithm routes the vehicles through the free time windows of the time window graph instead Cf the physical nodes of the flow path network. It requires o(v4n2) computations in the worst case. where v is the number of vehicles and ii is the number of nudes. [ABSTRACT FROM AUTHOR]