A global repair operator for capacitated arc routing problem

Yi MEI, Ke TANG, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

51 Citations (Scopus)

Abstract

Capacitated arc routing problem (CARP) has attracted much attention during the last few years due to its wide applications in real life. Since CARP is NP-hard and exact methods are only applicable for small instances, heuristics and metaheuristic methods are widely adopted when solving CARP. This paper demonstrates one major disadvantage encountered by traditional search algorithms and proposes a novel operator named global repair operator (GRO) to address it. We further embed GRO in a recently proposed tabu search algorithm (TSA) and apply the resultant repair-based tabu search (RTS) algorithm to five well-known benchmark test sets. Empirical results suggest that RTS not only outperforms TSA in terms of quality of solutions but also converges to the solutions faster. Moreover, RTS is also competitive with a number of state-of-the-art approaches for CARP. The efficacy of GRO is thereby justified. More importantly, since GRO is not specifically designed for the referred TSA, it might be a potential tool for improving any existing method that adopts the same solution representation. © 2009 IEEE.
Original languageEnglish
Pages (from-to)723-734
Number of pages12
JournalIEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
Volume39
Issue number3
Early online date13 Feb 2009
DOIs
Publication statusPublished - Jun 2009
Externally publishedYes

Bibliographical note

This work was supported in part by the Fund for Foreign Scholars in University Research and Teaching Programs under Grant B07033 and in part by an Engineering and Physical Science Research Council (EPSRC) grant in U.K. under Grant EP/E058884/1. This paper was recommended by Associate Editor H. Takagi.

Keywords

  • Capacitated arc routing problem (CARP)
  • Global repair operator (GRO)
  • Heuristic search
  • Tabu search

Fingerprint

Dive into the research topics of 'A global repair operator for capacitated arc routing problem'. Together they form a unique fingerprint.

Cite this