The Twin Rural Postman Problem

This paper presents a new combinatorial optimization problem within the class of arc routing problems, referred to as the Twin Rural Postman Problem. In this problem, a mixed and strongly connected graph composed of a set of required and positive weighted links must be fully covered by two servers with minimum total distance. One server covers a subset of required links in a tour that departs and ends from a garage, forming a rural postman tour. Meanwhile, the other server covers the remaining required links in a min-max open rural postman tour. Here we present the problem and its multi-objective set-partitioning formulation. We also discuss different forms and extensions of the problem, and we provide a solution methodology and its application with results to the domiciliary waste collection for the city of Andradina/SP.