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.