An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems: Technical report

Research output: Book/ReportReportResearch

Abstract

This report describes the implementation of an extension of the Lin-Kernighan-Helsgaun TSP solver for solving constrained traveling salesman and vehicle routing problems. The extension, which is called LKH-3, is able to solve a variety of well-known problems, including the sequential ordering problem (SOP), the traveling repairman problem (TRP), variants of the multiple travel-ing salesman problem (mTSP), as well as vehicle routing problems (VRPs) with capacity, time windows, pickup-and-delivery and distance constraints. The implementation of LKH-3 builds on the idea of transforming the problems into standard symmetric traveling salesman problems and handling constraints by means of penalty functions. Extensive testing on benchmark instances from the literature has shown that LKH-3 is effective. Best known solutions are often obtained, and in some cases, new best solutions are found. The program is free of charge for academic and non-commercial use and can be downloaded in source code. A comprehensive library of bench-mark instances and the best obtained results for these instances can also be downloaded.
This report describes the implementation of an extension of the Lin-Kernighan-Helsgaun TSP solver for solving constrained traveling salesman and vehicle routing problems. The extension, which is called LKH-3, is able to solve a variety of well-known problems, including the sequential ordering problem (SOP), the traveling repairman problem (TRP), variants of the multiple travel-ing salesman problem (mTSP), as well as vehicle routing problems (VRPs) with capacity, time windows, pickup-and-delivery and distance constraints. The implementation of LKH-3 builds on the idea of transforming the problems into standard symmetric traveling salesman problems and handling constraints by means of penalty functions. Extensive testing on benchmark instances from the literature has shown that LKH-3 is effective. Best known solutions are often obtained, and in some cases, new best solutions are found. The program is free of charge for academic and non-commercial use and can be downloaded in source code. A comprehensive library of bench-mark instances and the best obtained results for these instances can also be downloaded.
LanguageEnglish
Place of PublicationRoskilde
PublisherRoskilde Universitet
Number of pages60
StatePublished - 29 Dec 2017

Cite this

@book{36b9628e7a874d208624584d8a470985,
title = "An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems: Technical report",
abstract = "This report describes the implementation of an extension of the Lin-Kernighan-Helsgaun TSP solver for solving constrained traveling salesman and vehicle routing problems. The extension, which is called LKH-3, is able to solve a variety of well-known problems, including the sequential ordering problem (SOP), the traveling repairman problem (TRP), variants of the multiple travel-ing salesman problem (mTSP), as well as vehicle routing problems (VRPs) with capacity, time windows, pickup-and-delivery and distance constraints. The implementation of LKH-3 builds on the idea of transforming the problems into standard symmetric traveling salesman problems and handling constraints by means of penalty functions. Extensive testing on benchmark instances from the literature has shown that LKH-3 is effective. Best known solutions are often obtained, and in some cases, new best solutions are found. The program is free of charge for academic and non-commercial use and can be downloaded in source code. A comprehensive library of bench-mark instances and the best obtained results for these instances can also be downloaded.",
author = "Keld Helsgaun",
year = "2017",
month = "12",
day = "29",
language = "English",
publisher = "Roskilde Universitet",

}

An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems : Technical report. / Helsgaun, Keld.

Roskilde : Roskilde Universitet, 2017. 60 p.

Research output: Book/ReportReportResearch

TY - RPRT

T1 - An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems

T2 - Technical report

AU - Helsgaun,Keld

PY - 2017/12/29

Y1 - 2017/12/29

N2 - This report describes the implementation of an extension of the Lin-Kernighan-Helsgaun TSP solver for solving constrained traveling salesman and vehicle routing problems. The extension, which is called LKH-3, is able to solve a variety of well-known problems, including the sequential ordering problem (SOP), the traveling repairman problem (TRP), variants of the multiple travel-ing salesman problem (mTSP), as well as vehicle routing problems (VRPs) with capacity, time windows, pickup-and-delivery and distance constraints. The implementation of LKH-3 builds on the idea of transforming the problems into standard symmetric traveling salesman problems and handling constraints by means of penalty functions. Extensive testing on benchmark instances from the literature has shown that LKH-3 is effective. Best known solutions are often obtained, and in some cases, new best solutions are found. The program is free of charge for academic and non-commercial use and can be downloaded in source code. A comprehensive library of bench-mark instances and the best obtained results for these instances can also be downloaded.

AB - This report describes the implementation of an extension of the Lin-Kernighan-Helsgaun TSP solver for solving constrained traveling salesman and vehicle routing problems. The extension, which is called LKH-3, is able to solve a variety of well-known problems, including the sequential ordering problem (SOP), the traveling repairman problem (TRP), variants of the multiple travel-ing salesman problem (mTSP), as well as vehicle routing problems (VRPs) with capacity, time windows, pickup-and-delivery and distance constraints. The implementation of LKH-3 builds on the idea of transforming the problems into standard symmetric traveling salesman problems and handling constraints by means of penalty functions. Extensive testing on benchmark instances from the literature has shown that LKH-3 is effective. Best known solutions are often obtained, and in some cases, new best solutions are found. The program is free of charge for academic and non-commercial use and can be downloaded in source code. A comprehensive library of bench-mark instances and the best obtained results for these instances can also be downloaded.

UR - http://www.akira.ruc.dk/~keld/research/LKH-3/

M3 - Report

BT - An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems

PB - Roskilde Universitet

CY - Roskilde

ER -