Conflict-free shortest-time bidirectional AGV routeing

Publisher Website
Google Scholar
Abstract
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 of 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 n is the number of nodes.

This publication has 3 references indexed in Scilit: