Using column generation for the Time Dependent Vehicle Routing Problem with Soft Time Windows and Stochastic Travel Times
Summary
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.