On the undirected Rural Postman Problem:: Tight bounds based on a new formulation
成果类型：
Article
署名作者：
Fernández, E; Meza, O; Garfinkel, R; Ortega, M
署名单位：
Universitat Politecnica de Catalunya; Simon Bolivar University; University of Connecticut
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.51.2.281.12790
发表日期：
2003
页码：
281-291
关键词：
摘要：
The Rural Postman Problem (RPP) is a classic edge-routing problem. A mathematical programming formulation of the RPP that differs fundamentally from those in the literature was introduced, but not tested computationally, by Garfinkel and Webb (1999). A rudimentary algorithm that yields lower bounds via cutting planes and upper bounds via heuristics is developed and tested for a variation of that formulation. Computational results are encouraging, especially in terms of the relatively small number of added inequalities needed to get good lower bounds, and the fact that the vast majority of these have efficient, exact separation procedures. Note that a first algorithm based on this new formulation is computationally competitive, allowing the possibility of far more efficient and complex future realizations.