An Efficient Restart Strategy of Local Optimization for the TSP

摘要

Local optimization has been shown to be an effective approach for finding near-optimum solutions to the traveling salesman problem (TSP). Most local optimization based algorithms can be decomposed into three steps: initialization, optimization and restart. Previous research put much emphasis on the optimization step. In this paper, we focus on the restart step. Commonly used restart strategies are reviewed and a more efficient strategy called Hybrid Non-sequential Four-change is proposed. The results show that the alteration of restart strategy has a significant impact on the overall performance. Our improved algorithm is able to arrive at much better solutions in less time.