Heuristics for the mixed rural postman problem

Heuristics for the mixed rural postman problem

0.00 Avg rating0 Votes
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: , ,
Keywords: graphs, heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.