Solving Arc Routing Problems Using the Lin-Kernighan-Helsgaun Algorithm

Research output: Book/ReportReportResearch

Abstract

It is well known that many arc routing problems can be transformed into the Equality Generalized Traveling Salesman Problem (E-GTSP), which in turn can be transformed into a standard Asymmetric Traveling Salesman Problem (TSP). This opens up the possibility of solving arc routing problems using existing solvers for TSP. This paper evaluates the performance of the state-of-the art TSP solver Lin-Kernighan-Helsgaun (LKH) on a broad class of transformed arc routing instances. It is shown that LKH makes it possible to find solutions of good quality to large-scale undirected, mixed, and windy postman and general routing problem instances.
LanguageEnglish
Place of PublicationRoskilde
PublisherRoskilde Universitet
Number of pages6
Publication statusPublished - 15 Jan 2015

Cite this

@book{b1a7f1d9f60a42018bc98c4eed5ce24a,
title = "Solving Arc Routing Problems Using the Lin-Kernighan-Helsgaun Algorithm",
abstract = "It is well known that many arc routing problems can be transformed into the Equality Generalized Traveling Salesman Problem (E-GTSP), which in turn can be transformed into a standard Asymmetric Traveling Salesman Problem (TSP). This opens up the possibility of solving arc routing problems using existing solvers for TSP. This paper evaluates the performance of the state-of-the art TSP solver Lin-Kernighan-Helsgaun (LKH) on a broad class of transformed arc routing instances. It is shown that LKH makes it possible to find solutions of good quality to large-scale undirected, mixed, and windy postman and general routing problem instances.",
author = "Keld Helsgaun",
year = "2015",
month = "1",
day = "15",
language = "English",
publisher = "Roskilde Universitet",

}

Solving Arc Routing Problems Using the Lin-Kernighan-Helsgaun Algorithm. / Helsgaun, Keld.

Roskilde : Roskilde Universitet, 2015. 6 p.

Research output: Book/ReportReportResearch

TY - RPRT

T1 - Solving Arc Routing Problems Using the Lin-Kernighan-Helsgaun Algorithm

AU - Helsgaun, Keld

PY - 2015/1/15

Y1 - 2015/1/15

N2 - It is well known that many arc routing problems can be transformed into the Equality Generalized Traveling Salesman Problem (E-GTSP), which in turn can be transformed into a standard Asymmetric Traveling Salesman Problem (TSP). This opens up the possibility of solving arc routing problems using existing solvers for TSP. This paper evaluates the performance of the state-of-the art TSP solver Lin-Kernighan-Helsgaun (LKH) on a broad class of transformed arc routing instances. It is shown that LKH makes it possible to find solutions of good quality to large-scale undirected, mixed, and windy postman and general routing problem instances.

AB - It is well known that many arc routing problems can be transformed into the Equality Generalized Traveling Salesman Problem (E-GTSP), which in turn can be transformed into a standard Asymmetric Traveling Salesman Problem (TSP). This opens up the possibility of solving arc routing problems using existing solvers for TSP. This paper evaluates the performance of the state-of-the art TSP solver Lin-Kernighan-Helsgaun (LKH) on a broad class of transformed arc routing instances. It is shown that LKH makes it possible to find solutions of good quality to large-scale undirected, mixed, and windy postman and general routing problem instances.

M3 - Report

BT - Solving Arc Routing Problems Using the Lin-Kernighan-Helsgaun Algorithm

PB - Roskilde Universitet

CY - Roskilde

ER -