The Traveling Salesman Problem - Department of …

1 THE Traveling Salesman PROBLEMbyCorinne , Sonoma State University, , University of Pittsburgh, 2013 Submitted to the Graduate Faculty ofthe Department of Mathematics in partial fulfillmentof the requirements for the degree ofMaster of SciencesUniversity of Pittsburgh2013 UNIVERSITY OF PITTSBURGHMATHEMATICS DEPARTMENTThis thesis was presentedbyCorinne BrucatoIt was defended onApril 16, 2013and approved byDr. Jeffrey Paul Wheeler, University of Pittsburgh, MathematicsDr. Beverly Michael, University of Pittsburgh, MathematicsDr.

2 Catalin Trenchea, University of Pittsburgh, MathematicsDr. Anna Vainchtein, University of Pittsburgh, MathematicsThesis Advisor: Dr. Jeffrey Paul Wheeler, University of Pittsburgh, MathematicsiiCopyrightc by Corinne Brucato2013iiiTHE Traveling Salesman PROBLEMC orinne Brucato, of Pittsburgh, 2013 Although a global solution for the Traveling Salesman Problem does not yet exist, there are algorithms for anexisting local solution. There are also necessary and sufficient conditions to determine if a possible solutiondoes exist when one is not given a complete graph.

3 This paper gives an introduction to the TravelingSalesman Problem that includes current research. Additionally, the algorithms are used to find a routetraveling through twenty US colleges. As well, we use the Geometric Algorithm to assign scouts for thePittsburgh OF THE Problem STATED.. SOME BASIC GRAPH THEORY.. Basic Definitions .. Advanced Definitions .. THE HISTORY.. COMPLEXITY CLASSES.. SOME KNOWN ALGORITHMS.. Nearest-Neighbor Algorithm .. Closest Insertion Algorithm.

4 Geometric Algorithm .. EXISTENCE OF HAMILTONIAN PATHS AND CYCLES.. Complete Graphs .. Not Complete Graphs .. APPLICATIONS.. Colleges .. Nearest Neighbor and Closest Insertion .. Geometric Algorithm .. Pittsburgh Pirates .. CONCLUSION..45 BIBLIOGRAPHY..46 INDEX..47vLIST OF Tetrahedral Graph .. Cubical Graph .. Octahedral Graph .. Dodecahedral Graph .. Icosahedral Graph .. Bridge Graph .. Removed edgegf.. Removed edgegi.. Removed edgehi.

5 Towns .. Complete Graph .. Highlight outer edges .. Convex Hull of the towns .. Dodecahedron Graph .. Sample Start .. Brute Force .. Start .. Stage 1 .. Stage 2 .. Stage 3 .. Stage 4 .. Stage 5 .. Stage 6 .. Final .. Start .. Stage 1 .. Stage 2 .. Final .. Nearest-Neighbor Pseudocode .. Start .. Stage 2 .. Stage 3 .. Stage 4 .. Stage 5 .. Stage 6a.. Stage 7a.. Stage 8a.. Stage 6b.. Stage 7b.

6 Stage 8b.. Closest Insertion Algorithm Pseudocode .. Stage 1 .. Stage 2 .. Stage 3 .. Stage 4 .. Stage 5 .. Stage 6 .. Stage 7 .. Stage 8 .. Stage 9 .. Stage 7 .. Stage 8 .. Stage 9 .. Stage 10 .. Geometric Algorithm Pseudocode .. Each Degree is 2 .. US Colleges (c 2013 Google,c 2013 Tele Atlas).. Driving Distances Between Each College (c 2013 Google,c 2013 Tele Atlas) .. Nearest Neighbor and Closest Insertion Algorithms on Colleges.

7 Hamiltonian Cycle Using the Nearest Neighbor and Closest Insertion Algorithm (c 2013 Google,c 2013 Tele Atlas) .. Stage 1 .. Stage 2 .. Stage 3 .. Stage 4 .. Stage 5 .. Stage 6 .. Stage 7 .. Stage 8 .. Stage 9 .. Stage 10 .. Stage 11 .. Stage 12 .. Final .. Geometric Algorithm on Colleges .. Hamiltonian Cycle Using the Geometric Algorithm (c 2013 Google,c 2013 Tele Atlas) .. NAME (c 2013 Google,c 2013 Tele Atlas) .. Group 1.

8 Group 2 .. Group 3 .. Group 4 .. Group 5 .. Group 6 .. Group 7 .. Group 8 .. Group 9 .. Group 10 .. Group 11 .. Group 12 .. Stage 1: (c 2013 Google,c 2013 Tele Atlas) .. Stage 2 .. Stage (n 1) .. Stagen: (c 2013 Google,c 2013 Tele Atlas) ..44viiiACKNOWLEDGEMENTSA great number of individuals are owed a debt of gratitude for their contribution to the academic successthat I have attained. The following are but a few of those and foremost, I would like to thank Dr.

9 Jeffrey Wheeler of the University of Pittsburgh because abso-lutely none of this would have been possible without him. Dr. Wheeler walked up to me one day and askedabout my future plans as a graduate student, and when he realized that I had no idea he said, You are goingto write a thesis, and I am going to be your advisor. I am so grateful for all of the time that he created outof nowhere in order to be a great advisor. Thank you all day e ry day. Thank you Dr. Beverly Michael, Dr. Catalin Trenchea, and Dr.

10 Anna Vainchtein for going above andbeyond the duties of serving on my committee. Thank you for all of the comments on this thesis, and formaking my days at the University of Pittsburgh a true would like to thank my parents for always believing in me, no matter what my dreams are at any givenmoment. You have shown me what it means to love and have faith, and for that I am would like to thank my many support groups around this country. Specifically in Pittsburgh, I wouldlike to thank Marc, Alex, Nadine, Soheil, and Stuart, all of whom have helped me in countless ways.