Amending “A note on solving the fleet quickest routing problem on a grid graph”

Abstract A recent paper (Di Giacomo et al. Cent Eur J Oper Res 28:1069–1090, 2020) on the Fleet Quickest Routing Problem on Grid graphs (FQRP-G) claims that eight levels guarantee that a fleet of vehicles, simultaneously starting from the bottom level of the grid, can reach the top level by moving on Manhattan paths without ever stopping and without collisions, independently of the number of vehicles and columns of the grid and the configuration of vehicles’ origins and destinations. In this amending note, we will analyse the results in Di Giacomo et al. (Cent Eur J Oper Res 28:1069–1090, 2020) and show that the routing rule leading to this claim cannot be applied to all instances of FQRP-G, and that it can cause collisions. The analysis points out sufficient conditions under which the proposed rule draws proven collision-free routes for FQRP-G using no more than eight levels. Computational experiments demonstrate the relevance of the eight-levels bound and the functionality of the routing rule in practice, showing that it correctly solves the majority of instances up to one thousand vehicles. From a theoretical perspective, the claim that eight (or any constant number of) levels are sufficient to solve any instance of FQRP-G remains an open issue.