Large Multiple Neighborhood Search for the Soft-Clustered Vehicle-Routing Problem

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

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

Abstract: The soft-clustered vehicle-routing problem (SoftCluVRP) is a variant of the classical capacitated vehiclerouting problem. Customers are partitioned into clusters and all customers of the same cluster must be served by the same vehicle. In this paper, we present a large multiple neighborhood search for the SoftCluVRP. We design and analyze multiple cluster destroy and repair operators as well as two post-optimization components, which are both based on variable neighborhood descent. The first allows inter-route exchanges of complete clusters, while the second searches for intra-route improvements by combining classical neighborhoods (2- opt, Or-Opt, double-bridge) and the Balas-Simonetti neighborhood. Computational experiments show that our algorithm clearly outperforms the only existing heuristic approach from the literature. By solving benchmark instances, we provide 130 new best solutions for 220 medium-sized instances with up to 483 customers and prove 12 of them to be optimal.

Keywords: Vehicle Routing; Clustered Vehicle Routing; Large neighborhood search (search for similar items in EconPapers)
JEL-codes: C91 C92 D03 D91 (search for similar items in EconPapers)
Pages: 26 pages
Date: 2019-01-16
New Economics Papers: this item is included in nep-cmp, nep-tre and nep-ure
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1904.pdf First version, 2019 (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:1904

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 ().