Journal
DISCRETE APPLIED MATHEMATICS
Volume 288, Issue -, Pages 218-234Publisher
ELSEVIER
DOI: 10.1016/j.dam.2020.08.017
Keywords
Vehicle routing; Clustered customers; Branch-and-cut
Categories
Ask authors/readers for more resources
The soft-clustered vehicle-routing problem is a variant of the classical capacitated vehicle-routing problem, with a novel symmetric formulation and an asymmetric sub-model for clustering. A branch-and-cut algorithm is used to solve the new model, with problem-specific cutting planes and separation procedures introduced. Computational results show that the algorithm can now solve several previously open instances to proven optimality.
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 and a reduction scheme that is also applicable to the respective traveling salesman problem. In comprehensive computational test on standard benchmark instances, we compare the different formulations and separation strategies in order to determine a best performing algorithmic setup. The computational results with this branch-and-cut algorithm show that several previously open instances can now be solved to proven optimality. (C) 2020 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available