A Fast and Scalable Heuristic for the Solution of Large-Scale Capacitated Vehicle Routing Problems

Luca Accorsi () and Daniele Vigo ()
Additional contact information
Luca Accorsi: Department of Electrical, Electronic and Information Engineering “G. Marconi”, University of Bologna, Bologna 40136, Italy
Daniele Vigo: Department of Electrical, Electronic and Information Engineering “G. Marconi”, University of Bologna, Bologna 40136, Italy; Interdepartmental Center for Industrial Research on Information and Communication Technologies, University of Bologna, Cesena 47521, Italy

Transportation Science, 2021, vol. 55, issue 4, 832-856

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.

Keywords: Capacitated Vehicle Routing Problem; metaheuristics; acceleration techniques; large-scale instances (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2021.1059 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:55:y:2021:i:4:p:832-856

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().