The capacitated arc routing problem is one of the most important routing problems with many applications in real world situations. Since this problem is NP-hard, numerous heuristics and metaheuristics have been developed to solve it. In this paper, we propose a new constructive and improvement heuristic. The quality of this new approach was tested on three standard benchmark instances, and the results were compared with some known existing heuristics and metaheuristics in the literature.
