Optimization Approaches for Recreational Bicycle Tour Planning

Exercising is important to stay healthy. Therefore, we develop an algorithm for finding nice recreational bicycle tours with the goal of making exercising by cycling more attractive. We formulate this challenge as a mathematical optimization problem similar to the arc orienteering problem (AOP) on a directed multigraph. The objective is to maximize the attractiveness of a route under the condition of not exceeding a maximal tour length. It allows multiple usage of streets, but penalizes it such that the attractiveness or score of the route decreases. The problem is NP-hard and developing practically effective algorithms running in reasonable time is therefore crucial. Three mixed integer linear programs are provided for solving the given problem exactly. The first program uses a classical cut formulation as sub tour elimination, the second a flow formulation and the third the combination of the first two. Testing the implementations of the three mixed integer linear programs using CPLEX reveals that the flow formulation is for our purposes more efficient than the other two formulations. Compared to other exact algorithms solving similar problems like the AOP, our implementation of the flow formulation is faster up to a factor of 1000. If we compare our implementation with heuristic approaches for similar problems, we get the result that for some instances our implementation finds the optimal solution in short time and the heuristic approaches do not find the optimal solution. However, the heuristics scale better for large instances. On the countryside the algorithm is applicable for routes up to 60km and in urban areas for routes up to 13km, which seems to be enough for our intended practical purposes.