Routing a Fleet of Automated Vehicles in a Capacitated Transportation Network
Martin Schaefer, Michal Čáp, Jan Mrkos, Jiří Vokřínek
Abstract
Routing of a fleet of automated unit-occupancy vehicles in a capacitated transportation network is an emerging problem that needs to be addressed to realize large-scale automated transportation systems. We adopt an existing network-flow-based model for the problem and present a new reformulation based on Dantzig-Wolfe decomposition. This reformulation allows us to apply the column generation solution technique which, in turn, enables us to solve large-scale problem instances with tens of thousands of requests on networks with thousands of links. We empirically compare our method to the state-of-the-art approach on several standard benchmark instances and find that the computational time of our solution approach scales qualitatively better in all tested problem instance parameters: namely, in the size of the transportation network, in the magnitude of demand intensity, and in the number of demand flows.
BibTeX
@inproceedings{iros2019_routingafleetofa,
title = {Routing a Fleet of Automated Vehicles in a Capacitated Transportation Network},
author = {Martin Schaefer and Michal Čáp and Jan Mrkos and Jiří Vokřínek},
booktitle = {IROS 2019},
year = {2019}
}