旅行商问题优化解之间关系的分析

被引：2

作者：

王东

吴湘滨

毛先成

刘文剑

机构：

[1] 中南大学地学与环境工程学院

来源：

小型微型计算机系统 | 2008年 / 05期

关键词：

旅行商问题; 全局最优解; 局部最优解; 裁减; 求解质量;

D O I：

暂无

中图分类号：

TP18 [人工智能理论]; TP301 [理论、方法];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ; 081202 ;

摘要：

旅行商问题是经典的组合优化NP难题之一,学术界一直致力于建立在合理的计算时间内精确或近似求解问题的算法.近似算法常求得的高质量近似优化解与全局最优解之间边交集不为空,建立了两者之间及与全局最优解之间的特定关系,通过数学分析建立量化关系模型,利用实验确立模型中相关参数的先验概率.据此建立的随机TSP裁减过程大幅度裁减问题的求解规模;在求解过程中亦能高概率确定属于全局最优解的边,以提高问题求解效率和质量.

引用

页码：879 / 884

页数：6

共 6 条

[1] The co-adaptive neural network approach to the Euclidean Travelling Salesman Problem [J].

Cochrane, EM ;

Beasley, JE .

NEURAL NETWORKS, 2003, 16 (10) :1499-1525

[2]

Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number[J] . Gregory Gutin,Anders Yeo.Discrete Applied Mathematics . 2002 (1)

[3]

The traveling-salesman problem and minimum spanning trees: Part II[J] . Michael Held,Richard M. Karp.Mathematical Programming . 1971 (1)

[4]

Dynamic Programming Treatment of the Travelling Salesman Problem[J] . Richard Bellman.Journal of the ACM （JACM） . 1962 (1)

[5] SOLUTION OF A LARGE-SCALE TRAVELING-SALESMAN PROBLEM [J].

DANTZIG, G ;

FULKERSON, R ;

JOHNSON, S .

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF AMERICA, 1954, 2 (04) :393-410

[6]

Some new branching and bounding criteriafor the asymmetric traveling salesman problem. Carpaneto G,Toth P. Management Science . 1980

← 1 →