张家善

摘要：指出了TSP问题是一种具有代表性的组合优化问题，在现实生活中有着广泛的应用。不同于完全图，非完全图TSP问题中存在着某些节点之间没有路径直接相连，使得处于该节点位置时，其路径选择受到一定限制。受运筹学中大M法思想的启发，提出了通过引入一个非常大的正数（即大M）来表示此类节点间的距离，从而将非完全图TSP问题转化成完全图TSP问题，降低了问题求解的难度，并且验证了该方法的有效性。

关键词：TSP问题；非完全图；大M法；仿真

中图分类号：F57

文献标识码：A 文章编号：1674-9944（2016）05-0182-02

1 引言

旅行商问题（Traveling Salesman Problem，TSP），又称货郎担问题或旅行推销员问题，最早由美国的Rand公司提出。问题可简单描述为： 设有n个城市（节点），若从某城市（节点）出发，遍历各城市（节点）一次后返回原出发点，要求找出一条路线，使总路径最短[1]。TSP问题的图论描述为：设图G=（V，E）， V代表顶点集，E代表由不同顶点组成的边集，已知道各边的长度dij，要找出一个Hamilton回路，使它的距离最短。现实生活中有很多问题可以归结为旅行商问题，比如邮路问题、连锁店的货物配送路线问题、装配线上的螺帽问题和产品的生产安排问题等[2]，其研究具有重要的理论意义和应用价值。

通过中国知网检索发现，国内外学者就TSP问题进行了相关研究：Pintea等人[3]将蚁群优化算法应用于解决旅行商问题；李勇采用动态蚁群算法研究了TSP问题[4]；李如琦提出用MAX_MIN蚂蚁算法解决中国旅行商问题[5]；国圆媛应用蚁群算法解决了浙江旅行商问题的最短路径[6]；……