Extending the Lin-Kernighan algorithm to improve solutions to VRPs with Time Windows
Research report
Permanent lenke
http://hdl.handle.net/11250/2380706Utgivelsesdato
2009Metadata
Vis full innførselSamlinger
- Publikasjoner fra CRIStin - SINTEF AS [5583]
- SINTEF Digital [2379]
Originalversjon
SINTEF Rapport A13822, 12 p. SINTEF, 2009Sammendrag
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.
Beskrivelse
-