A hybrid nearest neighbour and progressive improvement approach for travelling salesman problem

Abstract

The Travelling Salesman Problem (TSP), one of the most famous combinatorial optimisation problems, has been widely studied for half a century now. The state-of-the-art solutions proposed in recent years seem to have focused on the nature-inspired algorithms. While good performance has been reported for many of these algorithms, they are considerably expensive in terms of computation. In this paper, we describe a hybrid solution based on the nearest neighbour algorithm and the progressive improvement algorithm. The nearest neighbour algorithm is a simple search that quickly yields a short tour for TSP, but its solution is usually not optimal. The progressive improvement algorithm, on the other hand, is an improvement strategy that needs to search through a lot of solutions that are near to the current solution, and derives a better one. We conduct experiments with this hybrid approach based on some major cities and towns in Borneo Island. Our experiments show that the hybrid approach is able to produce optimal or near-optimal results consistently for up to 100 cities/towns.