On a Mixed Routing and Scheduling Problem on a Grid Graph

In this paper we study a particular case of the Fleet Quickest Routing Problem (FQRP) on a grid graph, i.e., a Manhattan graph of m×n nodes: nodes are placed in m lines (which we shall call levels) and n columns. FQRP is a particular Multi-commodity Flow Problem in which we must find the routes n vehicles have to perform from an initial position, at the lowest level, to a final position at the highest level. Vehicles must respect capacity constraints on the arcs and on the nodes of the grid. The objective consists in the minimization of the sum of times needed to route every vehicle. The problem arises when we must manage at the same time and automatically the movements of a fleet of vehicles. In this setting, the number of levels has a strong impact both on the existence of routes which do not use the same resource at the same time, and on the time needed to reach the final position. In the paper we prove that the minimum number of levels which guarantees a feasible solution is linked to a parameter defined as the maximum length of a C-type conflict chain we can build in a problem involving n vehicles. In the paper we also propose a strategy which allows to find the optimal route for every vehicle.