Distance approximation to support customer selection in vehicle routing problems

Fabian Akkerman () and Martijn Mes ()
Additional contact information
Fabian Akkerman: University of Twente
Martijn Mes: University of Twente

Annals of Operations Research, 2025, vol. 350, issue 1, No 10, 269-297

Abstract: Abstract Estimating the solution value of transportation problems can be useful to assign customers to days for multi-period vehicle routing problems, or to make customer selection decisions very fast (e.g., within an online environment). In this paper, we apply several regression methods to predict the total distance of the traveling salesman problem (TSP) and vehicle routing problem (VRP). We show that distance can be estimated fairly accurate using simple regression models and only a limited number of features. Besides using features found in the scientific literature, we also introduce new classes of spatial features. The model is validated on a fictional case with different spatial instances considering both a backordering and lost sales configuration, and on a realistic case that involves dynamic waste collection in the city of Amsterdam, The Netherlands. For the fictional case, we show differences in performance per instance type and configuration, and we show that our model can save up to $$25.3\%$$ 25.3 % in distance compared with a heuristic approximation. For the waste collection case, we introduce a cost function that combines the travel distance and service level, and show that our model can reduce distances up to 17% compared to a well-known heuristic approximation while maintaining the same service level. Furthermore, we show the benefits of using approximations for combining offline learning with online or frequent optimization.

Keywords: Distance approximation; Traveling salesman; Vehicle routing; Customer selection; Inventory routing; Waste collection (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-022-04674-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:annopr:v:350:y:2025:i:1:d:10.1007_s10479-022-04674-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-022-04674-8

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().