Paper published: Approximate Arc Routing

One sentence summary: We show how to find approximate solutions for arc routing problems using approximation algorithms for the traveling salesman problem.

A very general problem in arc routing is the Capacitated Arc Routing Problem, where we want to route a fleet of vehicles in an in total shortest possible way so to service a given number of streets in a road network. Each vehicle has a certain capacity to service streets. A successful way to find approximate solutions is to first find a “giant tour” and then divide it suitably into tours for each vehicle.

A nontrivial contribution in this paper is that the giant-tour approach also works for the problem variant with one-way and two-way streets and where the time to traverse a road depends on the direction (windy). We show this using an interesting charging argument. The main difficulty to find a giant tour is in which order to traverse “connected components” of streets - this is where the traveling salesman comes in.

In the practical part of the paper we also exploit several degrees of freedom that we have in finding and subdividing the giant tour to optimize the resulting tour set in practice. In this way the implementation became competitive with known heuristics.

Our paper is available (orig, arXiv, source code).