Highlights We define and mathematically model the cycle trip planning problem (CTPP). We developed a set of realistic test instances with known optimal solutions based on an actual cycle network. We present a branch-and-cut procedure which is able to solve small problem instances to optimality. We design an efficient and effective metaheuristic to tackle realistic CTPP instances. The performance and robustness concerning quality and computation time of both procedures are verified.

    Abstract The cycle trip planning problem (CTPP) can be formulated as a variant of the arc orienteering problem (AOP), which is a well-known combinatorial optimisation problem. The CTPP aims at finding a route with the highest possible score, in a directed graph, among those having a total length that does not exceed some given upper bound. The contributions of this paper are a new mathematical programming model for the CTPP and two solution methods for its solution. The first is a branch-and-cut approach that is able to solve small problem instances to optimality and the second is a metaheuristic that solves CTPP and AOP instances of realistic size to near optimality in a few seconds.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    An extension of the arc orienteering problem and its application to cycle trip planning


    Beteiligte:
    Verbeeck, C. (Autor:in) / Vansteenwegen, P. (Autor:in) / Aghezzaf, E.-H. (Autor:in)


    Erscheinungsdatum :

    2014-05-09


    Format / Umfang :

    15 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch





    Navigational Planning in Orienteering

    Murakoshi, Shin | Online Contents | 1997


    The Correlated Arc Orienteering Problem

    Agarwal, Saurav / Akella, Srinivas | Springer Verlag | 2022


    Dubins orienteering problem with neighborhoods

    Penicka, Robert / Faigl, Jan / Vana, Petr et al. | IEEE | 2017


    The Team Orienteering Arc Routing Problem

    Archetti, Claudia | Online Contents | 2014