Abstract
| Original language | English |
|---|
| Place of Publication | Roskilde |
|---|---|
| Publisher | Roskilde Universitet |
| Number of pages | 6 |
| Publication status | Published - 15 Jan 2015 |
Cite this
}
Solving Arc Routing Problems Using the Lin-Kernighan-Helsgaun Algorithm. / Helsgaun, Keld.
Roskilde : Roskilde Universitet, 2015. 6 p.Research output: Book/Report › Report › Research
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 -