On-time delivery probabilistic models for the vehicle routing problem with stochastic demands and time windows

Increasing attention is given to on-time delivery of goods in the distribution and logistics industry. Due to uncertainties in customer demands, on-time deliveries cannot be ensured frequently. The vehicle capacity may be exceeded along the planned delivery route, and then the vehicle has to return to the depot for reloading of the goods. In this paper, such on-time delivery issues are formulated as a vehicle routing problem with stochastic demands and time windows. Three probabilistic models are proposed to address on-time delivery from different perspectives. The first one aims to search delivery routes with minimum expected total cost. The second one is to maximize the sum of the on-time delivery probabilities to customers. The third one seeks to minimize the expected total cost, while ensuring a given on-time delivery probability to each customer. Having noted that solutions of the proposed models are affected by the recourse policy deployed in cases of route failures, a preventive restocking policy is examined and compared with a detour-to-depot recourse policy. A numerical example indicates that the preventive restocking policy can help obtain better solutions to the proposed models and its effectiveness depends on the solution structure. It is also shown that the third model can be used to determine the minimum number of vehicles required to satisfy customers' on-time delivery requirements.