Senior Honors Projects, 2010-2019
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.
Date of Graduation
Spring 2016
Document Type
Thesis
Degree Name
Bachelor of Science (BS)
Department
Department of Computer Science
Advisor(s)
David H. Bernstein
Abstract
Shortest-path problems have seen a huge amount of study over the course of the last 50 years. Not surprisingly, this means the original problem of finding the shortest path from some starting location to some destination location has been thoroughly studied. However a large number of slight variations on the original problem still have yet to be thoroughly examined. In this paper we examine one of those variations, namely the problem of determining the optimal route from some source location to some destination location such that at least one location in an intermediate set is included in the route. Three algorithms/heuristics for solving this problem were developed and then tested against modified Virginia roadway data. The Brute Force Algorithm, Bi-Directional Heuristic and Multi-Label Heuristic each solve the problem in slightly different ways. Using a variety of representative test-cases on the Virginia roadways we found that the Brute Force algorithm greatly outperformed both the Bi-Directional and Multi-Label Heuristics. We also consider why this might be the case and discuss several promising directions for future work.
Recommended Citation
Young, Steven D., "A comparison of algorithms and heuristics for solving the O 1 I n D 1 shortest route problems" (2016). Senior Honors Projects, 2010-2019. 222.
https://commons.lib.jmu.edu/honors201019/222
