Vehicle Routing Problem in Stochastic Time-Dependent Networks with Time Window Constraint

This paper addresses the vehicle routing problem (VRP) in stochastic and time-dependent (STD) networks with hard time window constraint. As the sub-problem of STDVRP, the STD optimal path between two customer nodes is obtained through robust approach, which minimizes the worst-case travel time over all the candidate paths without requiring the probability distributions of link travel times. With the sub-problem solved, the proposed STDVRP model can be converted into a normal time-dependent (TD) vehicle routing problem and a route construction algorithm is applied to solving the simplified problem in the extended Solomon instances as efficiently as TDVRP. The computational results show that the proposed STDVRPTW model can improve the level of customers’ service by guarantee the time-window constraint satisfied and only lead to a little increase in cost, which is especially apparent in the problems where the customers’ time windows are narrow.