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.

A Treasure Hunt with Pro-Bot

In this assignment, we shall use Pro-Bot to do a treasure hunt. We shall work with a graph and use XY coordinates to specify the points where the treasures are located. We shall also think of ways of optimizing our paths to get to the various locations.

The minimum distance that Pro-Bot can traverse is 1cm. Hence, the graph paper that you use should have grids of a minimum dimension of 1cm x 1cm. If not, you can always draw your own set of XY axes and put in coordinates 1 cm or more apart. You can then set each step of Pro-Bot to be the distance between successive points on your XY axes. 

Computer Science concepts involved:  Sequential programming, Optimization

Math concepts involved:  XY coordinates, Measuring distances on a graph, Finding shortest path between points, Cost comparison, Angles

Grade levels:  3, 4, 5

Hours required:  1 or more

Compare and Contrast Different Paths for Pro-Bot’s Treasure Hunt

Pro-Bot is going on a treasure hunt. It has been told the coordinates at which the treasures are kept. Can you write the programs for Pro-Bot to get to the treasure?

Let us start with Pro-Bot placed at location (0, 0).

1. The first treasure is located at the coordinates (3, 4). Can you write a program for Pro-Bot to get to this point by traveling only along horizontal and vertical paths (i.e., turns only at 90 degrees)? There are no limits on the number of units of horizontal or vertical distance that Pro-Bot can travel continuously at a time. Remember that Pro-Bot starts its journey from location (0, 0).
2. What is the total distance traveled by Pro-Bot in your above program? Is there a shorter path for Pro-Bot to reach the point (3, 4) from its starting point of (0, 0), if you did not have the condition that Pro-Bot can only travel along horizontal and vertical paths? 
3. Can you write a program for Pro-Bot to travel along your new shorter path to get to the point (3, 4)? Assume that Pro-Bot is facing the X-axis at the start point.
4. If gas costs $3.00 per gallon, and Pro-Bot uses a gallon of gas per step, how much did it cost for gas using your first program? How much did it cost by using your second program with the shorter path? How much money did you save?

     A second treasure for Pro-Bot:

1. There is a second treasure located at the coordinates (6, 8). If Pro-Bot has to pick up the second treasure soon after the first one, what path would it take under the condition that it can only use horizontal and vertical paths (i.e., turns only at 90 degrees)? Can you modify your first program to allow Pro-Bot to pick up both treasures, with the starting point at (0, 0)? 
2. What is the total distance traveled by Pro-Bot now in your above program? Is there a shorter path for Pro-Bot to reach both points ((3, 4) and (6, 8)) from its starting point of (0, 0), if you did not have the condition that Pro-Bot can only travel along horizontal and vertical paths?
3. Can you write a program for Pro-Bot to travel along the shorter path to get to both the points (3, 4) and (6, 8)? Assume that Pro-Bot is facing the X-axis at the start point.
4. If gas costs $3.00 per gallon, and Pro-Bot uses a gallon of gas per step, how much did it cost for gas in your first program where you traveled only along horizontal and vertical paths? How much money did it cost using your second program with the shorter path? How much money did you save?

A Different Spin on Pro-Bot’s Treasure Hunt

Let’s try a variation on our treasure hunt. This time, we have an extra condition:  

Pro-Bot can take only one step (or 1 unit) at a time in any direction. 

For example, to get to a point with coordinates (2, 1), Pro-Bot cannot travel 2 cm straight along the X axis; it can take 1 step horizontally along the X axis, and then move up 1 step and then turn and move 1 step horizontally to get to (2, 1). 

1. Can you write a program for Pro-Bot to get to the treasure at location (3, 4) starting from (0, 0) with the condition that you can take only one step at a time in any direction. Do you travel more distance to get to the treasure under this condition?
2. If gas costs $3 per gallon and Pro-Bot uses a gallon of gas per step, how much does it cost to get to the treasure?
3. Can you write a program for Pro-Bot to get to the treasure at location (6, 8) starting from (0, 0) with the condition that you can take only one step at a time in any direction. 
4. If gas costs $3 per gallon and Pro-Bot uses a gallon of gas per step, how much does it cost to get to the treasure?
5. Can you write a program for Pro-Bot to get to the treasure at location (6, 8) starting from (3, 4) with the condition that you can take only one step at a time in any direction.