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 STD VRP, 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 STD VRP 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.
展开▼
