...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Optimization >Multiple phase neighborhood Search—GRASP based on Lagrangean relaxation, random backtracking Lin–Kernighan and path relinking for the TSP
【24h】

Multiple phase neighborhood Search—GRASP based on Lagrangean relaxation, random backtracking Lin–Kernighan and path relinking for the TSP

机译：多相邻域搜索-基于Lagrangean松弛的GRASP，随机回溯Lin–Kernighan和TSP的路径重新链接

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper, a new modified version of Greedy Randomized Adaptive Search Procedure (GRASP), called Multiple Phase Neighborhood Search—GRASP (MPNS-GRASP), is proposed for the solution of the Traveling Salesman Problem. In this method, some procedures have been included to the classical GRASP algorithm in order to improve its performance and to cope with the major disadvantage of GRASP which is that it does not have a stopping criterion that will prevent the algorithm from spending time in iterations that give minor, if any, improvement in the solution. Thus, in MPNS-GRASP a stopping criterion based on Lagrangean Relaxation and Subgradient Optimization is proposed. Also, a different way for expanding the neighborhood search is used based on a new strategy, the Circle Restricted Local Search Moves strategy. A new variant of the Lin-Kernighan algorithm, called Random Backtracking Lin-Kernighan that helps the algorithm to diversify the search in non-promising regions of the search space is used in the Expanding Neighborhood Search phase of the algorithm. Finally, a Path Relinking Strategy is used in order to explore trajectories between elite solutions. The proposed algorithm is tested on numerous benchmark problems from TSPLIB with very satisfactory results.
机译：本文针对旅行商问题提出了一种新的改进版本的贪婪随机自适应搜索程序（GRASP），称为多相邻域搜索—GRASP（MPNS-GRASP）。在该方法中，经典GRASP算法中包含一些过程，以提高其性能并解决GRASP的主要缺点，即它没有停止准则，该准则不会阻止算法花费时间进行迭代，对解决方案进行较小的改进（如果有的话）。因此，在MPNS-GRASP中，提出了基于拉格朗日松弛和次梯度优化的停止准则。同样，基于新策略“圈子限制本地搜索移动”策略，使用了不同的扩展邻域搜索的方式。 Lin-Kernighan算法的一个新变种，称为随机回溯Lin-Kernighan，可以在算法的扩展邻域搜索阶段中使用它来帮助算法使搜索空间的非有希望区域中的搜索多样化。最后，为了探索精英解决方案之间的轨迹，使用了路径重新链接策略。该算法在TSPLIB的众多基准测试问题上进行了测试，结果令人满意。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号