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

Research output: Book/ReportReportResearch


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.
Original languageEnglish
Place of PublicationRoskilde
PublisherRoskilde Universitet
Number of pages6
Publication statusPublished - 15 Jan 2015

Cite this