Districting for arc routing

Alexander Butsch, Jörg Kalcsics, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

40 Citations (SciVal)


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.

Original languageEnglish
Pages (from-to)809-824
Number of pages16
JournalINFORMS Journal on Computing
Issue number4
Publication statusPublished - 1 Sept 2014


  • Adaptive large neighborhood search
  • Arc routing
  • Districting
  • Multicriteria
  • Tabu search

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Districting for arc routing'. Together they form a unique fingerprint.

Cite this