Optimization Online


A Robust Approach to the Capacitated Vehicle Routing Problem with Uncertain Travel Times

Lars Eufinger (eufinger***at***itl.tu-dortmund.de)
Jannis Kurtz (jannis.kurtz***at***math.tu-dortmund.de)
Christoph Buchheim (christoph.buchheim***at***math.tu-dortmund.de)
Uwe Clausen (clausen***at***itl.tu-dortmund.de)

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 to calculate a set of k feasible solutions in a preprocessing phase. Once a scenario occurs, the corresponding best solution may be picked out of the set of candidates. The aim is then to determine the k candidates such that the respective best one of them is worst-case optimal, which 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 also heuristics for the CVRP can 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.

Keywords: Capacitated Vehicle Routing Problem, Robust Optimization, K-Adaptability

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Robust Optimization

Category 3: Combinatorial Optimization


Download: [PDF]

Entry Submitted: 12/09/2016
Entry Accepted: 12/09/2016
Entry Last Modified: 11/09/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society