Districting for arc routing

Alexander Butsch*, Jörg Kalcsics, Gilbert Laporte

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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
Early online date27 Jun 2014
Publication statusPublished - 1 Sept 2014

Keywords / Materials (for Non-textual outputs)

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


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

Cite this