Arc routing problems (ARPs) are a special kind of vehicle routing problem, in which the demands are located on edges or arcs, instead of nodes. There is a huge literature on ARPs, and a variety of exact and heuristic algorithms are available. Recently, however, we encountered some real-life ARPs with over 10 000 roads, which is much larger than those usually considered in the literature. For these problems, we develop fast upper- and lower-bounding procedures. We also present extensive computational results.