Upload your homework document here

This assignment represents various variations in the classic travelling salesman problem. Note that some of the later parts below might not be feasible to do, I am not sure but let me know if you run into problems. This assignment will start with slow direct steps and then become more elaborate.

Steps:

1. Download the files
   
   
   • City Positions this contains the lat and long of the State Capitals in the 48 contiguous states. Remember that the Earth is a sphere. Also note that while there are now "packages" available to do the following you are not supposed to use those, you have to write your own code for this. For instance, there are simulated annealing packages available that you can feed the data to but that is not the point of this exercise at all.
   
   
   
2. Let's start by using 5 cities, Olympia WA, Salem OR, Boise ID, Helena MT, and Sacramento CA.
   
   
   • Write a program that produces a random path that connects all these cities where you pick a starting point at random.
     
     
   • Submit that program along with an image that shows your random route.
     
     
   • Now start in Boise and by brute force code (not clever logic - that comes later) find the minimum length connecting from Boise to the other 4 cities. Submit a table of all the pathway lengths (I think there should be twelve) and indicate the minimum path. Also, record the approximate amount of time it takes to run this (might be very short) and include that.
     
     
   • Now using that same logic as a above, try your code on any randomly selected 7 cities and again on randomly selected 11 cities. Submit the list of cities for each case, the minimum route, and the time it takes to run - Note - this may not work under your brute force approach which means we now have to start thinking.
   
   
   
3. Now select Olympia, Salem and Sacremento for the west coast, Little Rock AK, Madison WI, Lexington KY, Concord NH, Raleigh NC, and Tallahasse Florida. Start your trip in Little Rock.
   
   
   • Using the "greedy algorithm" (nearest neighbor - refer to the You Tube videos in the class notes) construct the pathway that results. submit an image of that pathway along with total distance
     
     
   • Now your to do this Step by Step. From the greedy approach now try the 2 opt approach. Figure out which pairs to swap so that you can produce the "edge" pattern shown in the video. Submit each image along each step until you produce the final pathway
     
     
4. Step 3 was designed to have you practice and understand what your pair swap code (2 opt) is actually doing. Once your confident that it works then try it on all 48 states, starting in either Olympia WA or Augusta ME, to find the 2-opt path length (yes you can look the answer up). Submit your path length diagram (not one you looked up on the internet)
   
   
5. For this last part you will have to find something that tells you state boundaries so that you can tell in which state your path resides in. Note that there are seveal geomap templates outthere with predefined state shapes in them.
   
   
   • Determine the state which have the 3 longest path lengths in them and submit and image of the route through those 3 states
     
     Determine the state which have the 3 shortest path lengths in them and submit and image of the route through those 3 states
     
     
   • Determine the total distance involved in going North, South, East and West Submit those numbers along with routes through those states in which the direction of travel abruptly changes when you reach that capital. Submit your code snippet on how to detect abrupt travel directions