A Robust Approach to the Capacitated Vehicle Routing Problem with Uncertain Costs

INFORMS Journal on Optimization, vol. 2, pp. 79–95

Abstract

We investigate a robust approach for solving the capacitated vehicle routing problem (CVRP) with uncertain travel times. It is based on the concept of K-adaptability, which allows one to calculate a set of k feasible solutions in a preprocessing phase before the scenario is revealed. Once a scenario occurs, the corresponding best solution may be picked out of the set of candidates. The aim is to determine the k candidates by hedging against the worst-case scenario, as is common in robust optimization. This idea leads to a min-max-min problem. In this paper, we propose an oracle-based algorithm for solving the resulting min-max-min CVRP, calling an exact algorithm for the deterministic problem in each iteration. Moreover, we adjust this approach such that heuristics for the CVRP can also be used. In this way, we derive a heuristic algorithm for the min-max-min problem, which turns out to yield good solutions in a short running time. All algorithms are tested on standard benchmark instances of the CVRP.

Authors 4

1. Lars Eufinger

   Deutsche Bahn (Germany)

   Affiliation as printed

   Deutsche Bahn, 60329 Frankfurt am Main, Germany;

2. Jannis Kurtz Aachen Department for Mathematics

   RWTH Aachen University

   Affiliation as printed

   Department for Mathematics, RWTH Aachen University, 52062 Aachen, Germany;

3. Christoph Buchheim

   TU Dortmund University

   Affiliation as printed

   Department for Mathematics, TU Dortmund University, 44227 Dortmund, Germany;

4. Uwe Clausen

   TU Dortmund University

   Affiliation as printed

   Institute of Transport Logistics, TU Dortmund University, 44227 Dortmund, Germany