Optimization Online


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

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 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 it 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 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: 08/20/2018

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