论文部分内容阅读
摘 要：本文通过引入一个非常大的正数（即大M）来表示没有路径连接节点间的距离，从而将非完全图转化成完全图；并且通过先计算所有节点间距离得到一个非对称距离矩阵，然后在迭代过程中直接读取的方法，降低其在计算时间上的开销，成功解决了非完全有向图TSP问题。实例仿真，验证了该方法的有效性。
关键词：TSP问题 非完全有向图 大M 仿真
一、引言
旅行商问题 （Traveling Salesman Problem，TSP），又称货郎担问题或旅行推销员问题，最早由美国的Rand公司提出。问题可简单描述为：设有n个城市（节点），若从某城市（节点）出发，遍历各城市（节点）一次后返回原出发点，要求找出一条路线，使总路径最短。TSP问题的图论描述为：设图G=（V，E），V代表顶点集，E代表由不同顶点组成的边集，已知道各边的长度dij，要找出一个 Hamilton回路，使它的距离最短。现实生活中有很多问题可以归结为旅行商问题，比如邮路问题、连锁店的货物配送路线问题、装配线上的螺帽问题和产品的生产安排问题等，其研究具有重要的理论意义和应用价值。
针对TSP问题，国内外学者进行了相关研究：Pintea等人将蚁群优化算法应用于解决旅行商问题；李勇采用动态蚁群算法研究了TSP问题；李如琦提出用MAX_MIN蚂蚁算法解决中国旅行商问题；国圆媛应用蚁群算法解决了浙江旅行商问题的最短路径；潘庆祥建立了有向图TSP模型，并设计了算法进行求解。
二、TSP问题分类
按照TSP路径关系的不同特征，通常有以下两种基本分类：
1.根据任意两个城市之间是否均存在边相连接，可分为完全图TSP问题 与非完全图问题。完全图是指即一个图的每一对不同顶点恰有一条边相连，基于完全图的旅行商问题即为完全图TSP问题；非完全图是指存在两个顶点之间没有边相连接，即 n个端点的连接边数少于n（n -1） / 2条边，基于非完全图的旅行商问题即为非完全图TSP问题。
2.根据任意两个城市之间来回路径均是否相等，可分为无向图TSP问题和有向图TSP问题。所谓无向图，是指一个图中的每条边都没有方向，往返的费用值相等，即dij=dij；所谓有向图，是指一个图中的每条边有方向，往返的费用值不等，即dij≠dij。
上述研究多是針对完全图TSP问题，而完全图是一种简单图，任何两个顶点之间均有线路连接，问题求解相对容易，但针对非完全图的研究较少。此外，研究针对无向图的较多，而针对有向图的研究偏少。本文将重点就非完全有向图TSP问题展开探讨。
三、非完全有向图TSP问题的数学模型
与完全图、无向图TSP问题不同，非完全有向图TSP问题中存在城市之间没有路径连接，即不能从一个城市直接到达另一个城市；并且路径是有方向的，从城市达到另一城市，和从另一城市返回该城市的费用值（如距离、时间等）是不相等的。这就需要对问题进行转换处理。
1.非完全图问题。针对非完全图问题，一种设想是寻找一条经过第三个城市的最短路来间接地表示两个城市之间的路径关系，即令
dij=min{dip+dpj}，1≤i，j，p≤n
但是，这种设想要增加从若干种可能中选优，且仅仅是局部选优的计算过程，当城市数目n很大时，计算的复杂度将大大增加。本文引入大M（一个非常大的正数）来表示 没有路径直接相连的两个城市之间的距离，从而将问题转换成完全图TSP问题。
2.图的有向性问题。如果在算法过程中，每次都要计算城市（节点）间距离，那么相对于无向图TSP问题，有向图TSP问题的计算工作量将至少增加一倍以上，这势必影响计算速度，降低算法的效率。针对路径存在方向性，本文采用如下解决方法：在每次算法迭代之前，先将所有节点间距离计算出来，得到一个非对称距离矩阵，在后续迭代计算过程中，直接从该矩阵中读取，这样就大大减少了计算时间，从而提高了算法求解速度。
这样，非完全有向图TSP问题，就转化成了标准的TSP问题。
设
建立其数学模型如下：
上式中，n为集合中所含图的顶点数。约束（1）和（2）意味着对每个点而言，仅有一条边进和一条边出；约束（3）则保证了没有任何子回路解的产生。于是，满足约束（1）、（2）和（3）的解构成了一条Hamilton回路。
四、实例验证
本文选取Eil51前15个节点作为研究对象，随机选取其中9对节点间的边调整为有向路径，随机选取其中4对节点调整为没有路径连接（如表1所示），从而将其改造成非完全有向图TSP问题。该4对节点间距离取非常大的正数M（本例取M=10000），代表节点之间没有路径连接。表中红色加粗字体，代表该两节点间的路径，是有方向的，往返费用值不相等。
针对非完全有向图TSP问题，本文采用MATLAB软件作为运行平台，编写蚁群算法程序在计算机上仿真计算，得到最优路径如图1所示：
在非完全有向图TSP问题中，由于存在节点之间没有路径连接，搜索TSP路线的次数应等于或者少于完全图TSP问题，所得到的TSP路线方案总数也应少于完全图TSP情形。由于其路径带有方向性，需要先计算距离矩阵，故算法复杂性略大于无向图TSP问题，计算时间略多于无向图TSP问题 。仿真计算得到最短路径为：
4→13→14→6→7→8→3→2→1→11→9→10→15→5→12
最优路径的长度： 212.0552
五、结语
非完全有向图TSP问题中存在着某些城市（节点）之间没有路径直接相连，并且节点间路径带有方向性，这给问题的解决带来了困难。受到运筹学中大M法思想的启发，本文通过引入一个非常大的正数（即大M）来表示 这些节点间的距离，从而将非完全图TSP问题转化成完全图TSP问题；针对路径的方向性，本文采取先将所有节点间距离计算出来，得到一个非对称距离矩阵，然后在迭代计算过程中，直接从该矩阵中读取的方法，降低了计算时间上的开销。最终，将非完全有向图TSP问题 转化成规范化的、易于求解的标准TSP问题。需要指出的是，本文提出的这种将非完全有向图TSP问题转化成标准TSP问题的思想，也给我们解决其他非标准TSP问题以启发。
参考文献：
[1]余详宣，崔国华.计算机算法基础[M].第二版.武汉：华中科技大学，1998.
[2]李会玲.基于模拟退火的遗传优化算法在 TSP 问题中的应用[J].热处理技术与装备， 2007，28（6）：51-55.
[3] Pintea C M， Pop P C， Dumitrescu D. An ant-based technique for the dynamic generalized traveling salesman problem[C]. Proceedings of the 7-th WSEAS International Conference on Systems Theory and Scientific Computation. 2007： 257-261.
[4]李男，段正澄.动态蚁群算法求解 TSP 问题[J].计算机工程与应用，2003，39（17）：104-107.
[5]李如琦，苏媛媛.用MAX_MIN蚂蚁算法解决中国旅行商问题[J]. 湖南工业大学学报. 2007（05）
[6]国圆媛，许延鑫等.浙江旅行商问题研究[J].中国新技术新产品. 2009（22）：147-149.
[7]潘庆祥，徐自然.具有重复路径的有向TSP问题[J].才智. 2014（17）：103-106.
[8]徐心和，旅行商问题的一种新解法，东北工学院学报1990， 11（1）：68-74.
作者简介：张家善（1979—），男，四川巴中人，讲师，博士，从事信息管理和物流管理的研究工作。
※基金项目：重庆工程职业技术学院 院级课题（项目编号：RWB201504）；重庆市高等教育学会高等教育科学研究课题（项目编号：CQGJ15387C）；重庆市教育评估研究会立项课题（项目编号：PJY2015-50）.
关键词：TSP问题 非完全有向图 大M 仿真
一、引言
旅行商问题 （Traveling Salesman Problem，TSP），又称货郎担问题或旅行推销员问题，最早由美国的Rand公司提出。问题可简单描述为：设有n个城市（节点），若从某城市（节点）出发，遍历各城市（节点）一次后返回原出发点，要求找出一条路线，使总路径最短。TSP问题的图论描述为：设图G=（V，E），V代表顶点集，E代表由不同顶点组成的边集，已知道各边的长度dij，要找出一个 Hamilton回路，使它的距离最短。现实生活中有很多问题可以归结为旅行商问题，比如邮路问题、连锁店的货物配送路线问题、装配线上的螺帽问题和产品的生产安排问题等，其研究具有重要的理论意义和应用价值。
针对TSP问题，国内外学者进行了相关研究：Pintea等人将蚁群优化算法应用于解决旅行商问题；李勇采用动态蚁群算法研究了TSP问题；李如琦提出用MAX_MIN蚂蚁算法解决中国旅行商问题；国圆媛应用蚁群算法解决了浙江旅行商问题的最短路径；潘庆祥建立了有向图TSP模型，并设计了算法进行求解。
二、TSP问题分类
按照TSP路径关系的不同特征，通常有以下两种基本分类：
1.根据任意两个城市之间是否均存在边相连接，可分为完全图TSP问题 与非完全图问题。完全图是指即一个图的每一对不同顶点恰有一条边相连，基于完全图的旅行商问题即为完全图TSP问题；非完全图是指存在两个顶点之间没有边相连接，即 n个端点的连接边数少于n（n -1） / 2条边，基于非完全图的旅行商问题即为非完全图TSP问题。
2.根据任意两个城市之间来回路径均是否相等，可分为无向图TSP问题和有向图TSP问题。所谓无向图，是指一个图中的每条边都没有方向，往返的费用值相等，即dij=dij；所谓有向图，是指一个图中的每条边有方向，往返的费用值不等，即dij≠dij。
上述研究多是針对完全图TSP问题，而完全图是一种简单图，任何两个顶点之间均有线路连接，问题求解相对容易，但针对非完全图的研究较少。此外，研究针对无向图的较多，而针对有向图的研究偏少。本文将重点就非完全有向图TSP问题展开探讨。
三、非完全有向图TSP问题的数学模型
与完全图、无向图TSP问题不同，非完全有向图TSP问题中存在城市之间没有路径连接，即不能从一个城市直接到达另一个城市；并且路径是有方向的，从城市达到另一城市，和从另一城市返回该城市的费用值（如距离、时间等）是不相等的。这就需要对问题进行转换处理。
1.非完全图问题。针对非完全图问题，一种设想是寻找一条经过第三个城市的最短路来间接地表示两个城市之间的路径关系，即令
dij=min{dip+dpj}，1≤i，j，p≤n
但是，这种设想要增加从若干种可能中选优，且仅仅是局部选优的计算过程，当城市数目n很大时，计算的复杂度将大大增加。本文引入大M（一个非常大的正数）来表示 没有路径直接相连的两个城市之间的距离，从而将问题转换成完全图TSP问题。
2.图的有向性问题。如果在算法过程中，每次都要计算城市（节点）间距离，那么相对于无向图TSP问题，有向图TSP问题的计算工作量将至少增加一倍以上，这势必影响计算速度，降低算法的效率。针对路径存在方向性，本文采用如下解决方法：在每次算法迭代之前，先将所有节点间距离计算出来，得到一个非对称距离矩阵，在后续迭代计算过程中，直接从该矩阵中读取，这样就大大减少了计算时间，从而提高了算法求解速度。
这样，非完全有向图TSP问题，就转化成了标准的TSP问题。
设
建立其数学模型如下：
上式中，n为集合中所含图的顶点数。约束（1）和（2）意味着对每个点而言，仅有一条边进和一条边出；约束（3）则保证了没有任何子回路解的产生。于是，满足约束（1）、（2）和（3）的解构成了一条Hamilton回路。
四、实例验证
本文选取Eil51前15个节点作为研究对象，随机选取其中9对节点间的边调整为有向路径，随机选取其中4对节点调整为没有路径连接（如表1所示），从而将其改造成非完全有向图TSP问题。该4对节点间距离取非常大的正数M（本例取M=10000），代表节点之间没有路径连接。表中红色加粗字体，代表该两节点间的路径，是有方向的，往返费用值不相等。
针对非完全有向图TSP问题，本文采用MATLAB软件作为运行平台，编写蚁群算法程序在计算机上仿真计算，得到最优路径如图1所示：
在非完全有向图TSP问题中，由于存在节点之间没有路径连接，搜索TSP路线的次数应等于或者少于完全图TSP问题，所得到的TSP路线方案总数也应少于完全图TSP情形。由于其路径带有方向性，需要先计算距离矩阵，故算法复杂性略大于无向图TSP问题，计算时间略多于无向图TSP问题 。仿真计算得到最短路径为：
4→13→14→6→7→8→3→2→1→11→9→10→15→5→12
最优路径的长度： 212.0552
五、结语
非完全有向图TSP问题中存在着某些城市（节点）之间没有路径直接相连，并且节点间路径带有方向性，这给问题的解决带来了困难。受到运筹学中大M法思想的启发，本文通过引入一个非常大的正数（即大M）来表示 这些节点间的距离，从而将非完全图TSP问题转化成完全图TSP问题；针对路径的方向性，本文采取先将所有节点间距离计算出来，得到一个非对称距离矩阵，然后在迭代计算过程中，直接从该矩阵中读取的方法，降低了计算时间上的开销。最终，将非完全有向图TSP问题 转化成规范化的、易于求解的标准TSP问题。需要指出的是，本文提出的这种将非完全有向图TSP问题转化成标准TSP问题的思想，也给我们解决其他非标准TSP问题以启发。
参考文献：
[1]余详宣，崔国华.计算机算法基础[M].第二版.武汉：华中科技大学，1998.
[2]李会玲.基于模拟退火的遗传优化算法在 TSP 问题中的应用[J].热处理技术与装备， 2007，28（6）：51-55.
[3] Pintea C M， Pop P C， Dumitrescu D. An ant-based technique for the dynamic generalized traveling salesman problem[C]. Proceedings of the 7-th WSEAS International Conference on Systems Theory and Scientific Computation. 2007： 257-261.
[4]李男，段正澄.动态蚁群算法求解 TSP 问题[J].计算机工程与应用，2003，39（17）：104-107.
[5]李如琦，苏媛媛.用MAX_MIN蚂蚁算法解决中国旅行商问题[J]. 湖南工业大学学报. 2007（05）
[6]国圆媛，许延鑫等.浙江旅行商问题研究[J].中国新技术新产品. 2009（22）：147-149.
[7]潘庆祥，徐自然.具有重复路径的有向TSP问题[J].才智. 2014（17）：103-106.
[8]徐心和，旅行商问题的一种新解法，东北工学院学报1990， 11（1）：68-74.
作者简介：张家善（1979—），男，四川巴中人，讲师，博士，从事信息管理和物流管理的研究工作。
※基金项目：重庆工程职业技术学院 院级课题（项目编号：RWB201504）；重庆市高等教育学会高等教育科学研究课题（项目编号：CQGJ15387C）；重庆市教育评估研究会立项课题（项目编号：PJY2015-50）.