The Traveling Salesman Problem is one of the most famous and one of the most complex in Computer Science. The problem can be cited as the following: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the starting city?
This problem in its various forms has a variety of applications in multiple fields for optimization purposes. For example, a school district would like to find the best route for a school bus to pick up kids in the morning. The courier company would like to determine the best route to drop off packages, with minimum fuel costs. In a factory assembly line, if you can find a way to visit all the required stations in minimal time, you can manufacture more units in a day. There are several more instances of the application of this problem and the “cities” in the original problem will denote various points in those instances. As the number of “cities” increases, the complexity of the problem also increases.
We shall work on a very simple instance of the above problem, involving a maximum of just 5 cities. Pro-Bot shall represent our salesman, driving between the various cities.
Computer Science concepts involved: Sequential programming, A peek into optimization techniques
Math concepts involved: Using data given for creating a graph, Measuring distances and directions on a map, Finding shortest path, Cost comparison, Measuring angles, Scaling quantities
Grade levels: 4, 5
Hours required: 2 or more
Hours required: 2 or more
Distance between cities in miles
The distances between the various cities are given in the table below in miles. Note that these are straight line distances between the cities (as the crow flies) and not driving distances.
On a map of USA, locate the various cities given in the table above.
Task 1
We shall start with a very simple route. Let’s consider the three cities of San Diego, Austin and Denver. Pro-Bot has to visit all three cities, starting from San Diego and returning to San Diego. No city other than San Diego should be visited more than once. What order should the cities be visited in so that the total distance traveled is minimized?
Remember that the minimum distance Pro-Bot can draw is 1cm. Given the distances in the table above and using a scale of 1 cm to represent 100 miles, can you round the distances so that they can be used by Pro-Bot? Draw a small graphical representation of your cities and distances between them as shown below. This might be helpful for you to visualize the problem.
Using a map of the USA and a protractor, try to find out the angular measurements between the various cities (approximate values are fine). Using the distance and angular information, as well as the location of the various cities on the map, can you write a program for Pro-Bot to visit all three cities, starting and ending at San Diego?
If gas costs $3 a gallon and Pro-Bot uses one gallon per 10 miles, how much did it cost for the trip?
Task 2
We shall move on to a route that involves 4 cities now: San Diego, Austin, Denver and Chicago. Pro-Bot has to visit all four cities, starting from San Diego and returning to San Diego. No city other than San Diego should be visited more than once. What order should the cities be visited in so that the total distance traveled by Pro-Bot is minimized?
Remember that the minimum distance Pro-Bot can draw is 1cm. Given the distances in the table above and using a scale of 1 cm to represent 100 miles, can you round the distances so that they can be used by Pro-Bot? Draw a small graphical representation of your cities and distances between them as we did in the previous task. This might be helpful to visualize the problem.
Using a map of the USA and a protractor, try to find out the angular measurements between the various cities (approximate values are fine). Using the distance and angular information, as well as the location of the various cities on the map, can you write a program for Pro-Bot to visit all four cities, starting and ending at San Diego, so that the total distance traveled is kept to a minimum?
If gas costs $3 a gallon and Pro-Bot uses one gallon per 10 miles, how much did it cost for the trip?
Task 3
We shall work on a route that involves 5 cities now: San Diego, Austin, Denver, Chicago and Las Vegas. Pro-Bot has to visit all five cities, starting from San Diego and returning to San Diego. No city other than San Diego should be visited more than once. What order should the cities be visited in so that the total distance traveled by Pro-Bot is minimized?
Remember that the minimum distance Pro-Bot can draw is 1cm. Given the distances in the table above and using a scale of 1 cm to represent 100 miles, can you round the distances so that they can be used by Pro-Bot?
Using a map of the USA and a protractor, try to find out the angular measurements between the various cities (approximate values are fine). Using the distance and angular information, as well as the location of the various cities on the map, can you write a program for Pro-Bot to visit all four cities, starting and ending at San Diego, so that the total distance traveled can be kept to a minimum?
If gas costs $3 a gallon and Pro-Bot uses one gallon per 10 miles, how much did it cost for the trip?
A few points to think about:
For each of the tasks above, does this change in the conditions cause a change in the route?
Task 4:
Pro-Bot visits San Diego, Austin and Denver, starting from San Diego. The distances between the cities and the gas prices are the same as before. You do not have to return to San Diego. Can you write a program for Pro-Bot’s route that involves the minimum gas cost? Is it the same route as in Task 1?
Task 5:
Pro-Bot visits San Diego, Austin, Denver and Chicago, starting from San Diego. The distances between the cities and the gas prices are the same as before. You do not have to return to San Diego. Can you write a program for Pro-Bot’s route that involves the minimum gas cost? Is it the same route as in Task 2?
Task 6:
Pro-Bot visits San Diego, Austin, Denver, Chicago and Las Vegas, starting from San Diego. The distances between the cities and the gas prices are the same as before. You do not have to return to San Diego. Can you write a program for Pro-Bot’s route that involves the minimum gas cost? Is it the same route as in Task 3?
The distances between the various cities are given in the table below in miles. Note that these are straight line distances between the cities (as the crow flies) and not driving distances.
City Name City Name Distance in miles
On a map of USA, locate the various cities given in the table above.
We shall start with a very simple route. Let’s consider the three cities of San Diego, Austin and Denver. Pro-Bot has to visit all three cities, starting from San Diego and returning to San Diego. No city other than San Diego should be visited more than once. What order should the cities be visited in so that the total distance traveled is minimized?
Using a map of the USA and a protractor, try to find out the angular measurements between the various cities (approximate values are fine). Using the distance and angular information, as well as the location of the various cities on the map, can you write a program for Pro-Bot to visit all three cities, starting and ending at San Diego?
We shall move on to a route that involves 4 cities now: San Diego, Austin, Denver and Chicago. Pro-Bot has to visit all four cities, starting from San Diego and returning to San Diego. No city other than San Diego should be visited more than once. What order should the cities be visited in so that the total distance traveled by Pro-Bot is minimized?
We shall work on a route that involves 5 cities now: San Diego, Austin, Denver, Chicago and Las Vegas. Pro-Bot has to visit all five cities, starting from San Diego and returning to San Diego. No city other than San Diego should be visited more than once. What order should the cities be visited in so that the total distance traveled by Pro-Bot is minimized?
- As you worked on the above 3 tasks, did you notice that as the number of cities increased, your job of finding the route with minimum cost also became more complex?
- Was there a particular technique that you used for finding the minimum cost route in each case?
- Or did you evaluate all possible routes in each task and then choose the best one to write your program for? Do you think that it would be a good solution for a large number of cities, say 1000 or 10,000 or so?
- Can a change in constraints lead to a change in the routes that you found? Check the next section for an example.
A Different Condition & A Different Route:
Now, imagine that Pro-Bot is a rental car that you picked up at the San Diego airport. You shall use Pro-Bot to visit various cities starting from San Diego. We would still like to keep our distance and gas costs to a minimum and visit each city only once. But this time, Pro-Bot does not need to return to San Diego after visiting all the cities. You can it drop off at the last city that you visit.Pro-Bot visits San Diego, Austin and Denver, starting from San Diego. The distances between the cities and the gas prices are the same as before. You do not have to return to San Diego. Can you write a program for Pro-Bot’s route that involves the minimum gas cost? Is it the same route as in Task 1?
Pro-Bot visits San Diego, Austin, Denver and Chicago, starting from San Diego. The distances between the cities and the gas prices are the same as before. You do not have to return to San Diego. Can you write a program for Pro-Bot’s route that involves the minimum gas cost? Is it the same route as in Task 2?
Pro-Bot visits San Diego, Austin, Denver, Chicago and Las Vegas, starting from San Diego. The distances between the cities and the gas prices are the same as before. You do not have to return to San Diego. Can you write a program for Pro-Bot’s route that involves the minimum gas cost? Is it the same route as in Task 3?
No comments:
Post a Comment