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.
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
StatePublished - 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 -