Large multiple neighborhood search for the clustered vehicle-routing problem

Timo Hintsch and Stefan Irnich

European Journal of Operational Research, 2018, vol. 270, issue 1, 118-131

Abstract: 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.

Keywords: Vehicle routing; Clustered vehicle routing; Large neighborhood search (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718302066
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:270:y:2018:i:1:p:118-131

DOI: 10.1016/j.ejor.2018.02.056

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().