The vehicle routing problem with stochastic demands (VRPSD) is a well studied variant of the classic (deterministic) capacitated vehicle routing problem (CVRP) where the customer demands are given by random variables. Two prominent approaches for solving the VRPSD model it either as a chance-constraint program (CC-VRPSD) or as a two-stage stochastic program (2S-VRPSD). In this paper, we also propose a third combined approach, where we minimize the same objective function as 2S-VRPSD, but over the feasible region of CC-VRPSD. While CC-VRPSD and 2S-VRPSD were extensively studied individually, not much has been investigated regarding the possible advantages/disadvantages of one method against the other. We try to address this gap and conduct theoretical and practical comparisons between these variants of the problem. First, we derive worst-case bounds and show that these bounds can be made arbitrarily close to being tight. We also show sufficient conditions under which chance-constraint feasible routes are feasible for the deterministic counterpart. Next, we implement exact algorithms for solving all the considered approaches and conduct extensive computational experiments to measure their performance. Our findings show that, while the two-stage approach might experience a high failure ratio, in comparison to optimal solutions for the chance-constraint method, the combined approach attains a small failure ratio as well as second-stage cost.
Article
View A comparison of different approaches for the vehicle routing problem with stochastic demands