Exact algorithms for the multi-compartment vehicle routing problem with flexible compartment sizes
Abstract The multi-compartment vehicle routing problem with flexible compartment sizes is a variant of the classical vehicle routing problem in which customers demand different product types and the vehicle capacity can be separated into different compartments each dedicated to a specific product type. The size of each compartment is not fixed beforehand but the number of compartments is limited. We consider two variants for dividing the vehicle capacity: On the one hand the vehicle capacity can be discretely divided into compartments and on the other hand compartment sizes can be divided continuously. The objective is to minimize the total distance of all vehicle routes such that all custo…
Stabilized branch-and-price algorithms for vector packing problems
Abstract This paper considers packing and cutting problems in which a packing/cutting pattern is constrained independently in two or more dimensions. Examples are restrictions with respect to weight, length, and value. We present branch-and-price algorithms to solve these vector packing problems (VPPs) exactly. The underlying column-generation procedure uses an extended master program that is stabilized by (deep) dual-optimal inequalities. While some inequalities are added to the master program right from the beginning (static version), other violated dual-optimal inequalities are added dynamically. The column-generation subproblem is a multidimensional knapsack problem, either binary, boun…
A branch-and-cut algorithm for the soft-clustered vehicle-routing problem
Abstract The soft-clustered vehicle-routing problem is a variant of the classical capacitated vehicle-routing problem (CVRP) in which customers are partitioned into clusters and all customers of the same cluster must be served by the same vehicle. We introduce a novel symmetric formulation of the problem in which the clustering part is modeled with an asymmetric sub-model. We solve the new model with a branch-and-cut algorithm exploiting some known valid inequalities for the CVRP that can be adapted. In addition, we derive problem-specific cutting planes and new heuristic and exact separation procedures. For square grid instances in the Euclidean plane, we provide lower-bounding techniques …