Large multiple neighborhood search for the soft-clustered vehicle-routing problem

The soft-clustered vehicle-routing problem (SoftCluVRP) is a variant of the classical capacitated vehicle-routing problem. Customers are partitioned into clusters and all customers of the same cluster must be served by the same vehicle. This paper presents a large multiple neighborhood search for the SoftCluVRP. The author designs and analyzes 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 the algorithm clearly outperforms the only existing heuristic approach from the literature. By solving benchmark instances, the author provides 130 new best solutions for 220 medium-sized instances with up to 483 customers and prove 12 of them to be optimal. Furthermore, the author describes a straightforward adaption of the algorithm to the clustered vehicle-routing problem, a variant of the SoftCluVRP.

• Record URL:
  • https://doi.org/10.1016/j.cor.2020.105132
• Record URL:
  • http://www.sciencedirect.com/science/article/pii/S0305054820302495
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/1793974
• Supplemental Notes:
  • © 2020 Elsevier Ltd. All rights reserved. Abstract reprinted with permission of Elsevier.
• Authors:
  • Hintsch, Timo
  • 0000-0002-5111-8872
• Publication Date: 2021-5

Language

• English

Media Info

• Media Type: Web
• Features: Figures; References; Tables;
• Pagination: 105132
• Serial:
  • Computers & Operations Research
  • Volume: 129
  • Issue Number: 0
  • Publisher: Elsevier
  • ISSN: 0305-0548
  • Serial URL: https://www.sciencedirect.com/journal/computers-and-operations-research

Subject/Index Terms

• TRT Terms: Algorithms; Delivery vehicles; Logistics; Routing
• Identifier Terms: Vehicle Routing Problem
• Subject Areas: Freight Transportation; Operations and Traffic Management; Planning and Forecasting;

Filing Info

• Accession Number: 01845512
• Record Type: Publication
• Files: TRIS
• Created Date: May 17 2022 10:47AM