Exact Solution of the Soft-Clustered Vehicle Routing Problem

Timo Hintsch () and Stefan Irnich ()
Additional contact information
Timo Hintsch: Johannes Gutenberg-University
Stefan Irnich: Johannes Gutenberg-University

No 1813, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz

Abstract: The soft-clustered vehicle-routing problem (SoftCluVRP) extends the classical capacitated vehicle-routing problem by one additional constraint: The customers are partitioned into clusters and feasible routes must respect the soft-cluster constraint, that is, all customers of the same clusters must be served by the same vehicle. In this article, we design and analyze different branch-and-price algorithms for the exact solution of the SoftCluVRP. The algorithms differ in the way the column-generation subproblem, a variant of the shortest-path problem with resource constraints (SPPRC), is solved. The standard approach for SPPRCs is based on dynamic-programming labeling algorithms. We show that even with all the recent acceleration techniques and tricks (e.g., partial pricing, bidirectional labeling, decremental state space relaxation) available for SPPRC labeling algorithms, the solution of the subproblem remains extremely difficult. The main contribution is the modeling and solution of the subproblem using a branch-and-cut algorithm. The conducted computational experiments prove that branch-and-price equipped with this integer programmingbased approach outperforms sophisticated labeling-based algorithms by one order of magnitude. The largest SoftCluVRP instances solved to optimality have more than 400 customers or more than 50 clusters.

Keywords: Vehicle Routing; branch-and-price; shortest-path problem with resource constraints; dynamic-programming labeling; branch-and-cut (search for similar items in EconPapers)
Pages: 36 pages
Date: 2018-09-24
New Economics Papers: this item is included in nep-cmp
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1813.pdf First version, 2018 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:jgu:wpaper:1813

Access Statistics for this paper

More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().