Vehicle Routing Problem with Wind and Load dependent Travel Times (VRPWLTT)

Abstract

With increased e-commerce, the planning of last mile delivery has gained importance over the years. In light of dense urban areas and sustainability concerns, electric cargo bikes are well fit for this task. Due to constraints on the power output of the electro motor, the travel times are dependent, amongst others, on the load and the wind. In this thesis, a method is developed to compute optimal schedules for the stochastic vehicle routing problem (SVRP) for such cargo bikes. This is done using a combination of simulated annealing and a set cover formulation. The uncertainty in the weather forecast propagates into uncertainty in the travel times. The travel times are considered to be stochastic and strongly correlated. It is therefore non trivial to determine the arrival time distribution for each customer. In this thesis, the arrival time distribution is approximated using the non parametric technique of kernel density estimation (KDE). This technique can produce very robust schedules with only 5 or 20 samples. Average service levels of outputted schedules are often within one thousandth of a perfect score. With more samples, run time increases, without much benefit to average costs. Using the forecast wind as a deterministic given proved to be about as bad as ignoring the wind for the selected distribution of wind. Simply tightening the instance by shortening the time windows produces schedules with high service level and also high costs. Cheapest schedules are found approximating the arrival time distribution with only one sample that is exactly the weather forecast.