Variants of the Capacitated Arc Routing Problem

Luc Muyldermans, Gu Pang

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)peer-review

1 Downloads (Pure)


The Undirected Capacitated Arc Routing Problem (UCARP or CARP), first introduced by Golden and Wong [46], considers an undirected network or graph where every edge has a nonnegative length or cost and some of the edges (also called the required edges) have a positive demand for service. A fleet of identical vehicles, each vehicle with limited capacity, is based at the depot. The aim in the UCARP is to find a set of vehicle tours of total minimum length, each tour starting and ending at the depot, such that every required edge is serviced in exactly one tour, and that the total load on each route does not exceed the vehicle capacity. Heuristic solution procedures, lower bounds, and exact methods for CARP were covered in Chapters 7, 8, and 9 of this book.
Original languageEnglish
Title of host publicationArc Routing
Subtitle of host publicationProblems, Methods, and Applications
EditorsÁngel Corberán, Gilbert Laporte
PublisherSociety for Industrial and Applied Mathematics (SIAM)
ISBN (Electronic)978-1-61197-367-9
ISBN (Print)978-1-61197-366-2
Publication statusPublished - 2014

Publication series

NameMOS-SIAM Series on Optimization
PublisherSociety for Industrial and Applied Mathematics (SIAM)


Dive into the research topics of 'Variants of the Capacitated Arc Routing Problem'. Together they form a unique fingerprint.

Cite this