The Traveling Salesman Problem

The problem description is given in the class:
http://cs.nyu.edu/courses/Fall12/CSCI-GA.2965-001/travelingsalesman.html

From a graph perspective, this problem can be brief as:

Given a complete weighted graph (where the vertices would represent the cities, the edges would represent the roads, and the weights would be the cost or distance of that road), find a Hamiltonian cycle with the least weight.

To traverse all posible city sequence and find the best solution (optimal distance score), time complexity is as high as factorial time O(n!) with simplest recursion. Or to make things simpler, try use dynamic programming to reduce a great amount of efforts and get almost 30 cities run on my laptop.

Many strategies and heuristic are used to solve this problem, such as minimum matching and Simulated Annealing. We chose to use Simulated Annealing as our base algorithm for its flexibility to do optimization.

One general idea is to obtain the Minimum Spanning Tree (MST). For the baseline by traversing every nodes on the MST twice, we get solution up to 2*score of the shortest path. In the input provided, the shortest path of MST is ~625,000 miles, so our baseline is ~1,250,000.

Step 1
Consider the distance score  = sigma^n d[i][j], where n is total number of cities, d[i][j] is distance from city i to city j. And consider score_i = score after the ith iteration.

The primitive version is to randomly generate a city sequence. Then swap 2 cities in each iteration. The score will be updated (accepted) if the score_(i+1) < score_i || (score_(i+1) - score_i)/T > R(0, 1). 

The good thing about this algorithm is that it is really simple, and it allows worse result in order to search a larger solution space. This gives a result ~1,200,000, which is almost the same as the baseline with time limitation of 2 min. :( What can be realized is that this way doesn't shuffle the city sequence a lot as we swap every two cities at a time. So By swapping two fixed length of cities in the sequence as below:

ab1234cde5678fg

ab5678cde1234fg

Here the numbers are cities that are going to be swapped, where letters are cities stay in their current position. But still this doesn't make a lot improvement. So instead of swapping fixed length sub-sequence, we make the length arbitrary as below:

ab123cde45678fg

ab45678cde123fg

With this method and a lot of code optimization, we successfully reduce the score into 960,000. 

We don't shuffle inside the chosen sub-sequence is because that will cause more calculation of the distance score, thus reduce the number of iteration we can run. As in Simulated Annealing, it is guaranteed that with unlimited amount of time,  the optimal score should be obtained. That means we have two ways to improve our algorithm: one is to optimize our swapping (replacement) strategy, the other is to make the iterations to run as many as possible.

Step 2

As to the second one, we make the start sequence as reasonable as possible to avoid random solutions that actually make score worse by accepting bad scores. So we use the Depth First Search of MST as our initial sequence, instead random generalization. During the DFS, if the node in the tree has been visited, we skip and continue searching the whole tree. 

Also, we optimize our random() method by bit manipulation instead of Java.util.Random. This makes three times of iterations as before and start with 970,000 instead of very random scores larger than 1 million. 

Another method is that, after lowering the temperature several times to a low value, we only accept better scores, regardless of the probability of worse scores might generate larger solution space. Then we found the cooling temperature and the acceptance probability becomes not that important because we have already begun with an very small value, so accepting worse values will be meaningless even if we might be easy to get into local minimal solution. So we only accept the better scores through all iteration.

Step 3

As to the first one. We developed a different replacement method. The strategy is described as follow:

1. Save all the neighbors of the city sorted from the nearest to the farthest;
2. Randomly pick a start point a of the sequence;
3. Randomly pick b from the closest 4 neighbor cities around a, which the probability decrease from the closest to the farthest.
4. Reverse the sub-sequence of the city sequence start from city next to a to b.

For example:

abc12345defg

abc54321defg

Consider the start point we choose is c, and 5 is one of the closest 4 cities to c. So we reverse the sub-sequence from the point next to c, which is 1, to 5. Why this should work? Because you are trying to get a better path by making the almost closest cities to be the next city to travel, so this is much better heuristic than trying to do reverse randomly. We are not using the closest one because this will let the model go into local optima easily.

This simple model successfully beat all other 9 teams in our class. It wins because of the ability to run extremely fast by optimize every operation, and the heuristic of initialization and replacement. Anyone with different or better solution is welcomed to discuss with us.

Our code is on GitHub and running command is just (Consider the input file is the same directory as the  java files)

javac SAOpt.java MST.java

java SAOpt