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

Katrin Heßler () and Stefan Irnich ()
Additional contact information
Katrin Heßler: Department of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, D-55128 Mainz, Germany
Stefan Irnich: Department of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, D-55128 Mainz, Germany

INFORMS Journal on Computing, 2023, vol. 35, issue 1, 50-65

Abstract: We consider the exact solution of the basic version of the multiple-compartment vehicle-routing problem, which consists of clustering customers into groups, routing a vehicle for each group, and packing the demand of each visited customer 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 length of all vehicle routes such that all customers are visited. We study the shortest-path subproblem that arises when solving the problem with a branch-price-and-cut algorithm exactly. For this subproblem, we compare a standard dynamic-programming labeling approach with a new one that uses a partial dominance. The algorithm with standard labeling already struggles with relatively small instances, whereas 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)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1255 (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:inm:orijoc:v:35:y:2023:i:1:p:50-65

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().