This assignment is based on the definition of the Traveling Salesperson Problem (the TSP): Given a set of cities, you want to find the shortest route that visits every city and ends up back at the original starting city. For the purposes of this problem, every city will be directly reachable from every other city (think flying from city to city). Your goal is to use a non-genetic local search algorithm or algorithms from Chapter 4 of Poole & Mackworth to find the shortest paths that you can. Note that for any reasonably sized problem, you will not be able to try every possibility, and so you won’t ever know when you have the shortest possible path. You should have two types of output: Summary Mode and Verbose Mode. Verbose Mode should print to a file every path you try until your program terminates. Summary mode, which prints to the console, should print a path only when that path is better than any path that you have found previously. In all cases, print the single-letter mnemonic of the city (Node), not its full name.
Suggestions
You can start from any city you want, it really doesn’t matter which. For example, you can start from the first city in the file, since it is the easiest. Create some tours. You can do this randomly, or you can use a greedy algorithm of some sort, or you can just visit the cities in the order they appear in the file, whatever you prefer. Your choice probably won’t affect the goodness of your final tour, but it might affect how long it takes you to get to a good solution. Selecting and using the techniques of local search, try to find a better tour. Be sure to document what you’re trying to do. The rest of this section assumes you want to create your own algorithm. Here are some thoughts on what is probably the main question: how to step from one possible tour to the next.
One option would be two swaps the order of two cities and see if this shortens the tour
Mpls. => Seattle => Detroit => Boston => Chicago => Miami => Denver => Mpls.
Or you could pick one city in the tour, and try removing it and inserting it between every pair of cities to see which gives the shortest tour.
There are other forms of Iterative Best Improvement, too.
When deciding what cities to swap or what city to shuffle, you could use either a 1-stage or 2-stage choice algorithm.
With any sort of iterative best improvement, there are various techniques you could use if you wish. One of the big differences among peoples’ algorithms will be their choices to use or not use these techniques, and the algorithm they use to decide when to use them (for example, how often to do a random step or restart, temperatures for simulated annealing, etc.)
• You could choose to use Simulated Annealing to decide whether to keep a given tour even if it’s longer than the existing tour.
• You could inject randomness by sometimes making random permutations (random walk).
You could decide after a certain number of iterations that you should just start over from scratch with a random order of cities (random restart).
• You could choose to keep a tabulation list or not, and if you do, you could choose its size.
• You could keep multiple tours, and permute them in parallel (beam search).
Since you don’t actually know when you have an optimal tour for any reasonably sized problem, you need to decide on a stopping criterion. Some possible suggestions:
• Stop after some number of steps (where the number of steps might be some function of the number n of cities).
• Stop after you have gone some number k of steps without improving on your best answer.
• Stop after the program has run for some amount of real-time (measured by something like System. time. millis()).