Scientific Program > Talks by Speaker > Hessler Katrin

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. In contrast to the non-soft variant, a cluster must not be served completely before the next cluster is served, but visits to customers of the same cluster can be interrupted by visits to customers of another cluster. We introduce a new two-index formulation of the problem and solve it with a branch-and-cut algorithm. In addition to problem-specific cutting planes for clusters, known valid inequalities for the CVRP can be adapted, e.g., MTZ-based subtour-elimination constraints, capacity cuts etc. We compare different model formulations and separation procedures. Computational results on benchmark instances show the usefulness of the new branch-and-cut.