The covering Chinese postman problem: exact and heuristic methods

The covering Chinese postman problem (CCPP) is a combinatorial optimization problem. Given an undirected graph with cost and covering functions associated to the edges, this problem aim to find a minimum cost tour that covers all the edges of the graph. The problem is modeled by an integer programming mathematical formulation. An exact branch-and-cut method and a heuristic method are proposed for the CCPP. Extensive computational experiments were performed. Branch-and-cut method was able to obtain 325 optimal solutions out of 390 instances, while heuristic method obtained better solutions for some large instances in shorter processing times.