Arc routing problems (ARPs) arise naturally in several applications where streets require maintenance, or customers located along road must be serviced. The undirected rural postman problem (URPP) is to determine a least cost tour traversing at least once each edge that requires a service. When demands are put on the edges and this total demand must be covered by a fleet of identical vehicles of capacity Q based at a depot, one gets the undirected capacitated arc routing problem (UCARP). The URPP and UCARP are known to be NP-hard. This chapter reports on recent exact and heuristic algorithms for the URPP and UCARP.