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.
An extension of the arc orienteering problem and its application to cycle trip planning
2014-05-09
15 pages
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
An extension of the arc orienteering problem and its application to cycle trip planning
Online Contents | 2014
|Navigational Planning in Orienteering
Online Contents | 1997
|The Correlated Arc Orienteering Problem
Springer Verlag | 2022
|Dubins orienteering problem with neighborhoods
IEEE | 2017
|The Team Orienteering Arc Routing Problem
Online Contents | 2014
|