An integrated local-search/set-partitioning refinement heuristic for the Capacitated Vehicle Routing Problem

  • In this paper, an effective heuristic algorithm for large-scale instances of the Capacitated Vehicle Routing Problem is proposed. The technique consists in a local search method entangled with a restricted Set Partitioning problem optimization. Helsgaun’s LKH-3 algorithm has been used for the local search phase, with a number of implementation improvements. The restricted Set Partitioning formulation is solved by means of an exact commercial Integer Liner Programming solver. The resulting algorithm is able to consistently improve the solutions obtained by a state-of-the-art heuristic from the literature, as well as some of the best-know solutions maintained by the CVRPLIB website.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Francesco Cavaliere, Emilio Bendotti, Matteo Fischetti
DOI:https://doi.org/10.1007/s12532-022-00224-2
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2022
Volume:14
Issue:4
Page Number:31
First Page:749
Last Page:779
Mathematical Programming Computation :MPC 2022 - Issue 4
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.