摘要
本文对Marinakis等提出的扩展邻域GRASP算法进行改进。首先使用最近α值方法构造初始TSP回路,然后运用混合的局部搜索即2-opt算法、双桥策略和3-opt算法来改进初始回路,并且引进α-nearness候选集和don’t-lookbit技术来提高搜索速度。实验结果表明,本文提出的GRASP能够在合理的时间内得到很好的解,并且解的质量优于Marinakis等提出的扩展邻域GRASP算法得到的解。
In this paper we propose an improved GRASP algorithm for the traveling salesman problem. Starting with the nearest α-value method to construct an initial 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 increase the local search speed, the a-nearness candidate set and don＇t-look bit techniques are introduced. The computational results show that the proposed 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.
出处
《计算机工程与科学》
CSCD
2008年第11期60-64,共5页
Computer Engineering & Science
基金
国家自然科学基金资助项目(60773126)
福建省自然科学基金资助项目(2006J0030)
