Augment-insert algorithms for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is a generalization of the rural postman problem (RPP), which has many real-world applications. Examples include routing of school buses, mail delivery vehicles, street sweepers and many others. The CARP has been shown to be NP-hard, and, therefore, heuristic procedures are desired to solve the CARP approximately. In this paper, two new algorithms to solve the CARP near-optimally are introduced. Computational results show that the new algorithms outperform the existing procedures on sparse networks with large arc demands.