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.