Eulerian location problems

The problem of locating a set of depots in an arc routing context (with no side constraints) is addressed. In the case of one depot, it is shown that the problem can be transformed into a Rural Postman Problem (RPP). In the case of a set of depots, the problem is also reduced to an RPP if there are no bounds on the number of depots to be opened or to a RPP relaxation otherwise. The problem is then solved to optimality using a branch-and-cut algorithm. Extensive computational results on real-world and on some randomly generated test networks are reported.