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
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 ï¬‚eet 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
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) Track citations by RSS feed
Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_2004.pdf First version, 2020 (application/pdf)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
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 ().