Fleet Quickest Routing on Grid Subgraphs

We consider a routing network where a fleet of vehicles have to move from their origin to their destination. Network nodes correspond to vehicle origins and destinations, route crossing points or points where vehicles are allowed to stop and stay idle. Arcs correspond to directed or undirected routes between couples of nodes. For each arc/node a capacity is given, corresponding to the maximum number of vehicles that can move/stay idle on it. For each arc, a fixed traversal time is also given. The Fleet Quickest Routing (FQR) problem consists in determining a route for each vehicle in order to let it reach the desired destination as quickly as possible, e.g. minimizing the sum over all the arrival times. The problem arises in many contexts: the coordination of automated guided vehicles, the management of airport groundside traffic etc [2, 4]. A possible solution is to route vehicles on shortest paths. However, conflicts may arise, as several vehicles may need the same node or arc at the same time and capacity constraints might be violated. To avoid conflicts, vehicles may stay idle at some nodes for some time, waiting for the next arcs to become available. It follows that moving on a set of shortest paths may not be the optimal choice. Actually, FQR is NP-Hard on general networks [1, 3], while a polynomial Dispatching Algorithm (DA) [1] solves it on grids with equal arc traversal times and simultaneous vehicle starts. In this work, we propose an analysis toward fast heuristic solutions to more general FQR problems, based on modifications of DA. We consider non-complete grids, with arbitrary traversal time and arbitrary vehicle starting positions and times, and we compare different methods. Proposed methods apply the basic DA and use priority rules to solve detected conflicts. A simulation model is used to analyse the performance and compare different conflict management strategies.