A New Arc-Routing Algorithm Applied to Winter Road Maintenance

This problem is well-known to be NPhard [3]. For our purposes, an edge version is important: Given a subset of edges (instead of vertices), find a connected subgraph of G containing all prescribed edges with the minimal weight. This edge version of Steiner tree problem makes our problem hard even if the limit L is sufficiently large to ensure that only one inert (or chemical) car can maintain all inert roads. In this case, the set of all inert roads may be disconnected so a set of chemical roads has to be added to the inert car's plan to ensure connectivity. Finding such a set of chemical roads with the minimal weight is exactly the edge version of the Steiner tree problem. This kind of reasoning is used in Section 5 to obtain lower bounds on a minimal deadhead.