Inter-Depot Moves and Dynamic-Radius Search for Multi-Depot Vehicle Routing Problems

Jeam Bertrand Gauthier () and Stefan Irnich ()
Additional contact information
Jeam Bertrand Gauthier: Johannes Gutenberg University Mainz
Stefan Irnich: Johannes Gutenberg University Mainz

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

Abstract: Radius search is an effective neighborhood exploration technique for standard edge-exchange neighborhoods such as 2-opt, 2-opt*, swap, relocation, Or-opt, string exchange, etc. Up to now, it has only been used for vehicle routing problems with a homogeneous fleet and in the single-depot context. In this work, we extend dynamic-radius search to the multi-depot vehicle routing problem, in which 2-opt and 2-opt* moves may involve routes from different depots. To this end, we equip dynamic-radius search with a modified pruning criterion that still guarantees identifying a best-improving move, either intra-depot or inter-depot, with little additional computational effort. We experimentally confirm that substantial speedups of factors of 100 and more are observed compared to an also optimized implementation of lexicographic search, another effective neighborhood exploration technique using a feasibility-based pruning criterion. Moreover, the computational results show that depot swapping strongly favors heuristic solution quality, especially for multi-depot configurations where depots are not located close to each other.

Keywords: Vehicle routing; Local search; Sequential search; Dynamic-radius search; Inter-depot (search for similar items in EconPapers)
Pages: 31 pages
Date: 2020-02-25
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_2004.pdf First version, 2020 (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:2004

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