{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T17:31:40Z","timestamp":1767979900595,"version":"3.49.0"},"reference-count":44,"publisher":"MDPI AG","issue":"24","license":[{"start":{"date-parts":[[2021,12,8]],"date-time":"2021-12-08T00:00:00Z","timestamp":1638921600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Automation plays an important role in modern transportation and handling systems, e.g., to control the routes of aircraft and ground service equipment in airport aprons, automated guided vehicles in port terminals or in public transportation, handling robots in automated factories, drones in warehouse picking operations, etc. Information technology provides hardware and software (e.g., collision detection sensors, routing and collision avoidance logic) that contribute to safe and efficient operations, with relevant social benefits in terms of improved system performance and reduced accident rates. In this context, we address the design of efficient collision-free routes in a minimum-size routing network. We consider a grid and a set of vehicles, each moving from the bottom of the origin column to the top of the destination column. Smooth nonstop paths are required, without collisions nor deviations from shortest paths, and we investigate the minimum number of horizontal lanes allowing for such routing. The problem is known as fleet quickest routing problem on grids. We propose a mathematical formulation solved, for small instances, through standard solvers. For larger instances, we devise heuristics that, based on known combinatorial properties, define priorities, and design collision-free routes. Experiments on random instances show that our algorithms are able to quickly provide good quality solutions.<\/jats:p>","DOI":"10.3390\/s21248188","type":"journal-article","created":{"date-parts":[[2021,12,8]],"date-time":"2021-12-08T23:30:00Z","timestamp":1639006200000},"page":"8188","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Algorithms for Smooth, Safe and Quick Routing on Sensor-Equipped Grid Networks"],"prefix":"10.3390","volume":"21","author":[{"given":"Giovanni","family":"Andreatta","sequence":"first","affiliation":[{"name":"Dipartimento di Matematica \u201cTullio Levi-Civita\u201d, Universit\u00e0 degli Studi di Padova, 35122 Padova, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9081-1816","authenticated-orcid":false,"given":"Carla","family":"De Francesco","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica \u201cTullio Levi-Civita\u201d, Universit\u00e0 degli Studi di Padova, 35122 Padova, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8035-0013","authenticated-orcid":false,"given":"Luigi","family":"De Giovanni","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica \u201cTullio Levi-Civita\u201d, Universit\u00e0 degli Studi di Padova, 35122 Padova, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,12,8]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.sbspro.2013.12.817","article-title":"A fast heuristic for airport ground-service equipment-and-staff allocation","volume":"108","author":"Andreatta","year":"2014","journal-title":"Procedia Soc. Behav. Sci."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Fleuren, H., Hertog, D., and Kort, P. (2005). Conflict-free real-time AGV routing. Operations Research Proceedings 2004, Proceedings of the Operations Research 2004 Conference, Tilburg, The Netherlands, 1\u20133 September 2004, Springer.","DOI":"10.1007\/3-540-27679-3"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"102455","DOI":"10.1016\/j.tre.2021.102455","article-title":"Applications of smart technologies in logistics and transport: A review","volume":"153","author":"Chung","year":"2021","journal-title":"Transp. Res. Part E Logist. Transp. Rev."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1515\/logi-2017-0006","article-title":"Innovation of the process of inventorying of the selected transport units: Case study in the automotive industry","volume":"8","year":"2017","journal-title":"LOGI Sci. J. Transp. Logist."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1007\/978-3-030-85910-7_48","article-title":"Automatic drones for factory inspection: The role of virtual simulation","volume":"Volume 633","author":"Dolgui","year":"2021","journal-title":"Advances in Production Management Systems. Artificial Intelligence for Sustainable and Resilient Production Systems"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"280","DOI":"10.3846\/16484142.2016.1174882","article-title":"Determining the most suitable layout of space for the loading units\u2019 handling in the maritime port","volume":"33","author":"Stopka","year":"2018","journal-title":"Transport"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1363","DOI":"10.1057\/s41274-016-0152-9","article-title":"A note on a mixed routing and scheduling problem on a grid graph","volume":"68","author":"Cenci","year":"2017","journal-title":"J. Oper. Res. Soc."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1109\/TPDS.2008.75","article-title":"Trade-offs between stretch factor and load-balancing ratio in routing on growth-restricted graphs","volume":"20","author":"Gao","year":"2009","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1016\/j.ejor.2004.09.020","article-title":"Survey of research in the design and control of automated guided vehicle systems","volume":"170","author":"Vis","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Kim, K.H., Jeon, S.M., and Ryu, K.R. (2007). Deadlock prevention for automated guided vehicles in automated container terminals. Container Terminals and Cargo Systems, Springer.","DOI":"10.1007\/978-3-540-49550-5"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/S0925-5273(02)00370-5","article-title":"Cyclic deadlock prediction and avoidance for zone-controlled AGV system","volume":"83","author":"Moorthy","year":"2003","journal-title":"Int. J. Prod. Econ."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/s11740-013-0456-4","article-title":"Distributed control of multi-AGV system based on regional control model","volume":"7","author":"Zheng","year":"2013","journal-title":"Prod. Eng."},{"key":"ref_13","unstructured":"Wu, N.Q., and Zhou, M.C. (2000, January 24\u201328). Resource-oriented Petri nets for deadlock avoidance in automated manufacturing. Proceedings of the 2000 IEEE International Conference on Robotics and Automation, San Francisco, CA, USA."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1193","DOI":"10.1109\/TSMCB.2005.850141","article-title":"Modeling and deadlock avoidance of automated manufacturing systems with multiple automated guided vehicles","volume":"35","author":"Wu","year":"2005","journal-title":"IEEE Trans. Syst. Man Cybern. Part B"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1109\/70.388784","article-title":"Graph theoretic deadlock detection and resolution for flexible manufacturing systems","volume":"11","author":"Cho","year":"1995","journal-title":"IEEE Trans. Robot. Autom."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Zhai, W., Tong, X., Miao, S., Cheng, C., and Ren, F. (2019). Collision detection for UAVs based on GeoSOT-3D grids. ISPRS Int. J. Geo-Inf., 8.","DOI":"10.3390\/ijgi8070299"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Koszelew, J., Karbowska-Chilinska, J., Ostrowski, K., Kuczy\u0144ski, P., Kulbiej, E., and Wo\u0142ejsza, P. (2020). Beam search algorithm for anti-collision trajectory planning for many-to-many encounter situations with autonomous surface vehicles. Sensors, 20.","DOI":"10.3390\/s20154115"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"26022","DOI":"10.1109\/ACCESS.2018.2819199","article-title":"Collision-free route planning for multiple AGVs in an automated warehouse based on collision classification","volume":"6","author":"Zhang","year":"2018","journal-title":"IEEE Access"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/s13676-012-0008-7","article-title":"Conflict-free vehicle routing","volume":"1","author":"Gawrilow","year":"2012","journal-title":"EURO J. Transp. Logist."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","article-title":"Color-coding","volume":"42","author":"Alon","year":"1995","journal-title":"J. Assoc. Comput. Mach."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1077","DOI":"10.1287\/opre.41.6.1077","article-title":"Developing conflict-free routes for automated guided vehicles","volume":"41","author":"Krishnamurthy","year":"1993","journal-title":"Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"2177","DOI":"10.1080\/00207540110038531","article-title":"A bi-directional path layout for conflict-free routing of AGVs","volume":"39","author":"Qiu","year":"2001","journal-title":"Int. J. Prod. Res."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1406","DOI":"10.1016\/j.robot.2013.07.012","article-title":"An optimal algorithm for two robots path planning problem on the grid","volume":"61","author":"Davoodi","year":"2013","journal-title":"Robot. Auton. Syst."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"J\u00e4ger, W., and Krebs, H.J. (2008). Dynamic routing of automated guided vehicles in real-time. Mathematics: Key Technology for the Future. Joint Projects between Universities and Industry 2004\u20132007, Springer.","DOI":"10.1007\/978-3-642-55753-8"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Yu, J., and La Valle, S.M. (2013, January 6\u201310). Planning optimal paths for multiple robots on graphs. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Karlsruhe, Germany.","DOI":"10.1109\/ICRA.2013.6631084"},{"key":"ref_26","unstructured":"Ahuja, R.K., Magnanti, T.L., and Orlin, J.B. (1993). Network Flows: Theory, Algorithms, and Applications, Prentice Hall."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/j.procs.2018.07.018","article-title":"Methodology for path planning and optimization of mobile robots: A review","volume":"133","author":"Zafar","year":"2018","journal-title":"Procedia Comput. Sci."},{"key":"ref_28","first-page":"442","article-title":"Research on the collision-free path planning of multi-AGVs system based on improved A* algorithm","volume":"6","author":"Yuan","year":"2016","journal-title":"Am. J. Oper. Res."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Mugarza, I., and Mugarza, J.C. (2021). A coloured Petri net- and D* Lite-based traffic controller for Automated Guided Vehicles. Electronics, 10.","DOI":"10.3390\/electronics10182235"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Santos, J., Rebelo, P.M., Rocha, L.F., Costa, P., and Veiga, G. (2021). A* based routing and scheduling modules for multiple AGVs in an industrial scenario. Robotics, 10.","DOI":"10.3390\/robotics10020072"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.artint.2014.11.006","article-title":"Conflict-based search for optimal multi-agent pathfinding","volume":"219","author":"Sharon","year":"2015","journal-title":"Artif. Intell."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1613\/jair.1.11734","article-title":"Robust multi-agent path finding and executing","volume":"67","author":"Atzmon","year":"2020","journal-title":"J. Artif. Intell. Res."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"791","DOI":"10.1287\/opre.2018.1814","article-title":"Ship traffic optimization for the Kiel canal","volume":"67","year":"2019","journal-title":"Oper. Res."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/s11067-012-9179-x","article-title":"Vortex-based zero-conflict design of urban road networks","volume":"13","author":"Eichler","year":"2013","journal-title":"Netw. Spat. Econ."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"129","DOI":"10.3141\/2467-14","article-title":"Equilibrium analysis of low-conflict network designs","volume":"2467","author":"Boyles","year":"2014","journal-title":"Transp. Res. Rec."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"37","DOI":"10.4038\/engineer.v51i4.7312","article-title":"Obtaining the optimum block length of the Chet network: An at-grade transportation network without signalized intersections, roundabouts, or stop signs","volume":"50","author":"Liyanage","year":"2018","journal-title":"Engineer"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"988","DOI":"10.1287\/trsc.2021.1061","article-title":"Rhythmic control of automated traffic\u2014Part II: Grid network rhythm and online routing","volume":"55","author":"Lin","year":"2021","journal-title":"Transp. Sci."},{"key":"ref_38","first-page":"419","article-title":"Fleet quickest routing on grids: A polynomial algorithm","volume":"62","author":"Andreatta","year":"2010","journal-title":"Int. J. Pure Appl. Math."},{"key":"ref_39","unstructured":"Andreatta, G., De Francesco, C., De Giovanni, L., and Salmaso, G. (2021, December 02). A Note on FQRP-G. Available online: http:\/\/www.math.unipd.it\/~luigi\/manuscripts\/FQRP-G\/fqrp.pdf."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1007\/s10100-019-00620-5","article-title":"A note on solving the Fleet Quickest Routing Problem on a grid graph","volume":"28","author":"Mason","year":"2020","journal-title":"Cent. Eur. J. Oper. Res."},{"key":"ref_41","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1287\/ijoc.2018.0857","article-title":"Presolve reductions in Mixed Integer Programming","volume":"32","author":"Achterberg","year":"2020","journal-title":"INFORMS J. Comput."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Wolsey, L.A. (2020). Integer Programming, Wiley. [2nd ed.].","DOI":"10.1002\/9781119606475"},{"key":"ref_44","unstructured":"(2021, November 15). IBM CPLEX Optimizer. Available online: https:\/\/www.ibm.com\/it-it\/analytics\/cplex-optimizer."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/24\/8188\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:43:07Z","timestamp":1760168587000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/24\/8188"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,8]]},"references-count":44,"journal-issue":{"issue":"24","published-online":{"date-parts":[[2021,12]]}},"alternative-id":["s21248188"],"URL":"https:\/\/doi.org\/10.3390\/s21248188","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,8]]}}}