The Traveling Salesman Problem

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. 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.

2 There are also necessary and sufficient conditions to determine if a possible solutiondoes exist when one is not given a complete graph. 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 .. Geometric Algorithm .. EXISTENCE OF HAMILTONIAN PATHS AND CYCLES.. Complete Graphs .. Not Complete Graphs .. APPLICATIONS.. Colleges .. Nearest Neighbor and Closest Insertion .. Geometric Algorithm.

3 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.. 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.. Stage 8b.. Closest Insertion Algorithm Pseudocode .. Stage 1 .. Stage 2 .. Stage 3.

4 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 .. 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).

5 Group 1 .. 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. 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.

6 Thank you all day e ry day. Thank you Dr. Beverly Michael, Dr. Catalin Trenchea, and Dr. 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. I amamazed that I get to have all of you in my life and I hope that I can be there for you as you have for family members around the country all are constantly supporting me. To Lisa, Lenny, Christine, all ofmy nieces, nephews, and cousins: your love is a blessing.

7 Thank you The Dax, Trevor, Kyle, Adam, Brad, Kerri and Fran for being amazing people in my life that Ican always count on although we are far away. I love you you to New Hope Church in Cotati, California. I want you to know that I count you as part of myfamily. Thank you for being so warm and inviting. A special thank you goes out to Fran, for making theserelationships THE Problem STATEDA Traveling Salesman wishes to go to a certain number of destinations in order to sell objects. He wants totravel to each destination exactly once and return home taking the shortest total voyage can be represented as a graphG= (V,E) where each destination, including his home, is avertex, and if there is a direct route that connects two distinct destinations then there is an edge betweenthose two vertices. The Traveling Salesman Problem is solved if there exists a shortest route that visits eachdestination once and permits the Salesman to return home.

8 (This route is called a Hamiltonian Cycle andwill be explained in Chapter 2.)The Traveling Salesman Problem can be divided into two types: the problems where there is a path betweenevery pair of distinct vertices (no road blocks), and the ones where there are not (with road blocks). Bothof these types of TSP problems are explained in more detail in Chapter we are not all Traveling Salesman , this Problem interests those who want to optimize their routes,either by considering distance, cost, or time. If one has four people in their car to drop off at their respectivehomes, then one automatically tries to think about the shortest distance possible. In this case, distanceis minimized. If one is Traveling to different parts of the city using the public transportation system, thenminimizing distance might not be the goal, but rather minimizing the first case, each vertex would be a person s home, and each edge would be the distance between the second case, each vertex would be a destination of the city and each edge would be the cost to getfrom one part of the city to the next.

9 Thus, the Traveling Salesman Problem optimizes SOME BASIC GRAPH THEORYB efore presenting algorithms and conditions for when a locally optimal solution exists, some basic graphtheory definitions are needed. For an extensive overview of Graph Theory, refer to [1] or [5]. BASIC DEFINITIONSThe platonic solids in figures through will be used to explain some basics of Graph : Tetrahedral GraphgfehbadcFigure : Cubical GraphDefinition 1.[Simple Graph]Asimple graph,G = (V,E), is a finite nonempty setVof objects called vertices (singular vertex) to-gether with a possibly empty setEof 2-element subsets ofVcalled of the figures in Chapter 2 are examples of simple : Octahedral GraphcbaedljhfnkmogistpqrFigure : Dodecahedral GraphDefinition 2.[Adjacent]Two vertices areadjacentif they are connected by an 3.[Incident]Vertexuand the edgeuvare said to beincidentwith each other.

10 Similarly,vanduvare Figure are adjacent, while verticesaandfin the same figure are not. In , vertexpand edgepqare incident, but vertexpand edgeaeare 4.[Degree of a Vertex]Thedegreeof a vertexv (denoted: deg(v))is the number of vertices inGthat are adjacent example, the vertexain Figure has degree three, while the vertexkin Figure has degree 5. Ina simple graph the maximum degree that any vertex can have is one less than the total number of 5.[Minimum and Maximum Degree of a Graph]Themaximumdegree of a graph,G, is the greatest degree over all of the vertices inG. Theminimumdegree of a graph is the least degree over all of the vertices inG. The maximum degree is denoted (G),while the minimum degree is denoted (G).For example, letH1= Figure andH2= Figure Then, (H1) = 5, and (H1) = 4, and (H2) = (H2) = 6.[Order and Size of a Graph]The number of vertices in a given graphG, denoted|V(G)|, is called theorderofGand is denotedOrd(G),or|G|.