Vehicle routing with time windows and stochastic demands: a case study

Abstract

Vehicle routing problems have already been widely studied in literature. However, the focus is mainly on deterministic problem variants where all input parameters are assumed to be known in advance (Oyola et al., 2018). Yet, different forms of uncertainty can be observed in real life, such as uncertainty in travel times, customers, service times and demand. Stochastic problems assume that only a probability distribution is known on these uncertain parameters. This study focuses on the VRP with time windows and stochastic demands. The problem under consideration is based on a real-life problem faced by a logistics service provider who provides personalized and integrated transport and logistics solutions across Europe. One of the problems the company is facing is that there are often deviations between the specified quantities by the customers and the actual quantities when arriving at the customer, which makes it difficult to make a reliable planning. Stochastic demands can result in inefficient use of vehicle capacity or capacity shortages, leading to costly corrective actions when executing planned collection routes. This study quantifies the importance of this problem. As common in literature, a two-stage stochastic programming with recourse method is applied to model the problem. This approach treats the problem in two stages. The focus is on the initial phase, where a first-stage solution is planned, based on planned routing costs and expected recourse costs for corrective actions. Decisions must be taken here based on stochastic information. However, route failures can occur when executing the planned routes and actual customer demands are revealed. These route failures can occur at different positions in a planned route, each with a certain probability of occurring. When a route failure occurs, a corrective action (recourse) can be taken in the second stage. Different recourse policies exist such as detour to depot, preventive restocking and re-optimization (Oyola et al., 2018). The detour to depot recourse policy is used in this study and is most used in literature (Erera et al., 2010). In this policy, the vehicle returns to the depot to (un)load when a failure occurs. Afterwards, it resumes its route as planned, restarting at the customer where the route failure occurred. This study extends the state of the art by including the effect of expected violations of time windows, maximum route duration and other time-related constraints into the recourse cost function. An iterated local search algorithm is presented to solve the problem. Moreover, different learning techniques are used and compared to estimate the probabilities of failure at every customer in a route from real-life historic data. Different widths of time windows are included in the experiments as well, since they have an effect on the construction of the routes and the recourse cost. Experimental results demonstrate that both operational costs and time window violations can be reduced by taking the expected cost of corrective actions into account when planning the routes. In some cases, different routes are constructed when the expected cost of corrective actions is not included initially in the planning compared to the first-stage planning. However, in general, this leads to higher recourse costs subsequently.