TY - JOUR

T1 - A vehicle routing problem with distribution uncertainty in deadlines

AU - Zhang, Dali

AU - Li, Dong

AU - Sun, Hailin

AU - Hou, Liwen

PY - 2021/7/1

Y1 - 2021/7/1

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

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

KW - Conditional Value-at-Risk

KW - Distributionally robust optimisation

KW - Sample approximation

KW - Stochastic vehicle routing problem

U2 - 10.1016/j.ejor.2020.10.026

DO - 10.1016/j.ejor.2020.10.026

M3 - Journal article

VL - 292

SP - 311

EP - 326

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -