Vehicle scheduling with sliding time windows

In this paper the authors introduce a heuristic approach for the vehicle scheduling problem with sliding time windows. In the problem with time windows, they take advantage of the fact that the starting time of each task must fall within a given time interval (i.e., a time window) rather than being fixed. Here, another level of flexibility is added by allowing the time windows of subsets of tasks to slide. The approach consists of identifying pairs of tasks offering good opportunity costs for reducing the overall cost, and finding ways of modifying the starting times to allow them to be linked. The technique is first developed for the problem with time windows and then extended to the case with sliding windows. Numerical results are reported to indicate the efficiency of the approach.