Article ID: | iaor2001247 |
Country: | United Kingdom |
Volume: | 27 |
Issue: | 2 |
Start Page Number: | 183 |
End Page Number: | 203 |
Publication Date: | Feb 2000 |
Journal: | Computers and Operations Research |
Authors: | Mart Rafael, Corbern Angel, Romero Antonio |
Keywords: | graphs, heuristics |
The Rural Postman Problem on a mixed graph (MRPP) consists of finding a minimum cost tour which traverses, at least once, the arcs and edges of a given subset of the arcs and edges of the graph. This problem is known to be NP-hard. This paper presents two heuristic approaches to solve it. An approximate algorithm based on the resolution of some flow and matching problems and a tabu search implementation is presented. The tabu search algorithm seeks high-quality tours by means of a switching mechanism in an intensification phase and two levels of diversification. Computational results are presented to assess the merits of the method.