Date of Award

Spring 2002

Document Type



Mathematics, Engineering & Computer Science

First Advisor

Holly Zullo

Second Advisor

Mark Parker

Third Advisor

Joan Stottlemyer


Finding an efficient algorithm for solving NP-Complete problems has long been a goal of computer scientists and mathematicians. The purpose of this paper is to examine existing heuristics (approximate algorithms) and to construct original heuristics for solving the Traveling Salesperson Problem, a famous NP-Complete problem. Each heuristic is implemented on a personal computer using C++. The results of the heuristics are then compared against the best known solutions for specific well-studied instances of the problem.