A Study on Greedy Search to Improve Simulated Annealing for Large-Scale Traveling Salesman Problem

摘要

Traveling salesman problem (TSP) is a typical NP-hard problem. How to design an effective and efficient algorithm to solve TSP within a limited time is of great theoretical significance and practical significance. This paper studies how the greedy search improves simulated annealing algorithm for solving large-scale TSP. First, the TSP formulation is presented. The aim of the TSP is to structure a shortest route for one traveling salesman starting from a certain location, through all the given cities and finally returning to the original city. Second, a simple simulated annealing (S A) algorithm is developed for the TSP. The orthogonal test is employed to optimize the key parameters. Third, a group of benchmark instances are tested to verify the performance of the SA. The experimental results show that for the small-scale and medium-scale instances the simply SA can search the optimal solution easily. Finally, to solve the large-scale instance, we integrate a greedy search to improve SA. A greedy coefficient is proposed to control the balance of the exploration and the exploitation. Different levels of the greedy coefficient are tested and discussed. The results show that the greedy search can improve SA greatly with a suitable greedy coefficient.