期刊
INFORMS JOURNAL ON COMPUTING
卷 35, 期 1, 页码 50-65出版社
INFORMS
DOI: 10.1287/ijoc.2022.1255
关键词
vehicle routing; packing; shortest-path problem with resource constraints; dynamic-programming labeling; partial dominance
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据