J4 ›› 2008, Vol. 30 ›› Issue (11): 60-64.
• 论文 • 上一篇 下一篇
郑雅燕[1] 朱文兴[2]
出版日期:
发布日期:
Online:
Published:
摘要：
本文对Marinakis等提出的扩展邻域GRASP算法进行改进。首先使用最近α值方法构造初始TSP回路，然后运用混合的局部搜索即2-opt算法、双桥策略和3-opt算法来改进初始回路，并且引进α-nearness候选集和don’t-lookbit技术来提高搜索速度。实验结果表明，本文提出的GRASP能够在合理的时间内得到很好的解，并且解的质量优于M~rinakis等提出的扩展邻域GRASP算法得到的解。
关键词: 旅行售货商问题 贪心随机适应性搜索算法 局部搜索算法 候选集
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
郑雅燕[1] 朱文兴[2]. TSP问题的一种改进的GRASP算法[J]. J4, 2008, 30(11): 60-64.
0 / / 推荐
导出引用管理器 EndNote|Ris|BibTeX
链接本文: http://joces.nudt.edu.cn/CN/
http://joces.nudt.edu.cn/CN/Y2008/V30/I11/60
