{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T08:02:39Z","timestamp":1767945759926,"version":"3.49.0"},"reference-count":6,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,9,21]],"date-time":"2024-09-21T00:00:00Z","timestamp":1726876800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,21]],"date-time":"2024-09-21T00:00:00Z","timestamp":1726876800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003500","name":"Universit\u00e0 degli Studi di Padova","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003500","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cent Eur J Oper Res"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>A recent paper (Di Giacomo et al. Cent Eur J Oper Res 28:1069\u20131090, 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\u2019 origins and destinations. In this amending note, we will analyse the results in Di Giacomo et\u00a0al. (Cent Eur J Oper Res 28:1069\u20131090, 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.<\/jats:p>","DOI":"10.1007\/s10100-024-00940-1","type":"journal-article","created":{"date-parts":[[2024,9,24]],"date-time":"2024-09-24T09:25:38Z","timestamp":1727169938000},"page":"49-61","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Amending \u201cA note on solving the fleet quickest routing problem on a grid graph\u201d"],"prefix":"10.1007","volume":"34","author":[{"given":"Giovanni","family":"Andreatta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9081-1816","authenticated-orcid":false,"given":"Carla","family":"De Francesco","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luigi","family":"De Giovanni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,21]]},"reference":[{"key":"940_CR1","first-page":"419","volume":"62","author":"G Andreatta","year":"2010","unstructured":"Andreatta G, De Giovanni L, Salmaso G (2010) Fleet quickest routing on grids: a polynomial algorithm. Int. J. Pure Appl. Math. 62:419\u2013432","journal-title":"Int. J. Pure Appl. Math."},{"key":"940_CR2","doi-asserted-by":"publisher","first-page":"8188","DOI":"10.3390\/s21248188","volume":"21","author":"G Andreatta","year":"2021","unstructured":"Andreatta G, De Francesco C, De Giovanni L (2021) Algorithms for smooth, safe and quick routing on sensor-equipped grid networks. Sensors 21:8188","journal-title":"Sensors"},{"key":"940_CR3","unstructured":"Andreatta G, De Francesco C, De Giovanni L (2023), Experiments with the routing rule by Di Giacomo et al. 2020. GitHub. Available at https:\/\/github.com\/luigidegiovanni\/fqrpg8digiac"},{"key":"940_CR4","doi-asserted-by":"publisher","first-page":"1363","DOI":"10.1057\/s41274-016-0152-9","volume":"68","author":"M Cenci","year":"2017","unstructured":"Cenci M, Di Giacomo M, Mason F (2017) A note on a mixed routing and scheduling problem on a grid graph. J. Oper. Res. Soc. 68:1363\u20131376","journal-title":"J. Oper. Res. Soc."},{"key":"940_CR5","volume-title":"Optimization and decision science: operations research, inclusion and equity","author":"C De Francesco","year":"2023","unstructured":"De Francesco C, De Giovanni L (2023) Integer linear programming formulations for the fleet quickest routing problem on grids. In: Cappanera P, Lapucci M, Schoen F, Sciandrone M, Tardella F, Visintin F (eds) Optimization and decision science: operations research, inclusion and equity. Springer, Cham"},{"key":"940_CR6","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1007\/s10100-019-00620-5","volume":"28","author":"M Di Giacomo","year":"2020","unstructured":"Di Giacomo M, Mason F, Cenci M (2020) A note on solving the fleet quickest routing problem on a grid graph. Cent. Eur. J. Oper. Res. 28:1069\u20131090","journal-title":"Cent. Eur. J. Oper. Res."}],"container-title":["Central European Journal of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-024-00940-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10100-024-00940-1","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-024-00940-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T06:37:41Z","timestamp":1767940661000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10100-024-00940-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,21]]},"references-count":6,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["940"],"URL":"https:\/\/doi.org\/10.1007\/s10100-024-00940-1","relation":{},"ISSN":["1435-246X","1613-9178"],"issn-type":[{"value":"1435-246X","type":"print"},{"value":"1613-9178","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,21]]},"assertion":[{"value":"9 September 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 September 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no Conflict of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}