Using column generation for the Time Dependent Vehicle Routing Problem with Soft Time Windows and Stochastic Travel Times

Abstract

The vehicle Routing Problem with Time Windows and time dependent stochastic travel times (TDVRPTW) is extended by using continuous distribution functions to model variation in travel times directly into the objective function. The used model is flexible by allowing different travel time distributions for different periods of the day to allow the modeling of realistic situations with often changing levels of traffic congestion. In this thesis the cases where the travel times are either normally distributed or gamma distributed are covered, although the techniques can be applied to other distributions as well. Using this model the objective function can accurately predict the cost of a route, taking into account both the travel costs (traveling and vehicle cost) as well as the service costs (probability of being late or a driver suffering overtime). To meet minimum service level requirements we maintain a minimum feasibility of serving each customer on time. The model allows an early decision to not further explore routes that already are infeasible due to not meeting a threshold probability of serving some customers on their route within their time window. The problem is solved using column generation to solve a linear programming problem consisting of selecting a sub set of routes out of a set of selected high quality candidate routes. Candidate routes are selected using two different heuristics to solve the pricing problem, local search and dynamic programming.