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

This paper is concerned with the problem of finding collision-free, nonstop Manhattan paths for a set of vehicles that move on a grid, each from a node on the bottom row to the top of the destination column; in particular, we are interested in minimising the number of rows that allow such routing. This problem is known as the Fleet Quickest Routing Problem on Grids. We propose an Integer Linear Programming formulation, introduce some valid inequalities and present a reduced-size model, based on the analysis of vehicle movements on the grid. Computational tests, performed on random benchmarks, show the impact of inequalities on the proposed formulation and that reducing the size of the formulation results in better performances for some classes of instances.