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.
| Place of Publication | Roskilde |
|---|
| Publisher | Roskilde Universitet |
|---|
| Number of pages | 6 |
|---|
| Publication status | Published - 15 Jan 2015 |
|---|
Cite this
-
APA
-
Author
-
BIBTEX
-
Harvard
-
Standard
-
RIS
-
Vancouver
@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 = jan
day = "15",
language = "English",
publisher = "Roskilde Universitet",
}
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 -