Theoretical and computational analysis of a new formulation for the Rural Postman Problem and the General Routing Problem
针对农村邮递员问题和一般路由问题，提出一种使用两组二元变量的新公式，并给出有效不等式族，基于此设计分支切割算法，在大型基准实例上测试并优于已知最佳精确方法。
The Rural Postman Problem (RPP) is one of the most well-known problems in arc routing. Given an undirected graph, the RPP consists of finding a closed walk traversing and servicing a given subset of edges with minimum total cost. In the General Routing Problem (GRP), there is also a subset of vertices that must be visited. Both problems were introduced by Orloff and proved to be NP-hard. In this paper, we propose a new formulation for the RPP and the GRP using two sets of binary variables representing the first and second traversal, respectively, of each edge. We present several families of valid inequalities that induce facets of the polyhedron of solutions under mild conditions. Using this formulation and these families of inequalities, we propose a branch–and–cut algorithm, test it on a large set of benchmark instances, and compare its performance against the exact procedure that, as far as we know, produced the best results. The results obtained show that the proposed formulation is useful for solving undirected RPP and GRP instances of very large size.