Traveling Salesman Problem
Abstract
In the Traveling Salesman Problem (TSP), a list of cities and the distances between them are given. The goal is to find the shortest possible route that visits each city exactly once and returns to the original city. The TSP has a wide range of applications in many different industries including, but not limited to, optimizing mail and shipping routes, guiding industrial machines, mapping genomes, and improving autonomous vehicles. For centuries, traveling salesmen, politicians, and circuit preachers have tackled their own versions of the problem. Within the last century, the TSP has become one of the most important problems in the fields of mathematics and computer science. The time to find an exact solution is often impractically long, which has led to the development of numerous approximation techniques, ranging from linear programming methods to nature-inspired models. Here, we present a novel N-body approach to the TSP.
Publications
Johnny Seay, Edwin Gonzalez, Stephen Lowe, Jesse Crawford, Bryant Wyatt (2020). “N-Body Approach to the Traveling Sales Man Problem (TSP)”. Pearson Publishing, Boston, Ma: International Conference on Technology in Collegiate Mathematics.
Students
Johnny Seay
Edwin Gonzalez
Stephan Lowe
Baylor Fain
Taylor Hutyra
Clayton Tobin
Collaborators
Dr. Jesse Crawford
Posters
Videos
Student Presentations
Math Day 2020 (Virtual because of COVID-19)
Tarleton State University – Stephenville, Texas April 28 2020
-
An N-body Approach to the Traveling Salesman Problem – Clayton Tobin
123nd Annual Meeting of the Texas Academy of Science
Stephen F. Austin University – Nacogdoches, Texas February 28-29, 2020
-
N-body Approach to the Traveling Salesman Problem – Clayton Tobin
Texas Oklahoma Regional Undergraduate Symposium
Cameron University – Lawton, Ok February 15, 2020
-
N-body Approach to the Traveling Salesman Problem – Clayton Tobin
Second Annual Meeting SIAM TX-LA Section
Southern Methodist University – Dallas, Texas, November 1–3, 2019
-
N-Body Approach to the Traveling Salesman Problem – Johnny Seay
15th Annual Texas Undergraduate Mathematics Conference
University of Texas at Tyler – Tyler, Texas October 25-26, 2019
-
An N-body Approach to the Travelling Salesman Problem – Johnny Seay
Math Day 2019
Tarleton State University – Stephenville, Texas May 2 2019
-
An N-body Approach to the Travelling Salesman Problem Utilizing GPUs – Johnny Seay
Tarleton College of Science and Technology Research Symposium
Tarleton State University – Stephenville, Tx April 4, 2019
-
N-body Approach to the Traveling Salesman Problem – Johnny Seay
99th Annual Meeting of the Texas Section of the MAA
Tarleton State University – Stephenville, Tx March 28 -30, 2019
-
N-body Approach to the Traveling Salesman Problem – Johnny Seay
Texas Oklahoma Regional Undergraduate Symposium
Southern Nazarene University – Bethany, Ok February 23, 2019
-
N-body Approach to the Traveling Salesman Problem – Johnny Seay
Math Day 2018
Stephenville, Texas May 3 2018
-
N-body Approach to the Traveling Salesman Problem (TSP) – Edwin Gonzalez & Stephan Lowe (First place)
98th Annual Meeting of the Texas Section of the MAA
El Centro College – Dallas, Tx April 5-7, 2018
-
N-body Approach to the Traveling Salesman Problem (TSP) - Edwin Gonzalez, Stephanie Lowe (First place applied mathematics)
12th Annual Texas Oklahoma Research Undergraduate Symposium (TORUS)
Midwestern State University, Wichita Falls, Texas February 10, 2018
-
N-body Approach to the Traveling Sales Man Problem – Edwin Gonzalez, Stephen Lowe
TSU COST Research Week Poster Session
Stephenville, Texas October 25, 2017
-
N-body Approach to the Traveling Sales Man Problem – Edwin Gonzalez, Stephen Lowe
13th Annual Texas Undergraduate Mathematics Conference
University of The Incarnate Word– San Antonio, Tx 10/20/2017 – 10/21/2017
-
N-body Approach to the Traveling Sales Man Problem – Edwin Gonzalez, Stephen Lowe
14th Annual Tarleton State University Student Research Symposium
Tarleton State University 10/16/2015
-
N-Body solution to the Traveling Sales Man Problem – Baylor Fain, Taylor Hutyra
Tarleton State University – Stephenville, Texas April 28, 2020
-
An N-body Approach to the Traveling Salesman Problem – Clayton Tobin
123rd Annual Meeting of the Texas Academy of Science
Stephen F. Austin University – Nacogdoches, Texas February 28-29, 2020
-
N-body Approach to the Traveling Salesman Problem – Clayton Tobin
Texas Oklahoma Regional Undergraduate Symposium
Cameron University – Lawton, Ok February 15, 2020
-
N-body Approach to the Traveling Salesman Problem – Clayton Tobin
Second Annual Meeting SIAM TX-LA Section
Southern Methodist University – Dallas, Texas, November 1–3, 2019
-
N-Body Approach to the Traveling Salesman Problem – Johnny Seay
15th Annual Texas Undergraduate Mathematics Conference
University of Texas at Tyler – Tyler, Texas October 25-26, 2019
-
An N-body Approach to the Travelling Salesman Problem – Johnny Seay
Math Day 2019
Tarleton State University – Stephenville, Texas May 2, 2019
-
An N-body Approach to the Travelling Salesman Problem Utilizing GPUs – Johnny Sea
Tarleton College of Science and Technology Research Symposium
Tarleton State University – Stephenville, Tx April 4, 2019
-
N-body Approach to the Traveling Salesman Problem – Johnny Seay
99th Annual Meeting of the Texas Section of the MAA
Tarleton State University – Stephenville, Tx March 28 -30, 2019
-
N-body Approach to the Traveling Salesman Problem – Johnny Seay
Texas Oklahoma Regional Undergraduate Symposium
Southern Nazarene University – Bethany, Ok February 23, 2019
-
N-body Approach to the Traveling Salesman Problem – Johnny Seay
Math Day 2018
Stephenville, Texas May 3, 2018
-
N-body Approach to the Traveling Salesman Problem (TSP) – Edwin Gonzalez & Stephan Lowe (First place)
98th Annual Meeting of the Texas Section of the MAA
El Centro College – Dallas, Tx April 5-7, 2018
-
N-body Approach to the Traveling Salesman Problem (TSP) - Edwin Gonzalez, Stephanie Lowe (First place applied mathematics)
12th Annual Texas Oklahoma Research Undergraduate Symposium (TORUS)
Midwestern State University, Wichita Falls, Texas February 10, 2018
-
N-body Approach to the Traveling Sales Man Problem – Edwin Gonzalez, Stephen Lowe
TSU COST Research Week Poster Session
Stephenville, Texas October 25, 2017
-
N-body Approach to the Traveling Sales Man Problem – Edwin Gonzalez, Stephen Lowe
13th Annual Texas Undergraduate Mathematics Conference
University of The Incarnate Word– San Antonio, Tx 10/20/2017 – 10/21/2017
-
N-body Approach to the Traveling Sales Man Problem – Edwin Gonzalez, Stephen Lowe
14th Annual Tarleton State University Student Research Symposium
Tarleton State University 10/16/2015
-
N-Body solution to the Traveling Sales Man Problem – Baylor Fain, Taylor Hutyra
Closing Remarks
This project still has a great deal of opportunities for future work.