Large Multiple Neighborhood Search for the Clustered Vehicle-Routing Problem

Timo Hintsch () and Stefan Irnich ()
Additional contact information
Timo Hintsch: Johannes Gutenberg University Mainz
Stefan Irnich: Johannes Gutenberg University Mainz

No 1701, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz

Abstract: The clustered vehicle-routing problem (CluVRP) is a variant of the classical capacitated vehicle-routing problem (CVRP) 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 (LMNS) which makes use of multiple cluster destroy and repair operators and a variable-neighborhood descent (VND) for postoptimization. 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)
New Economics Papers: this item is included in nep-cmp, nep-tre and nep-ure
Date: 2017-01-23
References: View references in EconPapers View complete reference list from CitEc
Citations: Track citations by RSS feed

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1701.pdf First version, 2017 (application/pdf)

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:jgu:wpaper:1701

Access Statistics for this paper

More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().