TSP问题的一种改进的GRASP算法

摘要：

本文对Marinakis等提出的扩展邻域GRASP算法进行改进.首先使用最近a值方法构造初始TSP回路,然后运用混合的局部搜索即2-opt算法、双桥策略和3-opt算法来改进初始回路,并且引进a-nearness候选集和don”t-lookbit技术来提高搜索速度.实验结果表明,本文提出的GRASP能够在合理的时间内得到很好的解,并且解的质量优于Marinakis等提出的扩展邻域GRASP算法得到的解.

关键词： 旅行售货商问题 搜索算法 局部搜索 搜索速度 扩展邻域

作者: 郑雅燕 朱文兴

作者单位: 福州大学数学与计算机科学学院,福建,福州,350002 福州大学离散数学与理论计算机科学研究中心,福建,福州,350002

会议类型: 国内会议

会议名称: 2008年全国理论计算机科学学术年会

会议地点: 西安

会议语种:中文

页码: 60-64

在线出版日期: 2008-09-19（万方平台首次上网日期，不代表论文的发表时间）