...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>European Journal of Operational Research >Data structures and ejection chains for solving large-scale traveling salesman problems
【24h】

Data structures and ejection chains for solving large-scale traveling salesman problems

机译：解决大规模旅行商问题的数据结构和弹出链

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

摘要

Data structures play a crucial role in the efficient implementation of local search algorithms for problems that require circuit optimization in graphs. The traveling salesman problem (TSP) is the benchmark problem used in this study where two implementations of the stem-and-cycle (S&C) ejection chain algorithm are compared. The first implementation uses an Array data structure organized as a doubly linked list to represent TSP tours as well as the S&C reference structure. The second implementation considers a two-level tree structure. The motivation for this study comes from the fact that the S&C neighborhood structure usually requires subpaths to be reversed in order to preserve a feasible orientation for the resulting tour. The traditional Array structure proves to be inefficient for large-scale problems since to accomplish a path reversal it is necessary to update the predecessor and the successor of each node on the path to be reversed. Computational results performed on a set of benchmark problems up to 316,228 nodes clearly demonstrate the relative efficiency of the two-level tree data structure. (C) 2004 Elsevier B.V. All rights reserved.
机译：数据结构在有效执行局部搜索算法以解决需要图形中电路优化的问题中起着至关重要的作用。旅行推销员问题（TSP）是本研究中使用的基准问题，其中比较了干循环（S＆C）弹出链算法的两种实现。第一个实现使用组织为双向链接列表的Array数据结构来表示TSP巡视以及S＆C参考结构。第二种实现考虑了两级树结构。这项研究的动机来自这样一个事实，即S＆C邻域结构通常需要反转子路径，以便为最终的游览保留可行的方向。传统的数组结构被证明对于大规模问题效率低下，因为要完成路径反转，必须更新要反转的路径上每个节点的前任和后继。对多达316,228个节点的一组基准问题执行的计算结果清楚地表明了两级树数据结构的相对效率。 （C）2004 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号