Solution methods for the cycle trip planning problem

We present a novel approach to path finding in a directed graph, namely finding the route with the highest score, starting at one of the possible starting locations and with a length between a minimum and maximum distance. This setting is motivated by the problem that a recreational cyclist faces when searching the nicest route of a certain length. Our contributions are a clear definition and a mathematical model of the cycle trip planning problem (CTPP), a branch-and-cut approach for small instances and a metaheuristic that solves CTPP instances to near optimality in on average 0.6 seconds of computation time