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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    An Evolutionary Hybrid Strategy for Solving the Rural Postman Problem


    Contributors:


    Publication date :

    2011-11-01


    Size :

    296885 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    The Hierarchical Mixed Rural Postman Problem

    Colombi, Marco / Corberán, Ángel / Mansini, Renata et al. | British Library Online Contents | 2017


    The Hierarchical Mixed Rural Postman Problem

    Colombi, Marco | Online Contents | 2017


    The Hierarchical Mixed Rural Postman Problem

    Colombi, Marco | Online Contents | 2016


    The Directed Rural Postman Problem with Turn Penalties

    Benavent, Enrique | Online Contents | 1999


    The Directed Rural Postman Problem with Turn Penalties

    Benavent, E. / Soler, D. | British Library Online Contents | 1999