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

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

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.