Augment-insert algorithms for the capacitated arc routing problem

W.l. Pearn*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

54 Scopus citations


The capacitated arc routing problem (CARP) is a generalization of the rural postman problem (RPP), which has many real-world applications. Examples include routing of school buses, mail delivery vehicles, street sweepers and many others. The CARP has been shown to be NP-hard, and, therefore, heuristic procedures are desired to solve the CARP approximately. In this paper, we introduce two new algorithms to solve the CARP near-optimally. Computational results show that the new algorithms outperform the existing procedures on sparse networks with large arc demands.

Original languageEnglish
Pages (from-to)189-198
Number of pages10
JournalComputers and Operations Research
Issue number2
StatePublished - 1 Jan 1991

Fingerprint Dive into the research topics of 'Augment-insert algorithms for the capacitated arc routing problem'. Together they form a unique fingerprint.

Cite this