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

Autor: Francesco Cavaliere, Emilio Bendotti, Matteo Fischetti
Rok vydání: 2022
Předmět:
Zdroj: Mathematical Programming Computation. 14:749-779
ISSN: 1867-2957
1867-2949
DOI: 10.1007/s12532-022-00224-2
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: