Skip to Main content Skip to Navigation
Book sections

Chapter 7: The Capacitated Arc Routing Problem: Heuristics

Abstract : Whereas all previous chapters have covered arc routing problems (ARPs) with a single vehicle, this chapter opens the second part of the book, devoted to problems involving several vehicles with limited capacity. More precisely, the chapter addresses the seminal problem in this category, the Capacitated Arc Routing Problem (CARP). This important problem plays the same role in arc routing as the Capacitated Vehicle Routing Problem (CVRP) in node routing: Even if recent extensions get closer to the real world by handling more constraints, the CARP is already hard enough to constitute a good laboratory to develop and test new ideas in arc routing. The CARP is obviously more difficult than uncapacitated ARPs and its study is also more recent, explaining why many results concern constructive heuristics and metaheuristics. This chapter focuses on such approaches, while Chapters 8, 9, 10, respectively, survey lower bounds, exact algorithms, and more general problems.
Document type :
Book sections
Complete list of metadatas
Contributor : Daniel Gavrysiak <>
Submitted on : Wednesday, February 26, 2020 - 12:01:01 PM
Last modification on : Thursday, February 27, 2020 - 1:55:02 AM





Christian Prins. Chapter 7: The Capacitated Arc Routing Problem: Heuristics. Arc Routing, Society for Industrial and Applied Mathematics, pp.131-157, 2015, 978-1-61197-367-9. ⟨10.1137/1.9781611973679.ch7⟩. ⟨hal-02491681⟩



Record views