Bi-Objective Rich Vehicle Routing Problem with Customer Prioritization

Tim van Benthem, Mark Bergman, Martijn Mes

Research output: Working paper

139 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
PublisherUniversity of Twente
Number of pages15
Publication statusPublished - 23 May 2020


  • Vehicle routing problem
  • Customer satisfaction
  • Simulated annealing
  • Variable neighborhood search
  • Time windows


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

Cite this