Date of Award
6-2018
Document Type
Open Access
Degree Name
Bachelor of Science
Department
Computer Science
First Advisor
Matthew Anderson
Language
English
Keywords
biking, cycling, routing, bike routes, search, iterated local search, algorithms, heuristics, open street maps
Abstract
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.
Recommended Citation
Pieper, Aidan, "Iterated Local Search Algorithms for Bike Route Generation" (2018). Honors Theses. 1680.
https://digitalworks.union.edu/theses/1680