Heuristic Algorithms for Bike Route Generation

Planning routes for recreational cyclists is challenging because they prefer longer more scenic paths, not the shortest one. This problem is modeled as an instance of the Arc Orienteering Problem (AOP), a known NP-Hard optimization problem. Because no known algorithms exist to solve this optimization problem efficiently, we focus on heuristic algorithms which trade accuracy for speed to solve the AOP. We implement and evaluate two different Iterated Local Search heuristic algorithms using an open source routing engine called GraphHopper and the OpenStreetMap data set. Experimental results show that better routes can be achieved at the expense of longer route generation time.