...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Opsearch: Journal of the Operational Research Society of India >A minimum spanning tree based heuristic for the travelling salesman tour
【24h】

A minimum spanning tree based heuristic for the travelling salesman tour

机译：基于跨越的旅游推销局跨越式启发式

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

摘要

Abstract This paper presents a heuristic to find the travelling salesman tour (TST) in a connected network. The approach first identifies a node and two associated arcs that are desirable for inclusion in the required TST. If we let this node be denoted by $$p$$ p and two selected arcs emanating from this node be denoted by $$left( {p,q} ight),{ext{and}},left( {p,k} ight),$$ p , q and p , k , then we find a path joining the two nodes $$q,{ext{and}}, k$$ q and k passing through all the remaining nodes of the given network. A sum of these lengths, i.e. length of the links $$left( {p,q} ight),{ext{and}},left( {p,k} ight)$$ p , q and p , k along with the length of the path that joins the nodes $$q,{ext{and}}, k$$ q and k passing through all the remaining nodes will result in a feasible TST, hence gives an upper bound on the TST. A simple procedure is outlined to identify: (1) the node $$p$$ p , (2) the two corresponding links $$left( {p,q} ight),{ext{and}},left( {p,k} ight),$$ p , q and p , k , and (3) the path joining the nodes $$q,{ext{and}}, k$$ q and k passing through all the remaining nodes. The approach is based on the minimum spanning tree; hence the complexity of the TST is reduced. The network in the present context has been assumed to be a connected network with at least two arcs emanating from each node.
机译：摘要本文提出了一个启发式，可以在连接的网络中找到旅行的推销员巡回赛（TST）。该方法首先识别一种节点和两个相关的电弧，其希望包含在所需的TST中。如果我们让这个节点用$$ p $$ p，并且两个选定的弧从这个节点发出的弧度由$$ left（{p，q} 右），{ text {}}}表示。 left（{p，k}右），$$ p，q和p，k，然后我们找到了一个路径加入两个节点$$ q ，{ text {}} ，k $$ q和k通过给定网络的所有剩余节点。这些长度的总和，即链接的长度$$ left（{p，q}右），{ text {and}} ， left（{p，k} 右）$$ p， q和p，k以及加入节点$$ q ，{ text {}} ，k $$ q和k通过所有剩余节点的路径的长度将导致可行的Tst，因此在TST上给出一个上限。概述了一个简单的程序来识别：（1）节点$$ p $$ p，（2）两个相应的链接$$ left（{p，q} 右），{ text {和}} ，左（{p，k}右），$$ p，q和p，k和（3）路径加入节点$$ q ，{ text {}} ，k $$ q k通过所有剩余的节点。该方法基于最小的生成树;因此降低了TST的复杂性。已经假设本文中的网络是连接网络，其具有从每个节点发出的至少两个弧。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号