Home Methods Data Analysis Conclusions/Future Studies and Motivations References

**Abstract**

The Traveling Salesman Problem is a classical operations research problem that deals with optimization, scheduling, and planning. The objective of this senior design project is to implement a divide and conquer algorithm to code a more efficient search algorithm than conventional exhaustive methods. Using Matlab, the Traveling Salesman Problem was perceived as an incidence matrix and divided into smaller sub-matrices. The divide and conquer method algorithm successfully processed the graph faster than exhaustive approaches. However, an important note to make is that there is a trade-off for the faster data processing. Though far slower, the exhaustive method produces all possible paths and possibilities, whereas the divide and conquer method neglects many paths. This divide and conquer method can be incorporated into larger graph problems to expedite search time and search for a relatively viable and efficient solutions.

**Introduction**

The Traveling Salesman Problem (TSP) is a classical
optimization problem often studied in operations research and theoretical
computer science. The general idea of the problem is that a salesman
is assigned to traveling through a set of
n cities, but can only visit
each city once and cities have specific paths connecting to another city (*Schättler,
88-100*). Given these restrictions, the salesman’s
goal is to find the shortest, optimal path. Further complications can be added
to the problem such as a path cost or queue time at a city. For the purpose of
this project, the graph is converted to a Hamiltonian graph. The paths have no weight
and the paths are undirected (Hamiltonian
Path).
Essentially a Hamiltonian graph is a simplified version of TSP graph without
cost or direction. To clarify future references, cycles and graph henceforth
mentioned will be Hamiltonian.
TSP and Hamiltonian cycle represents a general, broader
class of combinatorial optimization problems called NP-complete. Therefore a
specific algorithm applied to the TSP will also be applicable to all NP-complete
problems (*Hoffman and Padberg*).
The motivation of study the TSP is its applicability in real-world use.
Scheduling, city design, genome sequencing, and computer algorithms are some of
the many fields that TSP contributes to (TSP
Applications).

The TSP's goal is to find the optimal path that has the lowest cost and passes through each city once.