The rural postman problem on mixed graphs with turn penalties

In this paper we deal with a problem which generalizes the Rural Postman Problem defined on a mixed graph (MRPP). The generalization consists of associating a non-negative penalty to every turn as well as considering the existence of forbidden turns. This new problem fits real-world situations more closely than other simpler problems. A solution tour must traverse all the requiring service arcs and edges of the graph while not making forbidden turns. Its total cost will be the sum of the costs of the traversed arcs and edges together with the penalties associated with the turns done. The Mixed Rural Postman Problem with Turn Penalties (MRPPTP) consists of finding such a tour with a total minimum cost. We show that the new problem is NP-hard, even in some particular cases. In order to solve the MRPPTP, a polynomial transformation of the problem into the Asymmetric Traveling Salesman Problem (ATSP) can be done and we then apply heuristics and exact methods for the ATSP. This transformation is summarized here and a specific heuristic algorithm, based on two recent heuristics for the MRPP, is also presented. Extensive computational experiments with more than 250 instances establish the effectiveness of our procedures.