Scientific Program > Talks by Speaker > Hintsch Timo

The clustered vehicle-routing problem (CluVRP) is a variant of the classical capacitated vehicle-routing problem in which the customers are partitioned into clusters, and it is assumed that each cluster must have been served in total before the next cluster can be served. This presentation considers the CluVRP with soft cluster constraints (CluVRPSC). Customers of same clusters must still be part of same routes, but do not need to be served contiguously any more. We present an exact branch-and-price-and-cut algorithm, compare different solution methods for the subproblem, and discuss branching strategies and the addition of cutting planes. First, the subproblem is solved as an elementary shortest path problem with resource constraints by labeling algorithms. Second, a mixed integer programming based branch-and-cut algorithm is developed. Both approaches are supplemented by heuristic approaches for partial pricing. To the best of our knowledge, this branch-and-price-and-cut algorithm is the first exact approach for the CluVRPSC.