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

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (3): 34-38.

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

肖桂霞,郑金华

湘潭大学信息工程学院，湖南湘潭 411105

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-01-21 发布日期:2008-01-21
通讯作者: 肖桂霞

New dynamic TSP model and its solution

XIAO Gui-xia,ZHENG Jin-hua

Institute of Information Engineering，Xiangtan University，Xiangtan，Hunan 411105，China

Received:1900-01-01 Revised:1900-01-01 Online:2008-01-21 Published:2008-01-21
Contact: XIAO Gui-xia

摘要/Abstract

摘要： TSP问题是经典的NP难问题，学者们已经提出很多有效的方法，但大多都是基于静态情形的，然而现实中的TSP问题基本为动态的，动态TSP将是一个更符合实际TSP问题的研究领域。提出了一种基于高斯扰动的动态TSP模型，设计了扰动响应算法，并对反序交叉算子做了改进。实验证明该算法的有效性和新模型的现实意义。

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

Abstract: 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.

Key words: dynamic, dynamic evolution, TSP, DTSP, evolution computation, genetic algorithm, Gauss disturbance

肖桂霞,郑金华. 一种新的动态TSP模型及其求解方法[J]. 计算机工程与应用, 2008, 44(3): 34-38.

XIAO Gui-xia,ZHENG Jin-hua. New dynamic TSP model and its solution[J]. Computer Engineering and Applications, 2008, 44(3): 34-38.