The Traveling Salesman Problem

THE TRAVELING SALESMAN PROBLEM

by Corinne Brucato B.A., Sonoma State University, 2010 M.S., University of Pittsburgh, 2013

Submitted to the Graduate Faculty of the Department of Mathematics in partial fulfillment

of the requirements for the degree of Master of Sciences

University of Pittsburgh 2013

UNIVERSITY OF PITTSBURGH MATHEMATICS DEPARTMENT

This thesis was presented by

Corinne Brucato It was defended on

April 16, 2013 and approved by Dr. Jeffrey Paul Wheeler, University of Pittsburgh, Mathematics Dr. Beverly Michael, University of Pittsburgh, Mathematics Dr. Catalin Trenchea, University of Pittsburgh, Mathematics Dr. Anna Vainchtein, University of Pittsburgh, Mathematics Thesis Advisor: Dr. Jeffrey Paul Wheeler, University of Pittsburgh, Mathematics

ii

Copyright c by Corinne Brucato 2013

iii

THE TRAVELING SALESMAN PROBLEM Corinne Brucato, M.S.

University of Pittsburgh, 2013 Although a global solution for the Traveling Salesman Problem does not yet exist, there are algorithms for an existing local solution. There are also necessary and sufficient conditions to determine if a possible solution does exist when one is not given a complete graph. This paper gives an introduction to the Traveling Salesman Problem that includes current research. Additionally, the algorithms are used to find a route traveling through twenty US colleges. As well, we use the Geometric Algorithm to assign scouts for the Pittsburgh Pirates.

iv

TABLE OF CONTENTS

1.0 THE PROBLEM STATED . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2.0 SOME BASIC GRAPH THEORY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 Advanced Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.0 THE HISTORY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.0 COMPLEXITY CLASSES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5.0 SOME KNOWN ALGORITHMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5.1 Nearest-Neighbor Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5.2 Closest Insertion Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 5.3 Geometric Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 6.0 EXISTENCE OF HAMILTONIAN PATHS AND CYCLES . . . . . . . . . . . . . . . . 28 6.1 Complete Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 6.2 Not Complete Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 7.0 APPLICATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 7.1 Colleges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

7.1.1 Nearest Neighbor and Closest Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . 35 7.1.2 Geometric Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 7.2 Pittsburgh Pirates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 8.0 CONCLUSION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 INDEX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

v

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download