Modelling intra-city time-dependent travel speeds for vehicle scheduling problems

Many research papers have presented mathematical models for vehicle scheduling. Several of these models have been embedded in commercial decision support systems for intra-city vehicle scheduling for laundries, grocery stores, banks, express mail customers, etc. Virtually all of these models ignore the important issue of time-dependent travel speeds for intra-city travel. Travel speeds (and times) in nearly all metropolitan areas change drastically during the day because of congestion in certain parts of the city road network. The assumption of constant (time-independent) travel speeds seriously affects the usefulness of these models. This is particularly true when time windows (earliest and latest stop time constraints) and other scheduling issues are important. This research proposes a parsimonious model for time-dependent travel speeds and several approaches for estimating the parameters for this model. An example is presented to illustrate the proposed modelling approach. The issue of developing algorithms to find near-optimal vehicle schedules with time-dependent travel speeds is also discussed. The modelling approach presented in this paper has been implemented in a commercial courier vehicle scheduling system and was judged to be ‘very useful’ by users in a number of different metropolitan areas in the United States.