The Rural Postman Problem (RPP) is a classical arc routing problem proven to be NP-Hard whith applications in many contexts of practical interest. A common strategy for solving RPP instances is to first determine a suitable graph transformation in order to either reduce the dimensionality of the search space or to produce a single cursus graph to derive an Eulerian circuit in polynomial time. In this paper we present a simple but effective hybrid heuristic for the RPP that uses such a graph transformation and finds solutions using a Genetic Algorithm for global search and a local search algorithm to compute optimal traversal directions of a solution tour. Our approach is tested on a set of instances than have been already used in previously published work.
An Evolutionary Hybrid Strategy for Solving the Rural Postman Problem
2011-11-01
296885 byte
Conference paper
Electronic Resource
English
The Hierarchical Mixed Rural Postman Problem
British Library Online Contents | 2017
|The Hierarchical Mixed Rural Postman Problem
Online Contents | 2017
|The Hierarchical Mixed Rural Postman Problem
Online Contents | 2016
|The Directed Rural Postman Problem with Turn Penalties
Online Contents | 1999
|The Directed Rural Postman Problem with Turn Penalties
British Library Online Contents | 1999
|