This paper proposes a new dataset of Capacitated Vehicle Routing Problem instances, up to two orders of magnitude larger than those in the currently used benchmarks. Although these sizes might not have an immediate application to real -world logistic scenarios, we believe they could foster fresh new research efforts on the design of effective and efficient algorithmic components for routing problems. We provide computational results for such instances by running FILO2, an adaptation of the FILO algorithm proposed in Accorsi and Vigo (2021), designed to handle extremely large-scale CVRP instances. Solutions for such instances are obtained using a standard personal computer in a considerably short computing time, thus showing the effectiveness of the acceleration and pruning techniques already proposed in FILO. Finally, results of FILO2 on well-known literature instances show that the newly introduced changes improve the overall scalability of the approach with respect to the previous FILO design.
Accorsi L., Vigo D. (2024). Routing one million customers in a handful of minutes. COMPUTERS & OPERATIONS RESEARCH, 164, 1-10 [10.1016/j.cor.2024.106562].
Routing one million customers in a handful of minutes
Vigo D.Membro del Collaboration Group
2024
Abstract
This paper proposes a new dataset of Capacitated Vehicle Routing Problem instances, up to two orders of magnitude larger than those in the currently used benchmarks. Although these sizes might not have an immediate application to real -world logistic scenarios, we believe they could foster fresh new research efforts on the design of effective and efficient algorithmic components for routing problems. We provide computational results for such instances by running FILO2, an adaptation of the FILO algorithm proposed in Accorsi and Vigo (2021), designed to handle extremely large-scale CVRP instances. Solutions for such instances are obtained using a standard personal computer in a considerably short computing time, thus showing the effectiveness of the acceleration and pruning techniques already proposed in FILO. Finally, results of FILO2 on well-known literature instances show that the newly introduced changes improve the overall scalability of the approach with respect to the previous FILO design.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.