Vehicle routing with stochastic time-dependent travel times

T. Van Woensel, C. Lecluyse, H. Peremans


The capability of taking into account time-dependent travel speeds is extremely valuable, not only because speed profiles do affect the objective function of the optimization, but also, the best solutions for the time-independent problem applied in a time-dependent context, are in general suboptimal (Van Woensel et al. [21]). Minimizing the expected travel time however still does not deal with the true stochastic nature of the travel times. As the real speed is a realization of a stochastic process, it is equally important to account for the variability of the speed and thus the travel time uncertainty when planning a route. This paper aims at obtaining a routing solution that performs well in the face of the extra complications due to congestion, which eventually leads to a better solution, i.e. more reliable routes in terms of travel time. These more realistic solutions have the potential to reduce real operating costs for a broad range of industries which face daily routing problems. When including the variance of the travel time, the potential applications are vast: it gives a manager a powerful tool to incorporate and take into account congestion uncertainty in his optimization. The higher the risk averseness of the planner, the more weight is allowed to that factor while optimizing, as such making the resulting routes more reliable and predictable. Although the gain in terms of less variability will be offset by a higher average travel time, the travel time associated with 95th - percentile will improve. Results and simulation results confirm these conclusions. Depending on the road and environmental conditions, this improvement will be more or less substantial. Due to the analytical approach to congestion, the developed approach can be extended to VRP with time windows. Hence, combined with the risk profile discussed above, the manager has a powerful tool not only for planning and scheduling his vehicle fleet, but on top of that he will be able to use the model for adequately determining costs and setting his rates at the individual customer level (e.g. someone with a tight and hard time window will need to pay more than a customer which is highly flexible in his requirements). The approach also opens doors for real life simulations.


« Terug