Abstract
This project investigates an approach to road-trip optimization. We formulate a Traveling Salesman problem to minimize the overall travel cost accumulated along a road-trip route. The NP-hard complexity of TSP makes exact methods inefficient at locating solutions. We research the alternate solution methods known as heuristics and implement a repetitive nearest-neighbor heuristic, a simulated annealing metaheuristic, and a genetic algorithm metaheuristic. We apply these three methods to the 40-National Park TSP referred to as the Road Trip Problem.
Advisor
Pasteur, R. Drew
Department
Mathematics
Recommended Citation
Burke, Lauren, "Are We There Yet?: A Traveling-Salesman Approach to Road-Trip Optimization" (2017). Senior Independent Study Theses. Paper 11800.
https://openworks.wooster.edu/independentstudy/11800
Disciplines
Applied Mathematics | Computer Sciences
Keywords
traveling salesman, np-hard, graph theory, hamiltonian, complexity, simulated annealing, genetic algorithm, heuristic, metaheuristic
Publication Date
2017
Degree Granted
Bachelor of Arts
Document Type
Senior Independent Study Thesis
© Copyright 2017 Lauren Burke