Lower bounds for hierarchical Chinese postman problem

Arc routing problems aim at finding a least cost traversal on a network with or without additional constraints. The Hierarchical Chinese Postman Problem (HCPP) is an arc routing problem. HCPP is NP-hard and several heuristics have been developed to solve this problem. The Chinese Postman Problem (CPP) tour solution is a known lower bound for the HCPP. This paper presents a heuristic that will prescribe improved lower bounds for the HCPP when compared to the CPP solutions. Better lower bounds aid exact search methods, such as branch-and-bound, to find an optimal solution in a shorter run time. It can also be used to determine the quality of a heuristic solution. Several problem instances were generated to evaluate the proposed heuristic. Experimental results indicate that our lower bounds are better than the CPP solution for all the sample problems chosen.