A note on solving the Fleet Quickest Routing Problem on a grid graph

Mirko Giacomo (), Francesco Mason and Marisa Cenci ()
Additional contact information
Mirko Giacomo: University of Rome III
Marisa Cenci: University of Rome III

Central European Journal of Operations Research, 2020, vol. 28, issue 3, No 10, 1069-1090

Abstract: Abstract We address the Fleet Quickest Routing Problem (FQRP) on a grid graph, i.e. the problem of finding the paths $$ n $$ n vehicles have to perform to reach their destinations by moving from the lowest to the highest level (row) of a grid, respecting capacity constraints on the arcs and nodes in the shortest time possible. Traversing an arc of the grid graph takes one unit of time: in this way, a solution is optimal if a vehicle travels along one of the shortest paths it can find from its starting node to its destination without stopping, meeting the capacity constraints we mentioned above. Such a path is made of both horizontal and vertical steps, from the lowest to the highest level of the grid, without cycles. The existence of such a solution is guaranteed by a sufficient number of levels. If this not being, an optimal solution could require stopping vehicles somewhere or making them travel on a non-shortest path. In a previous work, it has been proved that $$ m^{ *} $$ m ∗ levels, where $$ m^{ *} $$ m ∗ is an increasing function of $$ n $$ n , are sufficient to solve FQRP on grid graphs, when each vehicle performs all the horizontal steps of its path, if any, on one and only one level. The main contribution of this paper is the proof that, relaxing this property, the number of levels needed to guarantee a feasible and optimal solution is constant, i.e. it is 8. Whatever the number of vehicles, in a grid graph $$ (8 \times n) $$ ( 8 × n ) it is always possible to find $$ n $$ n shortest paths, one for each vehicle, which do not create conflicts and route every vehicle to its destination. Moreover, a routing rule that allows finding the solution to FQRP in every $$ 8 \times n $$ 8 × n grid graph, whatever the destinations of the vehicles are, is provided. Practical relevance of FQRP mainly concerns the routing of Automated Guided Vehicles as well as the routing of aircrafts in airports.

Keywords: Routing; Logistics; Graph theory; Grid graph; Transportation (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10100-019-00620-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:cejnor:v:28:y:2020:i:3:d:10.1007_s10100-019-00620-5

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10100

DOI: 10.1007/s10100-019-00620-5

Access Statistics for this article

Central European Journal of Operations Research is currently edited by Ulrike Leopold-Wildburger

More articles in Central European Journal of Operations Research from Springer, Slovak Society for Operations Research, Hungarian Operational Research Society, Czech Society for Operations Research, Österr. Gesellschaft für Operations Research (ÖGOR), Slovenian Society Informatika - Section for Operational Research, Croatian Operational Research Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().