Home > Research > Publications & Outputs > A vehicle routing problem with distribution unc...


Text available via DOI:

View graph of relations

A vehicle routing problem with distribution uncertainty in deadlines

Research output: Contribution to Journal/MagazineJournal articlepeer-review

  • Dali Zhang
  • Dong Li
  • Hailin Sun
  • Liwen Hou
<mark>Journal publication date</mark>1/07/2021
<mark>Journal</mark>European Journal of Operational Research
Issue number1
Number of pages16
Pages (from-to)311-326
Publication StatusPublished
Early online date18/02/21
<mark>Original language</mark>English


This article considers a stochastic vehicle routing problem with probability constraints. The probability that customers are served before their (uncertain) deadlines must be higher than a pre-specified target. It is unrealistic to expect that the perfect knowledge on the probability distributions of deadlines is always available. To this end, we propose a distributionally robust optimisation framework to study worst bounds of the problem, which exploits the moment information of the historical observations. This framework includes two steps. We first use Conditional Value-at-Risk (CVaR) as a risk approximation to the probability of missing customer deadlines. The resulting nonlinear model is then transformed into a semi-infinite mixed integer program, using the dual form of the CVaR approximation. A sample approximation approach is then used to address the computational challenges. As the standard CVaR approximation to probability constraints is rather conservative, we suggest a relaxation to the approximation and develop an iterative algorithm to find the right value of the parameter that is introduced to the relaxed CVaR constraints. The extensive numerical experiments show that the routing policies developed by the proposed solution framework are robust and able to achieve the required target, regardless of deadline distributions.