In this paper, we study a generalization of the Hierarchical Chinese Postman Problem on a mixed graph where only a subset of arcs and edges require a service to be accomplished following a hierarchical order. The problem, called the Hierarchical Mixed Rural Postman Problem, also generalizes the Rural Postman Problem and thus is NP-hard. We propose a new mathematical formulation, and introduce two effective solution algorithms. The first procedure is a matheuristic that is based on the exact solution of a variant of the Mixed Rural Postman Problem for each hierarchy. The second approach is a tabu search algorithm based on different improvement and diversification strategies. Computational results on an extended set of instances show how the proposed solution methods are quite effective and efficient when compared to the solutions of a branch-and-cut algorithm stopped after one hour of computation.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    The Hierarchical Mixed Rural Postman Problem



    Erschienen in:

    Transportation science ; 51 , 2 ; 755-770


    Erscheinungsdatum :

    2017




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Print


    Sprache :

    Englisch



    Klassifikation :

    Lokalklassifikation TIB:    770/1935/7000
    BKL:    55.80 / 55.80 Verkehrswesen, Transportwesen: Allgemeines



    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 | 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


    An Evolutionary Hybrid Strategy for Solving the Rural Postman Problem

    Marcial-Romero, J. R. / Montes-Venegas, H. A. / Zuniga, J. H. | IEEE | 2011