A Vehicle Routing heuristic based on accelerated LKH-3 coupled with Set Partitioning

Francesco Cavaliere, Matteo Fischetti, Keld Helsgaun

Research output: Contribution to conference › Paper › Research

Abstract

In our work, an effective refining heuristic algorithm for large-scale instances of Vehicle Routing Problems has been developed. The technique consists in a local search step entangled with restricted Set Partitioning problem optimization. Helsgaun’s LKH-3 algorithm has been used for the local search phase, with a number of acceleration techniques to improve its performance. The restricted Set Partitioning formulation is solved by means of a novel Set Partitioning heuristic inspired by the technique proposed by Caprara et al for the Set Covering problem. The resulting algorithm has been able to improve many best-known solutions for both CVRP and VRPTW instances used in the DIMACS 12th Implementation Challenge.
Original languageEnglish
Publication date2022
Publication statusPublished - 2022
Event
12th DIMACS Implementation Challenge: Vehicle Routing Problems - Online, Piscataway, NJ, United States
Duration: 5 Apr 2022 → 8 Apr 2022
Conference number: 12
http://dimacs.rutgers.edu/events/details?eID=1090

Workshop

Workshop
12th DIMACS Implementation Challenge
Number12
LocationOnline
Country/TerritoryUnited States
CityPiscataway, NJ
Period05/04/2022 → 08/04/2022
Internet address

Keywords

  • Vehicle routing
  • CVRP
  • VRPTW

Link to document

Cite this