On-line vehicle routing and scheduling with time-varying travel speeds

This article considers the application of an on-line vehicle scheduling system to road networks where travel speeds vary over time. In such conditions, the volume of path calculations needed to maintain a consistent view of vehicle deployments may be much greater than when travel speeds are invariant. The article investigates the contexts in which time-dependent estimates of travel duration are required and presents approximate methods based on the idea of reducing the number of path calculations carried out. Simulation tests show that two of the proposed approximations are robust and effective in terms of computational performance.