This is a simple projects that evaluates some TSP solvers:
- Tree state space search optimal solvers
- Nearest-neighbor solvers
- Simulated annealing solvers
- Genetic algorithm
Outcome of the simple nearest-neighbor heuristic:
Ensemble nearest-neighbor followed by ensemble simulated annealing:
Results show that some SA implementations can reach optimal outcomes or very close ones. Meanwhile, chosen popular genetic library does not work satisfyingly.
- Brute force
- Includes branch-and-bound that can optionally be set to result from chosen heuristic
- Serial and multi-threaded parallel variants
- For 15-16 cities time grows to around one minute
It is repeated nearest-neighbor for each possible staring city. Implementation does support multiple cores and scales well.
It has three implementations with different path modification approaches. Main result is that this method does not work when it is started with low quality random state. The best outcomes happen when it is supplied with result of simple construction heuristic, such as nearest-neighbor.
It has low convergence rate.
This method reaches stable state more quickly and with better results.
There has second implementation, Swapping pairs of paths, which de facto has same effect but has significantly lower performance
Due to random nature of SA repeated runs of the algorithm likely will find better result than single run. It is an embarrassingly parallel problem so it can easily scale to large number of cores, albeit with diminishing results.
Jenetics library was used for the implementation. Library has high overhead with such simple problem and has low performance of mutations. Results are significantly worse than simulated annealing.
- Add ant colony optimization
- Research sparse, planar graphs