A note on a mixed routing and scheduling problem on a grid graph |
| |
Authors: | Marisa Cenci Mirko Di Giacomo Francesco Mason |
| |
Affiliation: | 1.Department of Business Studies,University of Rome III,Rome,Italy;2.Department of Management,University of Venice,Venice,Italy |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|