Arc routing problems, part I: The Chinese postman problem

Arc routing problems arise in several areas of distribution management and have long been the object of study by mathematicians and operations researchers. In the first of a two-part survey, the Chinese postman problem (CPP) is considered. The main algorithmic results for the CPP are reviewed in five main sections: the undirected CPP, the directed CPP, the windy postman problem, the mixed CPP, and the hierarchical CPP.