Approximate solutions for the capacitated arc routing problem

W.l. Pearn*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

60 Scopus citations


The capacitated arc routing problem (CARP), is a capacitated variation of the arc routing problems in which there is a capacity constraint associated with each vehicle. Due to the computational complexity of the problem, recent research has focussed on developing and testing heuristic algorithms which solve the CARP approximately. In this paper, we review some of the existing solution procedures, analyze their complexity, and present two modifications of the existing methods to obtain near-optimal solutions for the CARP. Extensive computational results are presented and analyzed.

Original languageEnglish
Pages (from-to)589-600
Number of pages12
JournalComputers and Operations Research
Issue number6
StatePublished - 1 Jan 1989

Fingerprint Dive into the research topics of 'Approximate solutions for the capacitated arc routing problem'. Together they form a unique fingerprint.

Cite this