位置：成果数据库 > 期刊 > 期刊详情页
瓶颈TSP下界快速算法
  • 期刊名称：《科学技术与工程》, 2006, 6 (9): 1260-1263
  • 时间：0
  • 分类：O224[理学—运筹学与控制论;理学—数学]
  • 作者机构：[1]上海理工大学管理学院,上海200093
  • 相关基金：国家自然科学基金（70471065）,上海市教委科技发展基金（05EZ31）和上海市重点学科建设项目（T0502）资助
  • 相关项目：竞争型多目标元胞蚂蚁算法研究
关键词： 瓶颈TSP, 下界, 算法, 逼近程度, bottleneck traveling salesman problem lower bound algorithm approximation ratio
中文摘要：

瓶颈TSP是网络设计和优化中的一个NP难题，在数学推导和证明的基础上，给出了一个求解对称型瓶颈TSP问题下界的快速算法，利用该算法求解了TSP问题标准库中部分对称型问题，给出了计算结果并与标准问题库中已知的最好解进行了比较。

英文摘要：

Finding the Bottleneck Traveling Salesman Problem （BTSP） tour in a given graph is a NP-hard problem which is important in network design and combinatorial optimization. Based on mathematical inference and proof, a quick algorithm for calculating the lower bound of symmetric bottleneck is proposed Travelling Salesman Problem is proposed. Series of numerical examples of BTSP from TSBLIB are tested and the computational results of the algorithm are compared with the best-known solutions published.

同期刊论文项目
竞争型多目标元胞蚂蚁算法研究
期刊论文 59 会议论文 1 著作 1
同项目期刊论文
基于元胞自动机的物流系统选址模
度约束欧氏Steiner最优树问题及
双层PCB布线的混合蚂蚁优化方法
求解度约束最小生成树的一种启发
若干扩展TSP的元胞蚂蚁算法
燃料电池发动机优化控制的建模与
度约束最小生成树(DCMST)的竞争
双目标旅行商问题及其蚂蚁算法实
非线性规划的元胞蚂蚁算法
欧氏Steiner最优树的快速算法
一种求解最小连通支配集的高效近
最小顶点覆盖快速降价算法
0/1背包问题竞争决策算法
基于加权绝对值距离Steiner最优
A New Evolutionary Algorithm f
多目标函数优化的元胞蚂蚁算法
对称型TSP下界的快速估算法
图着色问题的启发式搜索蚂蚁算法
燃料电池发动机优化控制建模与元
基于复杂适应系统的蚂蚁群体智能
TSP的元胞蚂蚁算法求解
最小比率旅行商(MRTSP)问题竞争
大规模旅行商问题的竞争决策算法
0/1背包问题快速降阶法及其应用
基于双层蚂蚁算法的半导体炉管制
竞争决策算法原理及其应用
基于快速下界估算的瓶颈旅行商问
PCB布线的元胞蚂蚁算法研究
欧氏Steiner最小树的智能优化算
多目标0-1规划的蚂蚁优化算法
Algorithms for Degree-constrai
限制情况下装卸工问题的最优解
最小顶点覆盖快速降阶算法
函数优化的元胞蚂蚁算法
装卸工人调配问题新解法及其证明
元胞蚂蚁算法的收敛性分析
复杂网络上计算机病毒传播和控制策略研究
度约束欧氏Steiner最小树问题及其求解
中国教育网拓扑结构比较研究
燃料电池发动机优化控制的建模与蚂蚁算法研究
基于元胞自动机的物流系统选址模型
双目标旅行商问题及其蚂蚁算法实验研究
基于多分辨率分析和改进离散余弦变换的音频水印算法
一种求解最小连通支配集的高效近似算法
基于Radon变换的多尺度虹膜特征提取算法
元胞蚂蚁算法的收敛性
一种新的大规模网络最短路径的近似算法
基于Haar尺度变换的连续分片线性逼近
基于小波分解和分类的人脸识别
一类特殊二次分配问题及其求解
带时间窗车辆路径问题的混合改进型蚂蚁算法
多目标0—1规划的蚂蚁优化算法
求解绝对值距离Steiner最小树的改进元胞蚂蚁算法
Steiner最小树问题及其应用
Algorithms for degree-constrained Euclidean Steiner minimal tree
数据流概念漂移双窗探测方法