基于eM-Plant与动态规划算法的TSP问题应用研究  

The Traveling Salesman Problem Research Based on eM-Plant and Dynamic Programming Algorithm

作　　者：戈艳艳[1] 

机构地区：[1]武汉理工大学物流工程学院,湖北武汉430063

出　　处：《物流工程与管理》2012年第3期78-79,97,共3页Logistics Engineering and Management

摘　　要：TSP问题是典型的组合优化问题,也是一个易于描述却难以处理的NP难题,该问题的特点是随着城市数目的增加,计算复杂度呈指数增长。文中首先对TSP问题和动态规划算法进行了详细的描述,接着应用eM-Plant软件采用动态规划算法对其进行求解,并用实例证明了该方法的灵活性、实用性。The traveling salesman problem is a classical problem in combinatorial optimization,which is also characterized as an NP-hard problem that easy-to-describe but difficult to solve.The characteristic of this problem is the computational complexity would increase exponentially with the increasing of the vertices in the graph.In this paper,described the traveling salesman problem and dynamic programming algorithm in detail firstly,and then the eM-Plant and dynamic programming algorithm were applied to solve the problem;in addition,the method has been proved to be flexibility and practicability through an example.

关 键 词：旅行商问题 EM-PLANT 动态规划算法 

分 类 号：F274[经济管理—企业管理]