Title
Problem size reduction methods for large CVRPs
Author
David I. Müller
Institute for Theoretical Physics, TU Wien
Abstract
We solve the Capacitated Vehicle Routing Problem (CVRP) by introducing a novel approach to problem size reduction. We propose the generation of short sequences of nodes called “sections”, which effectively act as single nodes in a reduced CVRP that is faster and easier to solve. Three section generation methods are compared, and the trade-off between solution quality and computation time savings is evaluated. We show that reduced problem sizes of up to around 60 percent of the original problem size, result in only modest decreases in solution quality, but allow for significant reductions of computation time, regardless of the optimization algorithm used. Our findings highlight the potential benefits of problem aggregation and size reduction for large-scale CVRPs and suggest opportunities for further improving aggregation methods.
Keywords
Vehicle routingHeuristicsDecomposition methods
Object type
Language
English [eng]
Persistent identifier
https://phaidra.univie.ac.at/o:2091600
Appeared in
Title
Computers & Operations Research
Volume
172
ISSN
0305-0548
Issued
2024
Publisher
Elsevier BV
Date issued
2024
Access rights
Rights statement
© 2024 The Author(s)

Download

University of Vienna | Universitätsring 1 | 1010 Vienna | T +43-1-4277-0