A constructive heuristic for the undirected rural postman problem
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). (c) 2005 Elsevier Ltd. All rights reserved.
heuristics rural postman problem arc routing