Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 270, Issue 1, Pages 118-131Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2018.02.056
Keywords
Vehicle routing; Clustered vehicle routing; Large neighborhood search
Funding
- Deutsche Forschungsgemeinschaft (DFG) [IR 122/7-1]
Ask authors/readers for more resources
The clustered vehicle-routing problem is a variant of the classical capacitated vehicle-routing problem in which customers are partitioned into clusters, and it is assumed that each cluster must have been served completely before the next cluster is served. This decomposes the problem into three subproblems, i.e., the assignment of clusters to routes, the routing inside each cluster, and the sequencing of the clusters in the routes. The second task requires the solution of several Hamiltonian path problems, one for each possibility to route through the cluster. We pre-compute the Hamiltonian paths for every pair of customers of each cluster. We present a large multiple neighborhood search which makes use of multiple cluster destroy and repair operators and a variable-neighborhood descent (VND) for post-optimization. The VND is based on classical neighborhoods such as relocate, 2-opt, and swap all working on the cluster level and a generalization of the Balas-Simonetti neighborhood modifying simultaneously the intra-cluster routings and the sequence of clusters in a route. Computational results with our new approach compare favorably to existing approaches from the literature. (C) 2018 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