Vehicle routing with stochastic time-dependent travel times

Assigning and scheduling vehicle routes in a stochastic time-dependent environment is a crucial management problem. The assumption that in a real-life environment everything goes according to an a priori determined static schedule is unrealistic. Our methodology builds on earlier work in which the traffic congestion is captured based on queueing theory in an analytical way and applied to the VRP problem. In this paper, we introduce the variability in the traffic flows into the model. This allows for an evaluation of the routes based on the uncertainty involved. Different experiments show that the risk taking/avoiding behaviour of the planner can be taken into account during optimization. As more weight is contributed to the variability component, the resulting optimal route will be slightly slower, but more reliable. The solution quality in terms of the 95th-percentile of the travel time distribution (assumed lognormal) will also improve.