Vehicle scheduling problems with time-varying speed

The vehicle scheduling problem with time-varying speed (VSPTS) is a generalization of the vehicle scheduling problem in which the travel speed between two locations depends on the passing areas and time of day. We propose a simple model for estimating time-varying travel speeds in the VSPTS that relieves much burden for the data-related problems. We present three heuristics for the VSPTS, developed by extending and modifying existing heuristics for conventional vehicle scheduling problems. The results of computational experiments demonstrate that the proposed estimation model performs well and the saving method is the best among the three heuristics.