Networks:
How to Solve the Traveling Salesman Problem
Goal: To understand networks in order to program and solve real world problems.
Breakout Development Team
College: University of Notre Dame ‘22
Major:
Electrical Engineering
Kiera Mallinson
College:
SUNY Polytechnic Institute ‘23
Major:
Mechanical Engineering Technology
Julian Centeno
Gigi Brusco
Edgar Martinez
College:
University of Notre Dame ‘23
Major:
Computer Science & Engineering
College:
Columbia University
Major:
Civil Engineering, B.S.
Industry Experience:
Skanska USA Underpinning and Foundation; John P. Picone Inc.
Part 1:
Introduction to Networks
Network: a group or system of interconnected things
What is a Network?
Found in our brains to connect signals.
Found in delivery systems to get your packages to you in the best way possible.
Found when using “Siri” or “Alexa” to learn new things.
Watch me!
Answer me!
What are 3 takeaways from this video?
Assign the Photos to the Correct Location:
Network
NOT a Network
Cyberspace Security
Internet Network
Cyberspace, or the internet in general, is a network, so network theory can be applied to figure out how to reduce the spread of malware and viruses.
Networks can be applied to many Engineering Grand Challenges...
Source: National Academy of Engineering
Reverse-Engineering the Brain
Neuron Network
Preventing Nuclear Terror
Terror Networks
Your brain is a network of neurons that communicate with one another.
Terror networks around the world are trying to acquire materials which can cause great destruction and terrorize lots of people, so understanding these networks can be done using network theory.
Click
Me!
Part 2:
Traveling Salesman Warm Up
The Traveling Salesman
What is the Shortest Path to fly to each of these cities exactly one time, and then return to your start point?
You are a salesman, who needs to travel to each of these cities in order to drop off packages.
Follow the steps on the next few slides. Note: These steps are also stated in your student instructions.
Step One
Step 1: Go to this link to get started!
The page will look like this.
Step Two
Step 2: Click “Create a New Game”
Step Three
Step 3: Choose a Location (NOT Grid) from “Map”
Then choose 6 cities from “Number of cities”
Then click “Start Game”
Step Four
Step 4: Connect the nodes - or cities - in a complete loop to try to find the optimal (shortest) path, then click “Show Solution” to see if your answer was correct.
Fill me Out!
Step 5: Repeat this process 4 more times to fill out the Table below.
Game | Number of Cities | Was your trip optimal? | Optimal Tour Distance (km) | Your Tour distance (km) | The difference in distance between Your Tour and Optimal (km) |
1 | 6 | YES NO | | | |
2 | 6 | YES NO | | | |
3 | 6 | YES NO | | | |
4 | 12 | YES NO | | | |
5 | 20 | YES NO | | | |
Part 2 Questions:
Answer Me!
What do you notice about the results? Were there any patterns?
What questions do you have about the Traveling Salesman Problem? What do you wonder?
Part 3:
The Traveling Salesman
Click
Me!
How can you solve this problem without the simulator?
This is called a“Graph.” The red dots are “Nodes”
(n – 1)! / 2
n = 9 …20,160 paths
n = 10 …181,440 paths
n = 12 …19,958,400 paths
Number of paths for 3 nodes?
Number of paths for 4 nodes?
Number of paths for 5 nodes?
1
3
12
Number of Paths for n amount of nodes is:
Your Challenge:
How can we find the shortest path to visit these 9 cities: Seattle, LA, Denver, Minneapolis, St. Louis, Houston, Chicago, Atlanta, and NYC?
Follow the steps on the next few slides.
CLICK HERE for a video walk through!
Step One: Go onto this website and use their distance calculator
to find the distance between each pair of the different cities.
Distance Between Each City (mi) | |||||||||
| Seattle | LA | Denver | Minneapolis | Chicago | St. Louis | Houston | Atlanta | NYC |
Seattle | 0 | | | | | | | | |
LA | | 0 | | | | | | | |
Denver | | | 0 | | | | | | |
Minneapolis | | | | 0 | | | | | |
Chicago | | | | | 0 | | | | |
St. Louis | | | | | | 0 | | | |
Houston | | | | | | | 0 | | |
Atlanta | | | | | | | | 0 | |
NYC | | | | | | | | | 0 |
NOTE: there are zeros in a diagonal line - this is because the distance between any city and itself is 0.
Step Two: Use the tool from step 1 to fill out this table.
Make sure the distance is as accurate as possible!
NOTE:
Input your data exactly as you had it in the table in Step Two.
Step Three: Go to this website and input the data from Step Two into a size 9 matrix (9x9).
NOTE:
These are the numbers that correlate with each city in the pattern you were given.
Step Four: After you click the “Calculate” button, the solver gives you the travel sequence for the shortest trip!
Seattle | 1 |
LA | 2 |
Denver | 3 |
Minneapolis | 4 |
Chicago | 5 |
St. Louis | 6 |
Houston | 7 |
Atlanta | 8 |
NYC | 9 |
Order of Cities |
|
|
|
|
|
|
|
|
|
Place your answer in the table below, as well as total miles (which is the red number under the title “Total Traveling Cost”) and total fuel cost. It costs $0.05 per mile for fuel!
Step Five: Put your solution here!
Total Miles Traveled (mi) |
|
Total Fuel Cost ($0.05/mi) |
|
Part 3 Questions:
Answer Me!
What did you find challenging about this problem? What do you feel went well?
Part 4:
Code a Virtual Drone
Type here
Now that you have your path for the Traveling Salesman Problem, it’s time to program your drone to fly that path!
THINK!
What might be some benefits of drones?
Read Me!
Infrared imaging of
solar modules
Applications of Drones in Problem Solving
Law Enforcement
Weather Forecasts
Entertainment
Shipping & Delivery
Wildlife Monitoring
Disaster Management
Geographic Mapping
One recent example of drones in the news is the infrared imaging of solar modules. This photo shows an infrared inspection of a solar plant (“California Valley Solar Ranch”) where they use drones to look for solar panels that are not connected or could cause a fire. These problematic panels are hotter than the others so they look whiter in the photo and it is easier for drones to spot them.
Answer Me!
Choose one of the Applications of Drones in Problem Solving on the previous slide: How do drones help with that specific application?
Use your prior knowledge, words, pictures, video clips, etc. to enhance your answer and explain your thinking.
The Application of Drones
Type here
Pretend you are a software engineer programming for a package delivery company such as FedEx. How would you use the Coding Design Process to program your route?
THINK:
Use this process to help you with coding in the next few slides!
Write code that follows the design made in the previous step
Write Code
How can you go about addressing goals and/or fixing the problems?
Design
Analyze your new code and look for what can be improved
Identify Problems
The Coding Design Process
Your Mission:
Use Scratch to program your drone to follow the solution you found to the TSP in Part 3.
Let’s start coding your drone!
Follow the steps on the next few slides.
Note: These steps are also stated in your student instructions.
1. Go to this link to download the free Scratch program.
2. On the website, click the download option that is compatible with your device (Windows, macOS, etc.) then follow the instructions given on the website from there.
“File” then “Load from your computer” then click on the saved “Drone Simulator.sb3” file to start
How to download Scratch Program:
3. Click on this link and download the file onto your device. NOTE: you will not be able to view the file because it can only be opened using the Scratch application.
4. Open the Scratch application.
5. On the top blue bar of the application click “File” then “Load from Your Computer” then click the file you downloaded in step 3: “Drone Simulator.sb3”
How to use Scratch
Preview Window
Work Space
Blocks Toolbar
1. Drag code blocks from the blocks toolbar to the workspace. Make sure they “snap” into place, and attach to the first block that says “When Clicked”
2. Click the green flag to see your code move the drone in the preview window.
Read Me!
Block | Use |
| This is essentially your "Start button." Anything you connect to this block will be activated when you click the green flag button above your map. |
| Use this block in between landings, so you can clearly see where the drone stops. |
| Use this block to make your drone "fly" from its current coordinates to the coordinates you enter. You will need this to make it travel from one city to another. |
| Use this block to relocate your drone. It will not “glide” like the last block, it will simply appear on the coordinates you program. |
Blocks You Might Use...
Play around with the features of the program:
Explore the Program
Scale: 1 block = 20 “steps” in Scratch
Each block on this grid scales to 20 “steps” in Scratch.
What does this mean?
This means that the distance from Denver to St. Louis is 240 steps away because they are 6 blocks away from each other!
Final Solution
Answer Me!
Record a video on another device (or screen record) your final solution to send your teacher the complete animation of your drone.
Upload Video Here
Answer Me!
Reflection
What part of this lab did you like the most?
Why?
In this lab, each section was related. What were the similarities and differences of each part?
Complete this mandatory, 5-minute Exit Ticket by clicking
here!
If you liked today’s breakout, you may be interested in these topics:
Types of Engineering Relevant to today’s Networks breakout:
Continue to Explore
Additional Resources to Check Out
The Application Network
How Drones Fly
Coding the Traveling Salesperson