Solving a Bi-Objective Rich Vehicle Routing Problem with Customer Prioritization

Tim van Benthem, Mark Bergman, Martijn Mes

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
23 Downloads (Pure)


This paper considers a rich vehicle routing problem in which a combination of transportation costs and customer perceived waiting times should be minimized and a differentiation is made between priority and non-priority customers. We illustrate the problem using a case study of a wholesaler with its own last-mile delivery network where customers can have pickup and delivery demand and are served by a heterogeneous fleet of vehicles. We propose a bi-objective mathematical problem formulation, minimizing the combination of transportation costs and customer dissatisfaction. We model customer dissatisfaction using a non-linear function that approximates the perceived waiting time of the customers. To be able to solve realistically sized problems in reasonable time, we propose a Simulated Annealing heuristic, Variable Neighborhood Search, and a combination of these. We perform various experiments considering different customer preferences (visit as soon as possible or at a specific time) and problem settings. For the combined objective, we see an average costs reduction for the dissatisfaction function approach compared to the standard time window approach of 48% over all experiments. Furthermore, we observe an average reduction in perceived waiting time of 48% and 20% for priority and non-priority customers, respectively.
Original languageEnglish
Title of host publicationComputational Logistics
Subtitle of host publication11th International Conference, ICCL 2020, Enschede, The Netherlands, September 28–30, 2020, Proceedings
EditorsEduardo Lalla-Ruiz, Martijn Mes, Stefan Voß
Number of pages17
ISBN (Electronic)978-3-030-59747-4
ISBN (Print)978-3-030-59746-7
Publication statusPublished - 22 Sept 2020
Event11th International Conference on Computational Logistics, ICCL 2020 - Online conference, Enschede, Netherlands
Duration: 28 Sept 202030 Sept 2020
Conference number: 11

Publication series

NameLecture notes in computer science


Conference11th International Conference on Computational Logistics, ICCL 2020
Abbreviated titleICCL
Internet address


  • 22/3 OA procedure


Dive into the research topics of 'Solving a Bi-Objective Rich Vehicle Routing Problem with Customer Prioritization'. Together they form a unique fingerprint.

Cite this