View paper here.
The travelling salesman problem (TSP) is one of the most studied optimisation problems and has numerous applications, ranging from the drilling of printed circuit boards to route planning and logistics. This paper applies simulated annealing (SA), a heuristic method for approximating global optimums, to the TSP. A sequential implementation is provided as a benchmark, on which a number of optimisations are made. A parallel approach is implemented and its performance overheads investigated.