Determining the shortest path for a vehicle moving on a network is easy. If more vehicles share the same network resources and we want vehicles to reach their destinations as soon as possible, moving on shortest paths might not be the optimal solution. In fact, conflicts may arise, requiring some vehicles to stay idle at some point of the shortest path: choosing an appropriate schedule on different paths may be quicker. The problem of finding the best set of conflict-free paths and schedule arises in many contexts: the coordination of automated guided vehicles, the management of airport groundside traffic, etc. After defining the general problem and proving its NP-hardness, we give a polynomial optimal dispatching algorithm for grids.
Fleet Quickest Routing on Grids: a Polynomial Algorithm
ANDREATTA, GIOVANNI;DE GIOVANNI, LUIGI;
2010
Abstract
Determining the shortest path for a vehicle moving on a network is easy. If more vehicles share the same network resources and we want vehicles to reach their destinations as soon as possible, moving on shortest paths might not be the optimal solution. In fact, conflicts may arise, requiring some vehicles to stay idle at some point of the shortest path: choosing an appropriate schedule on different paths may be quicker. The problem of finding the best set of conflict-free paths and schedule arises in many contexts: the coordination of automated guided vehicles, the management of airport groundside traffic, etc. After defining the general problem and proving its NP-hardness, we give a polynomial optimal dispatching algorithm for grids.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
