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
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 diﬀerent branch-and-price algorithms for the exact solution of the SoftCluVRP. The algorithms diﬀer 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 diﬃcult. 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)
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1) Track citations by RSS feed
Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1813.pdf First version, 2018 (application/pdf)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
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 ().