Integer Linear Programming Formulations for the Fleet Quickest Routing Problem on Grids

In an automated transportation system, a fleet of vehicles moves on a grid, each from its starting point on one side, to its destination on the opposite side. For the sake of efficiency, the only allowed routes are nonstop shortest paths. Among these, one route for each vehicle has to be properly chosen, avoiding that two vehicles cross the same node or move on the same edge at the same time. Therefore, an assignment of origin-to-destination nonstop collision-free shortest path routes is required. The Fleet Quickest Routing Problem on Grids aims at finding the minimum number of grid lanes allowing for such an assignment. We present two Integer Linear Programming models that exploit some combinatorial properties of conflicting shortest paths: the first one has binary variables and refines a multicommodity flow formulation; the second one exploits a compact representation of shortest paths with a reduced number of integer variables. We compare the two formulations through test on random and on purpose generated instances, showing the better performance of the compact formulation, and we discuss their potential towards more efficient methods.