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
01.11.2011
296885 byte
Aufsatz (Konferenz)
Elektronische Ressource
Englisch
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
|