Distance approximation to support customer selection in vehicle routing problems

Fabian Akkerman*, Martijn Mes

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)
212 Downloads (Pure)


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 % 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.

Original languageEnglish
JournalAnnals of operations research
Early online date7 Apr 2022
Publication statusE-pub ahead of print/First online - 7 Apr 2022


  • Customer selection
  • Distance approximation
  • Inventory routing
  • Traveling salesman
  • Vehicle routing
  • Waste collection
  • UT-Hybrid-D


Dive into the research topics of 'Distance approximation to support customer selection in vehicle routing problems'. Together they form a unique fingerprint.

Cite this