Lien pour le séminaire
Nº de réunion : 965 4543 0365
Code secret : 216335

The soft-clustered vehicle-routing problem (SoftCluVRP) extends the classical capacitated vehicle-routing problem by one additional constraint: The customers are partitioned into clusters and feasible routes must respect the soft-cluster constraint, that is, all customers of the same cluster must be served by the same vehicle. Likewise, the soft-clustered capacitated arc-routing problem (SoftCluCARP) is a restricted variant of the classical capacitated arc-routing problem. The only additional constraint is that the set of required edges, i.e., the streets to be serviced, is partitioned into clusters and feasible routes must respect the soft-cluster constraint, that is, all required edges of the same cluster must be served by the same vehicle. We present effective branch-price-and-cut algorithms for the exact solution of the SoftCluVRP and SoftCluCARP. The most important finding is that the pricing subproblems can be solved effectively with branch-and-cut algorithms, while labeling based approaches are not competitive. For many design choices of the branch-price-and-cut algorithms, we conducted comprehensive computational experiments that we summarize in the presentation. For the SoftCluCARP, we also analyze different strategies for the integration of subset-row inequalities.

*Webinaire organisé par le GERAD.

Séminaire de Guy Desaulniers, A branch-price-and-cut algorithm for the two-echelon vehicle routing problem with time windows, 1 décembre 2020