If you don't already have all the source files in one place, you can download them here. From a command prompt type the following command:

javac -classpath .;OpenTS.jar *.java

That will generate several .class files in your current directory.

The command to run the code is very similar:

java -classpath .;OpenTS.jar Main

You should get something like the following on your screen:

Best Solution:
Solution value: 1025.509594617172
Sequence: [ 0, 4, 7, 6, 1, 8, 5, 12, 3, 13, 10, 
           16, 9, 2, 11, 19, 15, 14, 17, 18 ]
72.36062143209436	186.5986970577082
31.65330865904046	153.7776120384018
66.51727939444739	138.50626840743809
162.0462546930939	95.58307450675024
166.61826979420474	65.29515124758525
183.24577341373626	70.1724467685417
189.01469154596148	13.117008144132146
139.21366507607408	9.466871801969523
89.61552653863036	127.6305887567737
40.14429295263602	170.02917644462565
20.55498011060317	188.8716672695299
20.536646263235212	118.30519471918417
18.04865566274256	111.08005478256575
47.10475812952504	69.82307132497667
38.836647995939465	50.70319761183606
17.932880938130214	37.87442743261589
31.20277975254271	13.327835551901067
79.60378594606847	46.333632353910794
75.55484518831904	99.13175164522798
119.3827892351382	182.30827271981533

You might be wondering if this is a good solution. A quick trip to Excel gives us this chart of the solution. If you get something that looks like this then you got it right.

You may notice some obvious problems with the solution and say, "I could have done better with a pencil and paper!" Good, you're thinking. The tabu search we just built is embarrassingly primitive, but the premise of tabu search is that we can model a heuristic after the way humans think.

Think about how you search for things and make an analogy to tabu search. Here are some things people have tried:

Reactive Tabu List

Vary the tabu list tenure in response to how well the search is progressing. If you're "on a roll" finding many good solutions, the tabu list only gets in the way, so you can shorten the tenure. If you find yourself trapped in a local optima you can increase the tenure forcing your search to make unimproving moves while it moves to another area of the solution space.

Intensification and Diversification

Not techniques so much as classifications of techniques, the idea is to spend more effort on areas of the solution space that show promise and move to far corners of the solution space when you hit a dead end. A Reactive Tabu List is one way to explicitly address Intensification and Diversification.

Elite Solution Lists

Keep a record of the top 10 or so solutions and devote some iterations at the end of the run to intensifying your search around those solutions.

Jump Search

Similar to Elite Solution Lists, instead of using Tabu Search to generate several good solutions, use a known heuristic - especially one with variable parameters - to generate several good solutions, and then perform a Tabu Search from each of these starting points. Even if you don't make a list of starting solutions you may want to at least not start with a trivial solution as we did in this tutorial. Try this MyGreedyStartSolution (only need to change the one line in Main.java) to see how that improves your solutions.