刘倩++张心怡++逯瑶瑶+++杜晓磊

【摘要】TSP问题是一个经典组合优化问题，而最短路径算法多样，却因其复杂性不具有最优算法.本文在目标改进的基础上以江苏省地级市为例，利用MATLAB和LINGO软件模拟出最优路径图，改进算法确定回路，运用搜狗地图获取数据建立并求解数学模型以展开研究.

【关键词】TSP问题；动态规划；LINGO；优化算法

一、背景介绍

货郎担问题也叫旅行商问题，即TSP（Traveling Salesman Problem）问题，其要求很简单：在各城市的集合中，找出一条经过每个城市各一次，最终回到起点的最短路径.

求解该类问题可以使用精确算法，常用的方法包括：分支定界法、线性规划法和动态规划法等，但计算复杂度随着网络规模的增大呈指数增长，是NP困难的.当网络达到一定规模时，通常使用近似算法或启发式算法求解TSP.近似算法是把误差控制在一定范围的前提下快速得到解决方案，包括构造型算法和改进型算法，主要有遗传算法、蚁群算法、模拟退火算法、人工神经网络、LK算法、人工免疫算法、粒子群优化算法和混合智能算法等.

二、问题内容

目标①假设今年认识实习安排如下，从徐州市出发，需要访问江苏省的所有地级（以上）的城市，然后回到徐州市.本次实习搭乘我校的自备车，请设计路线要求至少经过每个城市1次，并且总的行驶里程最短.

目标②假设今年认识实习安排如下，从徐州市出发，需要访问江苏省的所有地级（以上）的城市，然后回到徐州市.本次实习搭乘我校的自备车，请设计路线要求至少经过每个城市1次，考虑公路的收费问题，假设汽车每千米的油耗是固定的，要求总的费用最少（注意：普通公路收费低，高速公路收费高）.

目标③假设今年认识实习安排如下，从徐州市出发，需要访问江苏省的所有地级（以上）的城市，然后回到徐州市.本次实习搭乘我校的自备车，请设计路线要求至少经过每个城市1次，考虑不同公路的车速限制问题，假设高速公路限速100千米/小时，其余公路限速60千米/小时，不考虑油耗和收费，汽车均按照最高限速行驶，要求总的时间最短.

三、模型假设

1.假设两个城市之间的往返是互逆过程.

2.假设所选路线都是可行的，即没有封路情况.

3.假设城市之间高速公路收费固定.

4.假设各城市的油价统一，均为国内统一油价.

5.假设车辆密度不随时间变化，不考虑车辆密度变化带来的速度变化.

6.假设在旅途中的车速一定，且不考虑突发事件干扰大巴的行程.

四、模型的建立与求解

首先用点来代替每个城市的位置，对江苏省各城市徐州、宿迁、连云港、淮安、盐城、扬州、泰州、镇江、南京、常州、无锡、苏州和南通等按顺序编号为1，2，…，13.

（一）问题一

1.模型的建立

设城市的个数为n，dij是两个城市i与j之间的距离，xij=0或1，假设一个TSP由城市1，2，3，…，13组成.当i≠j，设cij城市i到城市j的距离，设cij=M，其中M是一个非常大的数.设定cij=M将确保我们不会再离开城市i后不会马上到达城市i，此外定义

xij=1如果TSP的解是从城市i到城市j，

0如果TSP的解不是从城市i到城市j.

通过求解：

minz=∑i∑jcijxij，

∑i=ni=1xij≥1（j=1，2，…，n）.（1）

∑j=nj=1xij≥1（i=1，2，…，n）.（2）

ui-uj+n≤n-1（i≠j，i=2，3，…，n；j=2，3，…，n）.（3）

xij=0或1，uij≥0.（4）

目标函数给出了包括巡回访问路线中弧长的总长度，约束条件（1）确保我们到达城市至少一次，约束条件（2）确保我们只离开一个城市一次，（3）中的约束条件是表达的关键，他们确保：

（1）包含子巡回路线的任何一组xij都是不可行的（也就是它们违反了（3））；

（2）构成子巡回路线的任何一组xij都是可行的（存在一组满足（3）的uj）.

2.模型的求解

为了直观显示江苏省各城市之间的位置关系，我们搜集了江苏省13个城市的经纬度坐标，不相邻城市之间取非常大的数100 000 km.

根据江苏省各城市的经纬度坐标及两两城市之间的最短距离，我们运用Matlab软件模拟出了实习路线效果图，其中每一个“

Wingdings 2AB@ ”表示每个城市，折线表示实习路线，徐州市为实习起点，得到最优实习路线为：徐州→连云港→盐城→南通→泰州→苏州→无锡→常州→镇江→扬州→南京→淮安→宿迁→徐州，路线距离总和为：1534.2 km.

（二）问题二模型建立与求解

对于问题二，运用所建的模型，“最短距离”换为“最少费用”.由调查得出，汽车百千米油耗约为30 L，国内标准油价5.19元/L，且汽车每千米油耗固定，计算出汽车油耗费用为1.557元/km.根据实际道路长度，可以算出汽车油耗费用，再加上路程高速费用，从而可以得到江苏省两两城市之间的最少费用.同样，我们把不相邻的城市的行驶费用设为100 000元，即足够大，从而实现不可能选取.

我们基于上述模型及行驶费用最小原则，最优行驶路线为：徐州→连云港→盐城→泰州→南通→苏州→无锡→常州→镇江→南京→扬州→淮安→宿迁→徐州，行驶费用总和为2 523.25元.

（三）问题三模型建立与求解

1.理论时间模型

对于问题三，将模型二中的权值“最短距离”换为“最短时间”.由题目假设，汽车高速公路限速100千米/小时，其余公路限速60千米/小时，不考虑油耗和收费，根据问题一搜集到的两城市之间道路距离，再从中细化出高速距离与其他公路距离，根据车速，从而计算出江苏省各城市之间所需行驶时间，同样，根据江苏省交通厅的实时交通图及Lingo运行特点，我们把不相邻的城市的行驶时间设为100 000分钟，即足够大，从而实现不可能选取.

我们以任意两城市之间的行驶时间矩阵为权重矩阵，利用w3（i，j）13×13构造无向图UG3，利用Lingo軟件按改良圈算法求解，首先设C=v1v3…vnv3，求出符合要求的最短距离的最优圈circle3，保证从终点返回到出发点的行驶时间也最短.

从理论行驶时间模型的结果来看，基于总行驶时间最短原则，Lingo程序求解的认识实习的最优路线为徐州→宿迁→淮安→南京→扬州→镇江→常州→无锡→苏州→南通→泰州→盐城→连云港→徐州，行程总时间为1 011 min.

2.实际时间模型

由于实际路况的复杂性，各路况允许汽车行驶速度的不同，同时为了检验可靠性，我们在高德地图上搜集了城市之间的实际最短行驶时间，这个时间更具有说服力.

同样我们基于理论行驶时间模型的算法，以任意两城市之间的行驶时间矩阵为权重矩阵，利用Lingo软件按改良圈算法求解，首先设C=v1v4…vnv4，按改良圈算法求出此时的最优圈后，求出符合要求的最短距离的最优圈circle4，保证了从终点返回到出发点的行驶时间也最短.

从结果可知，基于实际行驶时间的实习最优路线与理论时间模型的最优路线相同，说明理论时间模型结果具有很高的可靠性，具体行驶路线与理论时间模型优化路线一致.

【参考文献】

[1]管琳，白艳萍.用分支定界算法求解旅行商问题[J].中北大学学报（自然科学版），2007（02）：104-107.

[2]吕善国，曹义亲，陈红丽.求解旅行商问题的一种新方法[J].华东交通大学学报，2012（05）：29-33.

[3]W L Winston.运筹学应用范例与解法[M].杨振凯，等译.北京：清华大学出版社，2006：572-599.endprint