Date of Award
Bachelor of Science
biking, cycling, routing, bike routes, search, iterated local search, algorithms, heuristics, open street maps
Planning routes for recreational cyclists is challenging because they prefer longer more scenic routes, not the shortest one. This problem can be 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 solve the AOP using heuristic algorithms which trade accuracy for speed. We implement and evaluate two different Iterated Local Search (ILS) heuristic algorithms using an open source routing engine called GraphHopper and the OpenStreetMap data set. We propose ILS variants which our experimental results show can produce better routes at the cost of time.
Pieper, Aidan, "Iterated Local Search Algorithms for Bike Route Generation" (2018). Honors Theses. 1680.