Journal
INFORMS JOURNAL ON COMPUTING
Volume 35, Issue 1, Pages 50-65Publisher
INFORMS
DOI: 10.1287/ijoc.2022.1255
Keywords
vehicle routing; packing; shortest-path problem with resource constraints; dynamic-programming labeling; partial dominance
Ask authors/readers for more resources
This study considers the exact solution to the basic version of the multiple-compartment vehicle-routing problem. It focuses on clustering customers, routing vehicles, and packing customer demand into compartments. The objective is to minimize the total length of all vehicle routes. The study compares different labeling approaches for solving the shortest-path subproblem, finding that partial dominance performs better than standard labeling.
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 vehi-cle 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 mini-mize 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 label-ing 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 domi-nance can cope with much larger instances.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available