Arc Routing is the process of selecting the best path in a network based on the route. Contrary to normal routing problems, which usually involve mapping a route between nodes, arc routing focuses more heavily on the route itself. The goal of many arc routing problems is to produce a route with the minimum amount of dead mileage, while also fully encompassing the edges required. Examples of arc routing applications include garbage collection, road gritting, mail delivery, network maintenance, and snowploughing.
Contents
Problem types
Arc routing problems (ARPs) differ in their goal and heuristics. However, all of them are known to be NP-hard.
Undirected rural postman problem
This problem is named after the postman and his challenge to deliver mail in any order he may choose, but minimizing his costs such as time or travel distance. It is also sometimes called the undirected chinese postman problem. The undirected rural postman problem (URPP) aims to minimize the total cost of a route that maps the entire network, or in more specific cases, a route that maps every edge that requires a service. If the whole network must be mapped, the route that maps the entire network is called a covering tour. In the case where only certain edges need to be mapped, the problem aims to solve the route that optimizes the demands, crossing over into non-required routes a minimal number of times.
Undirected capacitated arc routing problem
The undirected capacitated arc routing problem consists of demands placed on the edges, and each edge must meet the demand. An example is garbage collection, where each route might require both a garbage collection and a recyclable collection. Problems in real life applications might arise if there are timing issues, such as the case in which certain routes cannot be serviced due to timing or scheduling conflicts, or constraints, such as a limited period of time. The heuristics described in this article ignore any such problems that arise due to application constraints.
History
The URPP was first introduced in 1974 and was proven to be an NP-hard problem by Lenstra and Kan. The UCARP can be derived from the URPP, and thus is NP-hard as well. In 1981, another pair of computer scientists, Golden and Wong, managed to prove that even deriving a .5 approximation to the URPP was NP-hard. In 2000, Dror published a book describing different arc routing problems.
Heuristics and algorithms
Most algorithms require a pre-processing of the graph, which simplifies the initial graph by removing all edges that are not in the shortest path between 2 required edges. Another simplification that the pre-processing adds is that it transforms the shortest path between 2 required edges into a single, non-required edge, regardless of the number of edges in the path, provided that there were no required edges in the path.
Once the pre-processing is done, the problem can be generalized into a convex hull problem, with the edges being the points of the hull. The convex hull problem can be solved through linear programming or through convex hull algorithms, but the process of finding the convex hull is an exponential problem.
Methods of solving the URPP after the pre-processing is done consist of the cutting plane algorithm and the branch & cut methodology.