Incremental Improvement for Sub-optimal Euclidean TSP Paths Generated by Traditional Heuristics

摘要

This paper proposes and tests three simple algorithms that are capable of rapidly improving non-optimal paths for the Euclidean Travelling Salesman Problem (TSP).The ETSP is a special case of the more general TSP, but it still plays a very important part of planning and scheduling. For example, it can be used to optimise CNC tool paths. There is no known polynomial solution for the ETSP (nor for any of the other TSP problems), so various approximation heuristics were proposed over the years.Many advancements were made in the past 10 years. For example, CONCORDE [1] and LKH [2] are two of the most important publicly available implementations that are able to find optimal solutions for graphs up to a few thousand nodes. However, the runtime to find the optimal solution is very long for large graphs. In the case where the application can afford an approximate solution, it is convenient to improve one of the classical heuristic solutions, namely, Nearest neighbour, Greedy and Insertion.The cheapest of the improvement heuristics is 2opt, followed by a generalisation of the former, k-opt.The objective of the three proposed algorithms is to find an improved non-optimal suitable solution in a relatively short time, at least much shorter than the well-known 2-opt or k-opt improvement algorithms. This is of course a compromise, as the improvements are much further away from the optimal path. In many cases k-opt approaches can find optimal solutions, but the runtime can be very long.The three proposed algorithms improve an existing heuristic solution in polynomial time. The first algorithm unravels crossing edges in an sub-optimal path. The second algorithm moves nodes that are closer to edges, improving the path. The third algorithm uses a K-nodes optimiser to stretch small parts of the path.The experiments were carried out using the TSPLIB instances [3] for the instances that are Euclidean (and therefore, symmetric). The results show that one can quickly improve paths obtained using one of the well-known polynomial time heuristics. The proposed algorithms yield better paths than 2-opt paths in more than half of the Euclidean TSPLIB instances. Also, the runtime of the proposed algorithms is much shorter than 2-opt for graphs with more than 100 nodes. It is 2 to 10 times faster than running 2-opt.