### Abstract

Language | English |
---|

Place of Publication | Roskilde |
---|---|

Publisher | Roskilde Universitet |

Number of pages | 6 |

State | Published - 15 Jan 2015 |

### Cite this

*Solving Arc Routing Problems Using the Lin-Kernighan-Helsgaun Algorithm*. Roskilde: Roskilde Universitet.

}

*Solving Arc Routing Problems Using the Lin-Kernighan-Helsgaun Algorithm*. Roskilde Universitet, Roskilde.

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

Research output: Book/Report › Report

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 -