Team: 6
School: Capital High
Area of Science: Logistics
Interim: Team Number: 6
School Name: Capital High School
Area of Science: Logistics
Project Title: The Traveling Salesman Problem
Problem Definition:
The Traveling Salesman Problem is a very commonly known mathematical problem that asks for the “most efficient trajectory possible given a set of points and distances that must all be visitedâ€.In the old days, there used to be traveling salesmen who would go to different cities and states to sell their product, simple enough right? It is true that in today's world we don’t see any more of these “salesmen†because of the technology we have, but we do have the post office who deliver our mail, along with the people who operate school and city buses.
But all of these people face one common obstacle, what happens when there is more than one destination? It is pretty simple to find the most efficient route when you have about 3 to 5 places to go but what about when you have +20 places to visit? This is the biggest question this whole problem is based on, what is the most efficient route to take? Other problems people want to avoid but may face are common things like traffic, gas prices ( which are fairly expensive nowadays), and time management.
Problem Solution:
Our mission is to create an algorithm that will calculate the most efficient route in order to avoid traffic, accidents, and waste less gas. We want to find the most efficient route possible, in order for that to happen, we have to come up with different types of algorithms that work differently but efficiently.
Progress to Date:
Currently, we have been doing research and getting familiar with the problem and some algorithms that we have been testing in NetLogo. We have read over a few articles and we have found a few algorithms, for example, the “greedy†algorithm is about choosing the next closest city there is. We have been working with NetLogo over the past few months to create our first model. Our model works with links that connect the turtles shown on the interface and lists to shorten the program because without lists the program will be very long and helps us save computer memory this helps us avoid extra steps. With the “foreach†command it commands each item on the list to do what is asked, making the code shorter and better to understand. To make the links connect to each turtle I created a breed of cities to link the cities to each other.
Expected Results:
As a group, we expect to be able to come up with an algorithm that will calculate the most efficient route possible for someone to take and not have to go through some of the problems others have gone through. Not only that but we will attempt to find the shortest routes to the cities and will end up with some inconvenient routes that will only lengthen the distances.
Citations:
https://www.techopedia.com/definition/22635/traveling-salesman-problem-tsp
http://mentalfloss.com/article/79370/solving-traveling-salesman-problem
https://www.tutorialspoint.com/.../design_and_analysis_of_algorithms_travelling_sales...
mathworld.wolfram.com/TravelingSalesmanProblem.html
https://www.geeksforgeeks.org/top-20-dynamic-programming-interview-questions/
www.math.uwaterloo.ca/tsp/
Team Members: Arath Flores, Carlos Lopez, Melissa Gill, and Ariana Garcia
Sponsoring Teacher: Irina Cislaru
Team Members:
Ariana Garcia
Carlos Lopez Candelas
Melissa Gill
Arath Garcia
Sponsoring Teacher: Irina Cislaru