Summary: We describe a heuristic solution method for the Vehicle Routing Problem with Time Windows (VRPTW). The method uses four improvement operators in a steepest descent search strategy. The guided local search meta-heuristic is used to avoid local minima. The resulting algorithm is tested on Solomon’s capacitated vehicle routing problems with time windows. We compare our results to the best heuristic approaches reported for the VRPTW. The new method performs significantly better than previous methods on classes where vehicle routes tend to be longer. The method is slightly worse on classes with shorter routes. We report 12 new best solutions for Solomon’s problems.
For the entire collection see [Zbl 0930.00082].