CIT 594 Assignment 10: Travelling Salesman
Spring 2011, David Matuszek

Purposes of this assignment

• To give you more experience with Threads
• To give you some experience with synchronization and shared state
• To give you some experience with Timers

General idea of the assignment

“Solve” the Travelling Salesman problem.

In this instantiation of the problem, a salesman wants to visit each of the 50 U.S. state capitals, then return to his starting point. He wants to cover the minimum total distance (also called the cost) when doing so. No city can be visited more than once. Plan his route.

The word “solve” is in quotation marks because you won’t be able to find the optimum route. This is because there are 50! possible paths (actually 49!, since the path is a cycle, and any city can be used as the starting point.) With problems of this type, we can easily find ways to reduce the number of permutations to consider, but these reductions still result in an algorithm that is essentially O(n!).

The putative goal of this program is to find the best possible route (if you get under 18000 miles, you are doing well), but the real goal is to make a Thread-safe program to do it.

Details

I am providing the following:

• A file state-capitals.txt of capital cities, along with their latitudes and longitudes. The format is one city per line, where each line is:
        state name<tab>city name<tab>latitude<tab>longitude.
• A City class; each instance of this class will hold the information about a single city. Cities will be numbered sequentially, starting from 0, in the order they are created. The class also contains some useful methods.
• A SolutionSaverAndChecker class that extends Thread. To use this class,
  • Early in your program, call the class’s static init() method; this will ask you for a file on which to store results.
  • Each time you find a better path than any found previously, create and run a new SolutionSaverAndChecker thread.
  You should modify this class as little as possible, preferably only by adding synchronization where necessary.

You should make a travellingSalesman package, containing:

• A TravellingSalesman class with a main method. The code in this class should:
  • Declare a final static City[] sharedCityArray variable.This will be shared state.
  • Read in the data file of cities.
    • (The total distance required to visit the states in alphabetical order should be 58803 miles.)
  • Call SolutionSaverAndChecker.init() to choose the output file.
  • Create and start 10 or 12 Worker threads.
  • Create a QuitTimer, telling it how long (in seconds) the program should run. (Set this to 30 seconds or less before you turn the program in!)
  • When all Worker threads have finished, print out the final order of cities, and the total distance.
• A QuitTimer class that extends java.util.Timer.
  • An object of this class should run for some specified number of seconds, then tell all the Worker threads to stop.
• A Worker class that extends Thread.
  • When a worker Thread is constructed, it should make a copy of the sharedCityArray, and compute the total distance for that array.
  • The run() method should go into an infinite loop, doing the following:
    • Try to find a better arrangement (less total distance) of the cities. When one is found:
      • Print out the newly found distance.
      • Compare the newly found arrangement to the current arrangement of cities in the sharedCityArray:
        • If the newly found arrangement is better, copy the cities to the sharedCityArray.
        • If the newly found arrangement is worse (because the sharedCityArray has been updated by some other worker since you last saw it), copy the cities from the sharedCityArray to use as a new starting point.
    • Quit when the QuitTimer says to quit.

Notes

Shared state will result in errors if:

• A thread is interrupted partway through updating the state, and
• Another thread reads or updates the state.

To encourage such errors to occur, I need a method that is so  s l o w  that it is likely to be interrupted. This is harder than it sounds, because each Thread can execute thousands or millions of instructions between interruptions. In this assignment, SolutionSaverAndChecker.run() is an appropriately slow method: it loops through the sharedCityArray, printing each City to an unbuffered PrintStream, and accumulating information about that City as it goes. By the time it finishes printing, the data in sharedCityArray may have changed. Do not speed this method up, or give it a copy of the shared array. Instead, use synchronization to solve the problem.

The basic job of a Worker thread is: Rearrange cities until you find a better ordering, then compare it to the ordering in sharedCityArray. Copy the better ordering into the less good one, then do it all over again.

How do you find a better ordering? For this assignment, I recommend using a random number generator, and making random small changes in the ordering until you happen to find a better ordering. There is plenty of time to try a few million orderings. If you want to explore the extensive literature on the Travelling Salesman problem, that’s okay too, so long as your Worker threads aren’t all doing the same work.

Sample output

Here's a portion of output from my program. Your output should provide the same kind of information.

 0  Montgomery, Alabama       [32.3615, -86.2791]
 1  Juneau, Alaska            [58.3019, -134.4197]
 2  Phoenix, Arizona          [33.4485, -112.0738]
 ...
48  Madison, Wisconsin        [43.0747, -89.3844]
49  Cheyenne, Wyoming         [41.1455, -104.8020]

Total distance = 58803.517735751055

Worker 1 found a better distance on trial 2:  57415.875153771
Worker 1 found a better distance on trial 12:  57388.76286745295
Worker 1 found a better distance on trial 13:  57184.80580373073
...
Worker 6 found a better distance on trial 49:  50580.94449533747
ERROR! Cities have been duplicated or omitted!
Expected city sum = 1225
Actual city sum   = 1312
Difference        = 87
ERROR! Reported distance is 47275.212601280495 but actual distance is 53330.7747242515!
Worker 6 found a better distance on trial 51:  50520.923362174195
...

All done!

 8  Tallahassee, Florida      [30.4518, -84.2728]
 ...
17  Baton Rouge, Louisiana    [30.4581, -91.1402]
Total distance = 23559.759298308334

Due date