关键词: 旅行售货商问题 贪心随机适应性搜索算法 局部搜索算法 候选集

Abstract:

In this paper we propose an improved GRASP algorithm for the traveling salesman problem. Starting with the nearest α-value method to construct an ini tial TSP tour,we apply a hybrid local search method, i. e. , the 2-opt, the doublebridge and the 3-opt methods for the initial tour improvement. To incr ease the local search speed, the a-nearness candidate set and don＇t-look bit techniques are introduced. The computational results show that the propose ed GRASP gives fairly good solutions in a reasonable time,and the quality of solutions is better than that of the expanding neighborhood GRASP proposed    by Marinakis et al.

Key words: traveling salesman problem;greedy random adaptive search procedure, local search, candidate set