A heuristic algorithm based on Monte Carlo methods for the rural postman problem

A heuristic algorithm based on Monte Carlo methods for the rural postman problem

0.00 Avg rating0 Votes
Article ID: iaor19991810
Country: United Kingdom
Volume: 25
Issue: 12
Start Page Number: 1097
End Page Number: 1106
Publication Date: Dec 1998
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics
Abstract:

The Rural Postman Problem (RPP) consists of finding a minimum cost traversal of a specified arc subset of a graph. Given that the RPP is a NP-hard problem, heuristic algorithms are interesting both to handle large size instances and to provide upper bounds that could be used in branch and cut procedures. In this paper we propose a heuristic algorithm for the RPP based on Monte Carlo methods. We simulate a vehicle travelling randomly over the graph, jumping from one node to another on the basis of certain probabilities. Monte Carlo methods provide a simple approach to many different Routing Problems and they are easily implemented in a computer code. The application of this algorithm to a set of RPP instances taken from the literature demonstrates that, using the appropriate probabilities, they are also efficient.

Reviews

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