Heuristic Algorithms

Arc routing problems (ARPs) arise naturally in contexts where streets require treatments, or customers located along road must be served. Most ARPs are NP-hard and of large scale. They can therefore rarely be tackled by means of exact solution methods. This certainly explains why numerous heuristic algorithms have been developed for the solutions of ARPs. We will try in this chapter to give an overview of the main approaches and tools that are commonly used in heuristic procedures for ARPs. We do not aim to make an exhaustive survey of all articles that are devoted to this topic. We seek, however, to point out that the ingredients used in the heuristic methods strongly depend on the structure of the underlying graph.