To main content

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

Abstract

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

Category

Report

Client

  • SINTEF AS / 90A34901

Language

English

Author(s)

Affiliation

  • SINTEF Digital / Mathematics and Cybernetics

Year

2009

Publisher

SINTEF

Issue

A13822

ISBN

9788214044591

View this publication at Cristin