Home                    Methods                    Data Analysis                    Conclusions/Future Studies and Motivations                    References                     

Applying Divide and Conquer Search Algorithm in Traveling Salesman Problem

 

 

 

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.