Selecting a dynamic and stochastic path method for vehicle routing and scheduling problems

This paper investigates vehicle routing and scheduling which includes dynamic and stochastic elements of travel time on links. In order to consider the characteristics of travel time, three shortest path models were used. In the first model, the path is based on average travel time determined using Dijkstra's method (1959). The second model is the adaptive least-expected time path model developed by Miller-Hooks (2001), and the third one is the expected shortest path presented by Fu and Rilett (1998). Vehicle routes and schedules were calculated based on link costs by the three shortest path models. Deliveries using the vehicle routes and schedules were simulated and total costs of deliveries were compared. On a test road network, the dynamic and stochastic shortest paths showed good performance in delivery simulations. However, in the road network of the central area of Osaka, average costs in delivery simulations are at the same level for all the shortest path models considered. Therefore, it can be said that the performance of vehicle routing and scheduling in delivery simulations is influenced by characteristics of travel time information, and it is observed that low-cost and stable vehicle routing and scheduling are obtained using dynamic and stochastic shortest path models.