Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
476168 | Computers & Operations Research | 2006 | 8 Pages |
Abstract
This paper describes a constructive heuristic for the well-known Undirected Rural Postman Problem. At each iteration, the procedure inserts a connected component of the required edges and performs a local postoptimization. Computational results on a set of benchmark instances with up to 350 vertices show that the proposed procedure is competitive with the classical Frederickson procedure. Its use is recommended when a high-quality solution is needed in a short amount of time (e.g., in laser plotter applications).
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Gianpaolo Ghiani, Demetrio Laganà, Roberto Musmanno,