We consider a particular case of the Fleet Quickest Routing Problem (FQRP) on a grid graph of m × n nodes that are placed in m levels and n columns. Starting nodes are placed at the first (bottom) level, and nodes of arrival are placed at the mth level. A feasible solution of FQRP consists in n Manhattan paths, one for each vehicle, such that capacity constraints are respected. We establish m*, i.e. the number of levels that ensures the existence of a solution to FQRP in any possible permutation of n destinations. In particular, m* is the minimum number of levels sufficient to solve any instance of FQRP involving n vehicles, when they move in the ways that the literature has until now assumed. Existing algorithms give solutions that require, for some values of n, more levels than m*. For this reason, we provide algorithm CaR, which gives a solution in a graph m* × n, as a minor contribution.
Cenci, M., Di Giacomo, M., & Mason, F. (2017). A note on a mixed routing and scheduling problem on a grid graph. JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1-14.
Titolo: | A note on a mixed routing and scheduling problem on a grid graph |
Autori: | |
Data di pubblicazione: | 2017 |
Rivista: | |
Citazione: | Cenci, M., Di Giacomo, M., & Mason, F. (2017). A note on a mixed routing and scheduling problem on a grid graph. JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1-14. |
Handle: | http://hdl.handle.net/11590/317322 |
Appare nelle tipologie: | 1.1 Articolo in rivista |