Open Collections

Vehicle routing with subtours

Banff International Research Station for Mathematical Innovation and Discovery

When delivering items to a set of destinations, one can save time and cost by passing a subset to a sub-contractor at any point en route. We consider a model where a set of items are initially loaded in one vehicle and should be distributed before a given deadline $T$. In addition to travel time and time for deliveries, we assume that there is a fixed delay for handing over an item from one vehicle to another. We will show that it is easy to decide whether an instance is feasible, i.e., whether it is possible to deliver all items before the deadline $T$. We then consider computing a feasible tour of minimum cost, where we incur a cost per unit distance traveled by the vehicles, and a setup cost for every used vehicle. Our problem arises in practical applications and generalizes classical problems such as shallow-light trees and the bounded-latency problem. Our main result is a polynomial-time algorithm that, for any given $\alpha > 0$ and any feasible instance, computes a solution that delivers all items before time $(1+ \alpha) T$ and has cost $O(1 + 1 / \alpha)$ OPT, where OPT is the minimum cost of any feasible solution. (Joint work with Jochen Konemann and Jens Vygen. https://arxiv.org/pdf/1801.04991)

Mathematics; Computer science; Operations research, mathematical programming; Operation research

video/mp4

Author affiliation: University of Bonn

2020-12-07

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/76682

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/