The probabilistic vehicle routing problem with service guarantees

We develop a two-phase approach to solving the capacitated routing problem (CVRP) with stochastic demand. A nonlinear chance-constrained optimization model is solved to determine delivery quantities, and a tabu search metaheuristic is used to determine vehicle routes. The goal of this research is to assure that a logistics company would satisfy the demands of customers with a high probability, while minimizing the overall transportation cost. We introduce the concept of premium customers, who are guaranteed a higher level of service. We show that our chance-constrained method has some strategic advantages over the CVRP with recourse approach. We examine the possibility of the logistics company charging customers selectively with an additional service fee to assure a high level of service. Moreover, we provide managerial insight on when the best time is to pay for the premium membership. We present computational results on commonly studied small to large-scale CVRP instances. A simulation study is conducted to explore the performance of the proposed chance-constrained approach using the CVRP with recourse. We conclude that our chance-constrained CVRP model could serve a logistics company well when resource costs and service guarantees are of concern.