Extending the Lin-Kernighan algorithm to improve solutions to VRPs with Time Windows

Helsgaun’s implementation of the Lin-Kernighan algorithm (LKH) is an effective heuristic solver for the Traveling Salesman Problem (TSP). The report presents an extension of LKH to support time windows, i.e., to a solver for the TSPTW. The new solver is referred to as LKHTW. SINTEF’s solver for rich Vehicle Routing Problems, Spider, has been integrated with LKHTW. Several alternative methods for combining Spider’s VRP heuristics with optimization of each tour using LKHTW have been developed and investigated empirically on a set of test instances. The results show that small but significant improvements of the Spider solutions can be obtained in cases with few or very wide time windows, whereas only few and marginal improvements are obtained in cases with narrower time windows.

Oppdragsgiver: SINTEF ICT