A branch-and-cut algorithm for the Undirected Rural Postman Problem

作者：Ghiani G^*; Laporte G

来源：Mathematical Programming, 2000, 87(3): 467-481.

DOI：10.1007/s101070050007

• Arc Routing Problems
• Undirected Rural Postman Problem
• branch-and-cut
• polyhedral analysis
• facets

The well-known Undirected Rural Postman Problem is considered and a binary linear problem using new dominance relations is presented. Polyhedral properties are investigated and a branch-and-cut algorithm is developed. Extensive computational results indicate that the algorithm is capable of solving much larger instances than previously reported.

• 出版日期2000-5