一种新的动态TSP模型及其求解方法  

New dynamic TSP model and its solution

作　　者：肖桂霞[1] 郑金华[1] 

机构地区：[1]湘潭大学信息工程学院,湖南湘潭411105

出　　处：《计算机工程与应用》2008年第3期34-38,共5页Computer Engineering and Applications

基　　金：国家自然科学基金(the National Natural Science Foundation of China under Grant No.60773047);国家高技术研究发展计划( 863)(the National High-Tech Research and Development Plan of China under Grant No.2001AA114060);湖南省自然科学基金(the Natural Science Foundation of Hunan Province of China under Grant No.05JJ30125);留学回国人员科研启动基金(No.教外司留[2005]546 号);湖南省教育厅重点科研项目( No.06A074)

摘　　要：TSP问题是经典的NP难问题,学者们已经提出很多有效的方法,但大多都是基于静态情形的,然而现实中的TSP问题基本为动态的,动态TSP将是一个更符合实际TSP问题的研究领域。提出了一种基于高斯扰动的动态TSP模型,设计了扰动响应算法,并对反序交叉算子做了改进。实验证明该算法的有效性和新模型的现实意义。The traveling sales man problem is a classical NP-hard problem.Many algorithms and methods existed in this area,however most of them are used to solve static problems which are much different from problems in dynamic environment of real world.So the Dynamic Traveling Sales man Problem （DTSP） is a new research area where researchers will concentrate on useful models and methods of practical TSP.In this paper,we proposed a new model for practical TSP called DTSP based on Gauss disturbance.Also we designed an algorithm to respond the dynamic change and improved the inver_over operator.The experimental results showed that our new model is useful for practical problem and the algorithm is effective.

关 键 词：动态 动态进化 TSP DTSP 进化计算 遗传算法 高斯扰动 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]