1. A Fast and Scalable Heuristic for the Solution of Large-Scale Capacitated Vehicle Routing Problems.
- Author
-
Accorsi, Luca and Vigo, Daniele
- Subjects
- *
VEHICLE routing problem , *ALGORITHMS , *SOURCE code , *HEURISTIC , *METAHEURISTIC algorithms - Abstract
In this paper, we propose a fast and scalable, yet effective, metaheuristic called FILO to solve large-scale instances of the Capacitated Vehicle Routing Problem. Our approach consists of a main iterative part, based on the Iterated Local Search paradigm, which employs a carefully designed combination of existing acceleration techniques, as well as novel strategies to keep the optimization localized, controlled, and tailored to the current instance and solution. A Simulated Annealing-based neighbor acceptance criterion is used to obtain a continuous diversification, to ensure the exploration of different regions of the search space. Results on extensively studied benchmark instances from the literature, supported by a thorough analysis of the algorithm's main components, show the effectiveness of the proposed design choices, making FILO highly competitive with existing state-of-the-art algorithms, both in terms of computing time and solution quality. Finally, guidelines for possible efficient implementations, algorithm source code, and a library of reusable components are open-sourced to allow reproduction of our results and promote further investigations. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF