A vehicle routing problem with multiple service agreements

Vincent C.G. Karels*, Walter Rei, Lucas P. Veelenturf, Tom Van Woensel

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)


We consider a logistics service provider which arranges transportation services to customers with different service agreements. The most prominent feature of this service agreement is the time period in which these customers send their orders and want to retrieve delivery information. After customers place their orders, they require information about the driver and an early indication of the arrival times. At the moment, this information needs to be provided. The order information of other customers with a different service agreement that needs to be serviced in the same period might still be unknown. Ultimately all customers have to be planned, constrained by the information provided to the customers in the earlier stage. In this paper, we investigate how the logistic service provider plans its routes and communicates the driver and arrival time information in the phase where not all customers are known (stage 1). Once all customer orders are known (stage 2), the final routes can be determined, which adhere to the already communicated driver and arrival time information from stage 1, minimizing total routing cost. For this problem, an exact algorithm is presented. This problem is solved using a novel tractable branch-and-bound method and re-optimization in stage 2. Detailed results are presented, showing the improvements of using re-optimization. We show that integrating the planning of the customers with the different service agreements leads to significant cost savings compared to treating the customers separately (as is currently done by most logistics service providers).

Original languageEnglish
Pages (from-to)129-145
Number of pages17
JournalEuropean Journal of Operational Research
Issue number1
Publication statusPublished - 16 Feb 2024

Bibliographical note

Funding Information:
The funding for this research was provided by NWO, the Dutch Science Foundation, for the project DATAS for Cities (No. 438-15-507).

Publisher Copyright:
© 2023 The Authors


Dive into the research topics of 'A vehicle routing problem with multiple service agreements'. Together they form a unique fingerprint.

Cite this