A Greedy Look-ahead Heuristic for Combinatorial Optimization: An Application to Vehicle Scheduling with Time Windows

This paper describes a greedy heuristic for a class of combinatorial optimization problems; a central feature of the method being a look-ahead capability. The power of the heuristic is demonstrated through experimentation using a large, real-life vehicle scheduling problem with tight time-window constraints. Incorporation of the look-ahead feature gave an improvement in performance that was at least as great as, and in addition to, that which had been obtained through use of the well-known ‘savings’ method. Based upon the experimental results, some guidelines are proposed for the application of the heuristic to other problems. One of the conclusions is that designers of heuristics should give greater consideration to the inclusion of a look-ahead element in their algorithms.