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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    An Evolutionary Hybrid Strategy for Solving the Rural Postman Problem


    Beteiligte:


    Erscheinungsdatum :

    01.11.2011


    Format / Umfang :

    296885 byte




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    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