Senior Honors Projects, 2010-current

Date of Award

Spring 2016

Document Type

Dissertation/Thesis

Degree Name

Bachelor of Science (BS)

Department

Department of Computer Science

Advisor(s)

David H. Bernstein, Ph.D.

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.

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.