In this paper we consider a version of the capacitated vehicle routing problem (CVRP) where travel times are assumed to be uncertain and statistically correlated (CVRP-SCT). In particular we suppose that travel times follow a multivariate probability distribution whose first and second moments are known. The main purpose of the CVRP-CST is to plan vehicle routes whose travel times are reliable, in the sense that observed travel times are not excessively dispersed with respect to their expected value. To this scope we adopt a mean-variance approach, where routes with high travel time variability are penalized. This leads to a parametric binary quadratic program for which we propose two alternative set partitioning reformulations and show how to exploit certain special structure in the correlation matrix when there is correlation only between adjacent links. For each model, we develop an exact branch-price-and-cut algorithm, where the quadratic component is dealt with either in the column generation master problem or in its subproblem. We tested our algorithms on a rich collection of instances derived from well-known datasets. Computational results show that our algorithms can efficiently solve problem instances with up to 75 customers. Furthermore, the obtained solutions significantly reduce the time variability when compared with standard CVRP solutions.
Published December 2017 , 42 pages
G17109.pdf (600 KB)