Partial Dominance in Branch-Price-and-Cut for the Basic Multi-Compartment Vehicle-Routing Problem

Katrin Heßler () and Stefan Irnich ()
Additional contact information
Katrin Heßler: Johannes Gutenberg University Mainz
Stefan Irnich: Johannes Gutenberg University Mainz

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

Abstract: We consider the exact solution of the basic version of the multiple-compartment vehicle-routing problem, i.e., a problem consisting of clustering customers into groups, routing a vehicle for each group, and packing demands of the visited customer uniquely into one of the vehicle’s compartments. Compartments have a fixed size, and there are no incompatibilities between the transported items or between items and compartments. The objective is to minimize the total distance of all vehicle routes such that all customers are visited. We study the shortest-path subproblem that arises when exactly solving the problem with a branch-price-andcut algorithm. For this subproblem, we compare a standard dynamic-programming labeling approach with a new one that utilizes a partial dominance. While the algorithm with standard labeling already struggles with relatively small instances, the one with partial dominance can cope with much larger instances.

Keywords: vehicle routing; packing; shortest-path problem with resource constraints; dynamic-programming labeling; partial dominance (search for similar items in EconPapers)
Pages: 32 pages
Date: 2021-02-11
New Economics Papers: this item is included in nep-cmp, nep-ore and nep-tre
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_2115.pdf First version, 2021 (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:2115

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 ().