IJPAM: Volume 62, No. 4 (2010)

FLEET QUICKEST ROUTING ON GRIDS:
A POLYNOMIAL ALGORITHM

Giovanni Andreatta$^1$, Luigi De Giovanni$^2$, Giorgio Salmaso$^3$
$^{1,2,3}$Department of Pure and Applied Mathematics
University of Padova
63, Via Trieste, Padova, 35121, ITALY
$^1$e-mail: giovanni.andreatta@unipd.it
$^2$e-mail: luigi@math.unipd.it
$^3$e-mail: giorgio.salmaso@studenti.unipd.it


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.

Received: May 25, 2010

AMS Subject Classification: 90B06, 90C35, 05C85

Key Words and Phrases: fleet routing, quickest paths, conflict management, exact dispatching algorithms

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2010
Volume: 62
Issue: 4