Algorithms for Smooth, Safe and Quick Routing on Sensor-Equipped Grid Networks
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 warehou...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-12-01
|
| Series: | Sensors |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1424-8220/21/24/8188 |
| _version_ | 1797500852360970240 |
|---|---|
| author | Giovanni Andreatta Carla De Francesco Luigi De Giovanni |
| author_facet | Giovanni Andreatta Carla De Francesco Luigi De Giovanni |
| author_sort | Giovanni Andreatta |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-10T03:09:49Z |
| format | Article |
| id | doaj.art-8bf7c2f14f7b46c688ba0e9fefe976ea |
| institution | Directory Open Access Journal |
| issn | 1424-8220 |
| language | English |
| last_indexed | 2024-03-10T03:09:49Z |
| publishDate | 2021-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Sensors |
| spelling | doaj.art-8bf7c2f14f7b46c688ba0e9fefe976ea2023-11-23T10:27:59ZengMDPI AGSensors1424-82202021-12-012124818810.3390/s21248188Algorithms for Smooth, Safe and Quick Routing on Sensor-Equipped Grid NetworksGiovanni Andreatta0Carla De Francesco1Luigi De Giovanni2Dipartimento di Matematica “Tullio Levi-Civita”, Università degli Studi di Padova, 35122 Padova, ItalyDipartimento di Matematica “Tullio Levi-Civita”, Università degli Studi di Padova, 35122 Padova, ItalyDipartimento di Matematica “Tullio Levi-Civita”, Università degli Studi di Padova, 35122 Padova, ItalyAutomation 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.https://www.mdpi.com/1424-8220/21/24/8188automated transportation networkcollision-free routinggrid networkoptimization algorithminteger linear programmingheuristics |
| spellingShingle | Giovanni Andreatta Carla De Francesco Luigi De Giovanni Algorithms for Smooth, Safe and Quick Routing on Sensor-Equipped Grid Networks Sensors automated transportation network collision-free routing grid network optimization algorithm integer linear programming heuristics |
| title | Algorithms for Smooth, Safe and Quick Routing on Sensor-Equipped Grid Networks |
| title_full | Algorithms for Smooth, Safe and Quick Routing on Sensor-Equipped Grid Networks |
| title_fullStr | Algorithms for Smooth, Safe and Quick Routing on Sensor-Equipped Grid Networks |
| title_full_unstemmed | Algorithms for Smooth, Safe and Quick Routing on Sensor-Equipped Grid Networks |
| title_short | Algorithms for Smooth, Safe and Quick Routing on Sensor-Equipped Grid Networks |
| title_sort | algorithms for smooth safe and quick routing on sensor equipped grid networks |
| topic | automated transportation network collision-free routing grid network optimization algorithm integer linear programming heuristics |
| url | https://www.mdpi.com/1424-8220/21/24/8188 |
| work_keys_str_mv | AT giovanniandreatta algorithmsforsmoothsafeandquickroutingonsensorequippedgridnetworks AT carladefrancesco algorithmsforsmoothsafeandquickroutingonsensorequippedgridnetworks AT luigidegiovanni algorithmsforsmoothsafeandquickroutingonsensorequippedgridnetworks |