Districting for Arc Routing

This paper proposes a heuristic for districting problems arising in an arc routing context. The aim is to design districts by amalgamating edges of a graph as opposed to cells. Solutions must satisfy two hard criteria (complete and exclusive assignment as well as connectedness) and several soft criteria (balance, small deadheading, local compactness, and global compactness). The latter criteria are amalgamated into a weighted objective. The proposed heuristic applies a construction procedure followed by a tabu search improvement phase in which several subroutines are defined and selected according to a roulette wheel mechanism, as in adaptive large neighborhood search. Extensive tests conducted on instances derived from real-world street data confirm the efficiency of the proposed methodology.