The directed profitable location Rural Postman Problem

In this paper we introduce an extension of the well known Rural Postman Problem, which combines arc routing with profits and facility location. Profitable arcs must be selected, facilities located at both end-points of the selected arcs, and a tour identified so as to maximize the difference between the profit collected along the arcs and the cost of traversing the arcs and installing the facilities. We analyze properties of the problem, present a mathematical programming formulation and a branch-and-cut algorithm. In an extensive computational experience the algorithm could solve instances with up to 140 vertices and 190 arcs and up to 50 vertices and 203 arcs.