Districting for arc routing

Alexander Butsch*, Jörg Kalcsics, Gilbert Laporte

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume26
Issue number4
Early online date27 Jun 2014
DOIs
Publication statusPublished - 1 Sep 2014

Keywords

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

Fingerprint

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

Cite this