Traveling Pro-Bot: Finding the shortest path

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

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. 

                     City Name                            City Name                      Distance in miles

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:

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

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?

Transmit Electricity with Minimum Loss from the Power Plant to the Cities

In this programming assignment, we shall work on finding the shortest path to reach a point on the XY plane. We shall then write a program for Pro-Bot to travel along the shortest path that we found. This is a peek into the world of optimization, comparing and contrasting various solutions to a problem and choosing the best one that fits our needs and constraints. 

Your task is to find the paths to the various points on the XY plane, given the XY coordinates. Next, compare and contrast the cost options for the different paths and choose the best one that meets the constraints. Once you have found the best option, determine the  distances and angles at which Pro-Bot has to make turns, in order to traverse the path and write your program. 



Computer Science Concepts involved:   Sequential programming, Optimization

Math concepts involved:   Right triangles, Coordinates on XY plane, Measuring distances between points given (x, y) coordinates, Angles,  Finding shortest paths

Grade levels:   4, 5

Hours required:   1

Programming Assignment

Electricity is generated in power stations and then it gets transported to various cities for distribution to the consumers. Not all of the electricity that gets generated will reach the consumer. Several losses occur along the way on the distribution network. The power company would like to keep the distribution losses at a minimum as the consumers do not pay for it. 

Here is a set of coordinates given, representing 3 cities X, Y and Z and the power generation station at point A. 

Power is generated at location A and then transported to the cities. For each unit of distance between the points, 1 Kilowatt-hour of energy is lost (Kilowatt-hour is a unit  used to measure energy). Your task is to find the best option for drawing electric lines between the power station and the cities, which will have minimum total loss of electric power during transmission.

Your options are: 

(a) to have direct power lines drawn from A to the cities separately or 

(b) draw power lines from A to a city and then draw more power lines from that city to the next and so on. 

Given the coordinates of the cities and the power station, can you find the shortest distances between them? Use the values that you found to calculate the amount of electrical energy that is lost during transmission to the various cities. Which option do you think would work better, option (a) or option (b) as given above? 

Compare all options to see which approach can minimize the total loss of power during transmission from the power station A to all three cities X, Y and Z. 

If Pro-Bot is driving along the path that provides the minimum loss of electricity, starting from point A and visiting all three cities, can you write a program to trace Pro-Bot’s path? Assume that Pro-Bot is at the point (0, 0) and facing the X axis when it starts its journey.