Conflict-free shortest-time bidirectional AGV routeing

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 schedules. The authors 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 of the physical nodes of the flow path network. It requires o(v⁴n²) computations in the worst case, where v is the number of vehicles and n is the number of nodes.