2011苏北数学建模竞赛B题解答.pdf

《2011苏北数学建模竞赛B题解答.pdf》由会员分享，可在线阅读，更多相关《2011苏北数学建模竞赛B题解答.pdf（17页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数学建模王迪 B09010601 通信工程郑佳佳 B09010603 通信工程孟天舒 B09010604 通信工程题目旅游线路的优化设计旅游线路的优化设计摘要摘要本题为典型的旅行商问题（TSP），是组合数学中一个古老而又困难的问题，它易于描述却难以完全解决，属于 NP 完全问题。对于规模较小的旅行商问题，可以通过穷举得到最优解，但随着问题规模的增大空间复杂度急剧增加，需要通过启发式算法求解。由意大利学者于1992年首先提出的蚁群系统(AntColonySystem,ACS)是一种新生的仿生进化算法,适用于求解复杂组合优化问题,在解决 TSP 问题方面取得了较为理想的效果。 在此， 我们以改进的

2、蚁群算法为基础建立数学模型来设计这些旅游者在五一开始的路线，试图能得到一些合理的结论。(1) 第一问是典型的费用 TSP 问题。对于此问题我们套用基本蚁群算法，查找到城市坐标以及旅游费用，并建立求解矩阵。通过 MATLAB 软件的模拟，求出若干优化解，取相对最优解作为计算结果。 所求得的路线为徐州出发洛阳市龙门石窟西安市秦兵马俑山西祁县乔家大院青岛市崂山北京八达岭长城江西九江庐山黄山市黄山常州中华恐龙园舟山市普陀山武汉市黄鹤楼返回徐州，共计3201 元。(2) 第二问为时间 TSP 问题。 由于时间在具体操作上的波动性， 根据数据所得结论将时间的 TSP转化为距离 TSP 问题。 求解出的路线

3、为： 徐州出发常州中华恐龙园舟山市普陀山黄山市黄山九江市庐山武汉市黄鹤楼洛阳市龙门石窟西安市秦始皇兵马俑祁县乔家大院北京市八达岭长城青岛市崂山返回徐州，总计用时 11 天 12 小时 20 分。(3) 第三问为有费用约束下的 TSP 问题。对于此问题利用了试探法和最小元素得到近似解，再用基本蚁群算法进行优化。 求解出的路线为： 徐州西安山西武汉黄山北京洛阳徐州，所花费用 1839 元，游览了 5 个景点。(4) 第四问是在时间约束条件下的 TSP 问题。解法与前一问类似，求解出的路线为：徐州北京洛阳西安武汉祁县常州徐州， 总时长为 4 天 21 小时 48分。(5) 第五问寻求综合因素优化的问

4、题，通过计算给出评价模型，将价格和费用整合到一个无量纲描述矩阵中。再通过试探法得出最优的方案。最佳路线为：徐州北京青岛西安祁县武汉徐州，总时长 4 天 21 小时 23 分，花费 1823 元。联系实际情况可知，结果是合理可行的。关键词：旅行商问题（TSP），蚁群算法，动态分析，试探法一、一、 问题的重述问题的重述旅游线路的优化设计随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上 8 点之后出发，到全国一些着名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点。省市景点名

5、称在景点的最短停留时间江苏常州市恐龙园4 小时山东青岛市崂山6 小时北京八达岭长城3 小时山西祁县乔家大院3 小时河南洛阳市龙门石窟3 小时安徽黄山市黄山7 小时湖北武汉市黄鹤楼2 小时陕西西安市秦始皇兵马俑2 小时江西九江市庐山7 小时浙江舟山市普陀山6 小时假设：(A)城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。(B)市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。(C)旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票 (第一门票)。晚上20：00 至次日早晨 7：00 之间，如果在某地停留超过 6 小时，必须住宿，住宿费

6、用不超过 200 元/天。吃饭等其它费用 60 元/天。(D)假设景点的开放时间为 8:00 至 18:00。问题：根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等 )、宾馆地点和名称，门票费用，在景点的停留时间等信息。(1)如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用请建立相关数学模型并设计旅游行程表。(2)如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间请建立相关数学模型并设计旅游行程表。(3)如果这位游客准备 2000 元旅游费用， 想尽可能多游览景点， 请建立相关数学模型并设计旅游行程

7、表。(4)如果这位游客只有 5 天的时间， 想尽可能多游览景点， 请建立相关数学模型并设计旅游行程表。(5)如果这位游客只有 5 天的时间和 2000 元的旅游费用， 想尽可能多游览景点， 请建立相关数学模型并设计旅游行程表。二、二、 模型假设与符号说明模型假设与符号说明2.1 模型的基本假设（1） 每个景点仅经过一次。（2） 只考虑问题中提供的 11 个旅游景点，不考虑其他中转地点作为 TSP 的需求点。（3） 为使问题一定程度上简约化，将城市与路径抽象成点与直线的图论问题。在问题（ 2）中承认旅行中的车旅费用以及时间与两景点之间距离成正比，以距离的 TSP 替代时间的TSP。不考虑绕路等特

8、殊情况。在建模时认为两地之间往返的费用时间差异可忽略。（4） 在求解费用最少问题时，模型假设时认为住宿，门票，车旅及餐费都必须包含在内。（5）认为网上公布的机票与车票均可以在任意时刻获得，且班次误点等特殊情况不予考虑，忽略转站中的不合理因素。（6）不考虑天气原因对选择交通工具的影响。（7）关于两地间距离仅作比较参考，一切以路径为准。2.2 符号说明符号名称G赋权图矩阵C图中的元素（景点）n景点的个数D赋权图的描述矩阵T访问顺序集合L最优解（最小费用或最短路程）dti,ti+1mkbi(t)ij(t)Pg(C,L,)tabukpkij(t)ij(t)kij(t)QLkNCNCmax时间 ti到

9、ti+1的 TSP 描述蚂蚁的总数量蚂蚁的编号t 时刻位于城市 i 的蚂蚁数目t 时刻路径（i,j）上的信息量t 时刻 C 中两两景点之间的残留信息素浓度集合初始时刻各路径上的信息素量寻优有向图第 k 只蚂蚁的禁忌搜索表蚂蚁 k 在 t 时刻由 i 城市转向 j 城市的转移概率信息启发式因子期望启发式因子启发函数信息素挥发系数t 时刻 k 蚂蚁在路径 ij 上留下的信息素量蚂蚁携带的信息素量本次循环中第 k 只蚂蚁所走的路程长度所记录的循环次数最大循环次数三模型的建立与求解三模型的建立与求解基本蚁群算法求解权值不变时单一目标值 TSP 问题的最优化模型问题的图论阐述将旅游景点图优化成完全带权图

10、，问题即可抽象成图论问题：令赋权图为 G=(C,L)，其中C=C1,C2,Cn为节点，表示各个景点的集合；L=Lij|Ci，Cj C表示各个景点之间的路径，每两个景点间的路径 lij都有相关的权值 dij与之对应，从而建立起一个 D=（dij）矩阵，权值可以表示距离、费用、路径等。由于题目的相关要求可以抽象出一个典型旅行商问题的数学模型：minL=ni=1dti, ti + 1基本的蚁群算法模型基本思想：蚁群算法是一种通过模拟自然界蚂蚁寻径的行为的进化算法。蚂蚁群找到食物时,它们总能找到一条从食物到巢穴之间的最优路径。 这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素，当它们碰到一个还

11、没有走过的路口时,就随机地挑选一条路径前行，与此同时释放出与路线长度有关的信息素，路径越长,释放的激素浓度越低，当后来的蚂蚁再次碰到这个路口的时候,选择激素浓度较高路径概率就会相对较大，这样形成了一个正反馈。最优路径上的激素浓度越来越大,而其它的路径上激素浓度却会随着时间的流逝而消减。 这样,整个蚁群最终会找出最优路径。用 bi(t)表示城市 i 的蚂蚁数目，ij表示 t 时段路径（i，j）上的信息量，n 表示景点的个数，m 为蚂蚁的总数量，则 m=ni=1bi(t)初试时刻，各条路径上信息量相等，均为P，ij（0）=P。又因为蚂蚁不能重复经过同一个城市，因此建立禁忌表（或记录未走过的路径 J

12、k）tabuk(k 取正整数)来记录蚂蚁走过的城市，并随时间做动态调整。被随机分散在n个节点的m只蚂蚁同时出发，按照下面的概率公式逐次访问各个城市节点：蚂蚁k以概率在这里，有pijk访问下一个节点：ij表示边L(i, j)上的信息素强度。ij表示由节点i到节点j的启发函数，显然距离越长期望度越低，所以在此将ij设为1/ dij。随着时间的推移,可能会出现两种情况:之前各蚂蚁留下的信息素逐渐消失；经过多次循环后，路径上的残留信息素过多，淹没了期望程度对蚂蚁选择路径的影响。为了避免这两种情况,在每一只蚂蚁完成一次循环后，我们对引入参数对残留的信息素进行更新。为信息素的挥发速率，是在0,1间取值的可

13、变量,用于控制两种信息素的比重。设经过x个时间单位后,蚂蚁完成一次循环,各路径上的信息素的量根据以下式子作出调整： ij：蚂蚁在本次循环中留在路径L(i, j)上的信息素强度。ijk：蚂蚁k留在路径L(i, j)上的信息素强度。当蚁群完成了所有的节点的访问后， 在原路返回的过程中， 根据所得的解的好坏去修改路径上的信息素强度，以此来引导其他蚂蚁对该路径的选择，从而达到群体协作的目的，最后判断系统是否满足停止的条件（停止条件可以是最大的迭代次数，计算机运行时间，或者是达到系统所要达到的数据精度等），如果条件不满足，则蚁群又重新开始搜索路径，建立新的解；否则，系统将退出运行，将所得的结果输出。从上

14、面可以看出，蚁群优化算法的基本思想就是质量越好的解和距离越短的路径就越能吸引更多的蚂蚁。蚁群正是通过这种反复记忆和学习的过程，得到了最短路径，即全局最优解。我们将各城市的经纬度通过球面坐标系的转化分别投影到一个二维平面上点的横纵坐标， 在求解的时候可直接求出两地的直线距离，即为dij。基本蚁群算法的算法流程在本题中，基本蚁群算法的具体实现步骤如下：1.参数初始化：令 t=0；设置最大循环次数 NcMax，循环次数 Nc=0；将 m 只蚂蚁置于 n 个节点上，在每个节点 i 放置 bi(t)只蚂蚁；初始化每条边(i,j)上的信息素量ij(0)=c 为一个常量，初始时刻ijk(0)=0；初始化禁忌

15、表 tabuk和路径表 Lk。2.设置索引号 s=1，对k=1m 将蚂蚁 k 的起始城市放入禁忌表中，并重复以下步骤直至禁忌表填充完整：对 k=1m，利用公式计算转移概率 pij，根据伪随机比例规则选择下一景点，将蚂蚁 k 移动到下一景点 j 并将其填入禁忌表，同时记录蚂蚁 k 的路线，索引号自增。3.对 k=1m，根据 Lk的记录计算蚂蚁 k 所走循环路径的总长度，找到最佳路线4.计算每只蚂蚁的信息素增量kij(t)5.更新每条路径上的信息素量kij(t+n)6.清空禁忌表及路线表。+，若 NcNcMax，返回步骤 2，否则，循环结束。开始初始索引号蚂蚁 k=1计算转移概率 pij，选择下一

16、节点 j修改禁忌表，记录k=k+1Nk蚂蚁总数Ys=s+1NsnY根据记录计算权值，记录最优路径更新每条路径上的信息素量清空禁忌表及路线表Nc+NcNcMaxN输出结果，结束图 1 基本蚁群算法的程序流程图蚁群算法的模型求解问题（1）费用 TSP 问题的求解根据蚁群算法的解题思路，编写 MATLAB 程序。将各个景点的经纬度坐标转化为高斯坐标，便于MATLAB 的作图。建立文本输入参数，其中权值为两两景点之间的车费，旅游景点门票，住宿费以及餐费等。在车费的选择上在两景点拥有的航班，列车以及长途客运之中选择费用最低的。考虑到住宿的不确定性，以最坏的情况假设每天都需要住宿。Y首先对参数进行初始化。

17、时间t=0，循环次数 NC=0，最大循环次数NCMAX=200，蚂蚁所携带的信息素量为 100，初始时刻kij(0)=0，蚂蚁数量 m=11，景点数 n=11，信息启发式因子为 1，期望启发式因子为 5，信息素挥发系数为，程序运行 5 次，取相对最优解。MATLAB 运行结果为：Shortest_Route=Shoetest_Length=对运行结果的数据进行处理，可以得到以下结论：（1） 最省钱的旅行方案为： 徐州出发洛阳市龙门石窟西安市秦兵马俑山西祁县乔家大院青岛市崂山北京八达岭长城江西九江庐山黄山市黄山常州中华恐龙园舟山市普陀山武汉市黄鹤楼返回徐州，反向亦可。（2） 具体行程：时间事件费

18、用:25从徐州出发，乘 1085 普快（硬座）到达洛阳34 元:00入住于洛阳东宣假日酒店198 元+60 元（吃饭等其他费用）:00在洛阳市龙门石窟游玩 3 小时120 元:06从洛阳出发，乘 1184/1181 普快（硬座）到达西安28 元:00入住于西安西安华清豪泰商务会所130 元+60 元:00在西安市秦始皇兵马俑游玩 2 个小时90 元:45从西安出发，乘 2670 普快（硬座）到达太原45 元:44从太原出发，乘 L7815（硬座）到达祁县13 元:44在祁县乔家大院游玩 3 个小时40 元+60 元:08从祁县出发，乘 4626 次列车（硬座）返回太原7 元:45从太原出发，乘

19、 K884/K881K-快速（硬座）到达青岛120 元:45在青岛市崂山游玩 6 个小时100 元+60 元:38从崂山出发，乘 T26T-特快（硬座）到达北京116 元:00在北京八达岭长城游玩 3 个小时45 元+60 元:14从北京出发，乘坐 1453 普快（硬座）到达九江145 元:00在九江市庐山游玩 7 个小时180 元+60 元:07从庐山出发，乘坐 K13/K12K-快速（硬座）到鹰潭41 元:08从鹰潭出发，乘坐 K156K-快速（硬座）到黄山51 元:00在黄山市黄山游玩 7 个小时230 元+60 元:46从黄山出发，乘 K8420/K8417K-快速（硬座）到常州73

20、元:00在常州市恐龙园游玩 4 个小时160 元+60 元:19从常州出发，乘坐 K57/K78K-快速（硬座）到宁波73 元:40从宁波出发，乘坐大巴+快艇到达普陀山70 元:40在舟山市普陀山游玩 6 个小时160 元+60 元:50从普陀山出发，乘坐大巴+快艇返回宁波70 元:16从宁波出发，乘坐 Z32/Z33Z-直特（硬卧）到武昌143 元:00在武汉市黄鹤楼游玩 2 个小时80 元+60 元:13从汉口出发，乘坐 2614/2615 普快（硬座）返回徐州39 元总计：3201 元表 1 问题 1 的具体行程时间 TSP 问题的求解在本问题这一经典的 TSP 问题模型中，通过对于模型

21、之中城市的集合 L=Lij|Ci，Cj C，可以建立一个与之对应的描述矩阵 D=(dij)描述。由于问题中的限制条件以及时间的不可控性，在假设中选择使用距离的TSP 替代时间的 TSP。根据网络上的数据可知，若选择单一交通工具，旅途中的时间与旅途的长度成正比，而在本题的情况下可以乘坐的航班较少， 在不考虑费用的情况下， 可以近似认为选择的交通工具只有长途汽车与火车两种，且不同车种和班次之间的速度差异可以忽略。那么，仍然根据蚁群算法的解题思路， 使用各个城市的经纬度，转化为高斯坐标进行定位，而两两景点之间的有向线段的权值用城市之间的距离表示， 根据一些既定的班次并对距离做了调整 （可参见附录）。

22、在 MATLAB 算法中对参数初始化后运行程序，运行 5 次得相对最优解如下：Shortest_Route=1Shortest_length=5179作图结果如下：图 2MATLAB 运行结果对程序运行结果进行处理，可以得到以下结论：（1） 按地理经纬度考虑，在蚁群算法循环 200 次的结果下，给旅游者提供以下相对最优的方案：徐州出发常州中华恐龙园舟山市普陀山黄山市黄山九江市庐山武汉市黄鹤楼洛阳市龙门石窟西安市秦始皇兵马俑祁县乔家大院北京市八达岭长城青岛市崂山返回徐州，反向旅行一样不再赘述。（2） 按照此结果，画出地图上的仿真模拟图：图 3 旅行路线仿真模拟图（3） 根据原题中的假设，制定具体

23、的旅游计划如下：时事件费用间:从徐州出发，乘 K58/K55（硬座）到达常州70 元19:189 元+60 元（吃饭等入住于常州福兰特连锁旅店晋陵店00其他费用）:在常州市恐龙园游玩 4 小时160 元00:从常州出发，乘东方航空公司 MU5692 到达北京960 元25:从北京机场换乘中国南方航空股份有限公司 CZ3185 到达宁波1180 元15:入住于宁波格调时尚宾馆148 元00:从宁波出发，乘坐大巴+快艇到达普陀山70 元40:在舟山市普陀山游玩 6 个小时200 元+60 元40:从普陀山出发，乘坐大巴+快艇返回宁波70 元50:入住于宁波格调时尚宾馆148 元02:从宁波出发，乘

24、K8498K-快速（硬座），中转K70/K67K-快速（硬座）92 元25到达黄山:入住黄山宏村清和丹客栈60 元00:00:02:00:46:00:00:35:00:00:05:00:00:00:41:41:07:35:00:00:05:00:00:20在黄山市黄山游玩 7 个小时230 元+60 元从黄山市出发，乘 K70/K67(硬座)，中转 1586/1587 普快（硬座）到92 元达庐山在九江市庐山游玩 7 个小时从庐山出发，乘坐 D3230D-动车（二等软座）到达汉口入住于武汉尚果创意酒店在武汉市黄鹤楼游玩 2 个小时从武汉出发，乘中国南方航空公司 CZ8189，中转杭州，转乘 G

25、52717到达洛阳入住于洛阳东宣假日酒店游玩 3 个小时在洛阳市龙门石窟从洛阳出发，乘坐 K1130/K1131K-快速（硬座）到达西安入住于西安华清豪泰商务会所在西安市秦始皇兵马俑游玩 2 个小时从西安出发，乘坐中国南方航空公司 CZ6319 到达太原从太原出发，乘坐 2602/2603 到达祁县（硬座）在祁县乔家大院游玩 3 个小时从祁县出发，乘坐 L7816（硬座）到达太原从太原出发，乘坐中国海南航空公司 HU7371 到达北京入住于北京新宇桥宾馆在八达岭长城游玩 3 个小时从北京出发，乘坐中国国际航空公司 CA1575 到达青岛入住于青岛海利鑫凤凰山庄在青岛市崂山游玩 6 小时180

26、元+60 元80 元169 元80 元+60 元1620 元198 元120 元+60 元55 元130 元90 元+60 元310 元13 元40 元+60 元7 元300 元188 元45 元+60 元651 元180 元100 元从青岛出发，乘坐山东航空股份有限公司 SC4823，中转徐州，乘坐中1390 元国四川航空公司 3U8814 到达徐州表 2 问题 2 的具体行程试探法求解权值不变时有约束条件 TSP 问题的最优化模型在约束条件下 TSP 问题的模型建立在问题 3、4 中增加了“费用在两千元以内”和“时间在 5 天以内”的约束条件，问题转化为求解汉密尔顿图子集在给定条件下的最优

27、解，使得问题复杂度增加。与无约束条件的单一权值问题相同，首先建立以图为基础的模型。其中：D11D1nD=()为加权描述矩阵；Dn1Dnnx11x1nX=()为决策的 0-1 矩阵xn1xnn对于（3）（4）问之中对于游览景点数最多的要求，0-1 规划矩阵及其子集规模庞大，因此必须具体问题具体分析，结合本题实际情况， 寻找行之有效的算法。由于约束条件，应该先依据权值分配每个景点的优先级， 再依据优先级对 TSP 问题进行动态分析， 选取优先级高的景点试探满足一定条件之下的最优路线，并由蚁群算法得出固定的子集的路径最优解。模型的求解1.问题（3）存在费用约束条件下的最优解本题先用最小元素法进行估计

28、，再由蚁群算法得到最优解，并用试探法验证合理性。（1） 改进的最小元素法最小元素法的宗旨是每一步都取当前的最优值。算法步骤为对费用矩阵 D 做 n 次下列循环：在 D中找到一个最小值 Dij，令 xij=1:；将 D 的第 i 列所有数据改为无穷大，如果ni=1xij=n，可将 D 的i 行数据全部改为正无穷大。在循环过程中记录满足条件的 xij和 xij的个数。由贪婪法，可得满足条件的最优解为徐州北京祁县西安洛阳武汉徐州，最小费用为 1913 元。 可以近似认为满足条件时最多的游览景点数为 5.由于存在时间上的不确定导致费用的波动，将子集的元素个数从 5 个可以扩大至 6 个。根据每个景点的

29、费用，为每个景点加权值，选择其中权值最低的 5 至 6 个景点，用蚁群算法模拟出最优化的解。各个景点的权值可以简化为：Xj=ni=1Ci（2） 调整优化调整优化指的是将一个离最优解很近的初始解调整到调整算法下无法更优的程度。 调整法主要是用试探法对子集的个数进行优化， 也可以通过对蚁群算法的设置优化图形的路线。 采用试探法可以列举出游览不同个数个景点时的费用变化。确定子集个数时的算法仍然由蚁群算法实现。其结果如下：Shortest_Route=4173652Shortest_Length=2390图 3MATLAB 运行结果对所得的数据进行处理，可得以下结果：（1） 具体行程：时间事件费用:0

30、5从徐州出发，乘 K1354/K1351（硬座）到达常州113 元在西安市秦始皇兵马俑游玩 2 个小时90 元+60 元（吃饭等其他费用）:19从西安出发，乘 2670（硬座）到达山西祁县39 元:00在山西祁县乔家大院游玩 3 个小时40 元+60 元:29从山西出发，乘 K237/K240（硬座）到达武汉67 元:00入住于武汉尚果创意酒店169 元:00在武汉市黄鹤楼游玩 2 个小时80 元+60 元:02从武汉出发，乘动车 D3024/D3021（二等软座）到达合肥112 元:10从合肥出发，乘 2025 普快（硬座）到达黄山49 元:00:00:00:07:00:55:00:43入住

31、于黄山宏村清和丹客栈60 元在黄山市黄山游玩 7 个小时230 元+60 元入住于黄山宏村清和丹客栈69 元从黄山出发，乘 K46 快车（硬座）到达北京182 元在八达岭长城游玩 3 个小时45 元+60 元从北京出发，乘 T231 特快列车（硬座）到达洛阳106 元在洛阳市龙门石窟游玩 3 个小时120 元+60 元从洛阳出发，乘 1086 列普快（硬座）返回徐州34 元总计：1839 元表 3 问题 3 的具体行程2.问题（4）存在时间约束条件下的最优解本题与问题（3）类似，仍然是先根据贪婪法求得子集中元素个数的近似解，依据加权后每个景点的优先级筛选优先级高的景点。用蚁群算法实现最优解。其

32、结果如下：图 4MATLAB 运行结果时间事件费用:45从徐州出发，乘 KN2904 航班到达北京550 元:00在八达岭长城游玩 3 个小时45 元+60 元（吃饭等其他费用）:05从北京出发，乘 MU5695 到达洛阳机场787 元:00入住于洛阳东宣假日酒店198 元:00在洛阳市龙门石窟游玩 3 个小时120 元+60 元:13从洛阳出发，乘 K128/125 快车（硬座）到达西安55 元:00入住于西安华清豪泰商务会所130 元:00在西安市秦始皇兵马俑处游玩 2 个小时90 元+60 元:55从西安咸阳机场，乘 MF8218 航班到达武汉天河机场608 元:00在武汉市黄鹤楼游玩

33、2 个小时90 元+60 元:40从武汉天河机场出发，乘 MU2364 航班到达太原武宿机场540 元:08从太原出发，乘 2462/2463 普快（硬座）到达祁县7 元:00在祁县乔家大院游玩 3 个小时40 元+60 元:47从祁县出发，乘 1096 普快（硬座）到达太原7 元:58从太原出发，乘 K374/371 快车（软卧）到达常州458 元:00在常州恐龙园游玩 3 个小时160 元+60 元:48从常州出发，乘 K76/77 快车（硬座）返回徐州70 元表 4 问题 4 的具体行程求解多目标 TSP 问题为综合衡量费用 TSP 与时间 TSP 问题，建立以下模型评价：（1） 确定多

34、目标 TSP 问题的优化模型，本题中只考虑费用与时间两个因素的优化；（2） 给定各个目标因素的优先级。本题中，以费用为第一优先级，时间为第二优先级。（3） 对给定的指标进行无量纲化处理，使得各个指标具有可比性。由费用和时间两个描述矩阵，给定无量纲处理为：D=D/dmin其中，D为处理过后的无量纲矩阵，dmin为描述矩阵中的最小元素。（4） 对费用与时间两个矩阵， 取相同位置坐标的无量纲量进行整合形成一个新的无量纲量， 定为求解矩阵。（5） 用最小元素法确定在满足费用以及时间同时约束时，有向图包涵的原图的子集的元素个数。给定各个景点的优先级，用试探法选取可能为最优的路径。其中每个景点的权值为：X

35、j=ni=1Ci问题（5）多目标 TSP 问题模型求解处理数据后用 MATLAB 进行模拟，所得相对最优解如下：图 5MATLAB 运行结果具体行程如下：时间事件费用:45从徐州出发，乘坐中国联合航空公司 KN2904 航班到达北京550 元:46在北京八达岭长城游玩 3 个小时45 元+60 元:38从北京出发，乘坐 T25T-特快（硬座）到达青岛116 元:00在青岛市崂山游玩 6 个小时100 元+60 元:28从青岛出发，乘坐 1112/1113 普快（硬坐）到达中转站郑州123 元:42从中转站郑州出发，乘坐 K1363K-快速（硬坐）到达西安73 元:24在西安市秦始皇兵马俑游玩

36、2 个小时90 元+60 元:32从西安出发，乘坐 T42T-特快（硬座）到达太原站103 元:08从太原出发，乘 2462/2463 普快（硬座）到达祁县7 元:00在祁县乔家大院游玩 3 小时40+60 元:47从祁县出发，乘坐 1096 普快返回太原7 元:44从太原出发，乘 K520/K521K-特快（硬坐）到达武汉150 元:44在武汉市黄鹤楼游玩 2 个小时80 元+60 元:23从武汉出发，乘 2614/2615 普快（硬坐）返回徐州39 元总计：总计：18231823 元元表 5 问题 5 的具体行程四模型的评价四模型的评价模型的优点(1)算法表示借助了 MATLAB 语言，分

37、析精度高，节约时间，简介形象；（2）蚁群算法与遗传算法，Floyd 算法相比，准确度高；（3）给出的方案具体，详实并且可行。模型的缺点（1）算法具有一定局限性；（2）未详细考虑旅途中的安排与时间的衔接问题；（3）蚁群算法耗时较长。参考文献参考文献1徐莉.基于改进遗传算法的多目标TSP问题研究D.武汉：武汉理工大学2李闻.蚁群优化算法及其应用研究D.长沙：湖南大学，2005.3朱杰.蚁群算法解决TSP问题的浅析J.上海：同济大学，2008；1009-3044(2008)22-724-02.4夏国成，赵佳宝.智能蚂蚁算法求解多目标TSP问题的改进研究.南京：南京大学，2006.5游道明，陈坚.用蚂

38、蚁算法解决多目标TSP问题J.上海,2003(10)18080.6燕忠，袁春伟.用蚁群优化算法求解中国旅行商问题J.南京：东南大学.7汪林林.对“货郎担问题”的研究.重庆：重庆邮电学院.8刘峙麟，李臣，王露.基于层次分析和图论模型的旅游线路设计及其评估.南京：南京大学.9周康，强小利，同小军，许进.求解TSP算法.武汉：华中科技大学.10李敏，吴浪，张开碧.求解旅行商问题的几种算法的比较研究.重庆：重庆邮电大学.11王宇平,李英华.求解TSP的量子遗传算法J.计算机学报,2007,30(5):7482755.12马良，蒋馥多目标旅行售货员问题的蚂蚁算法求解系统程理论方法应用，1999；8(4)

39、：232713杨忠,鲍明,张阿舟.求解中国旅行商问题的新结果J.数据采集与处理,1993,8(3):177-184.14唐建清，邹国霞.基于Floyd算法的旅游路径智能选择系统.上海：华东师范大学15许峰，杜军平.改进蚁群算法在旅游线路规划中的应用研究.北京：北京邮电大学16杨志江，李国欣，张敏.管道订购与运输问题.徐州：中国矿业大学附录1. 基本蚁群算法的 MATLAB 实现2.m=11;3.Alpha=1;4.Beta=5;5.Rho=;6.NC_max=200;7.Q=100;8.C=load(D:);9.D=load(D:);10.n=11;11.Eta=1./D;12.Tau=one

40、s(n,n);13.Tabu=zeros(m,n);14.NC=1;15.R_best=zeros(NC_max,n);16.L_best=inf.*ones(NC_max,1);17.L_ave=zeros(NC_max,1);18.whileNC=rand);45.to_visit=J(Select(1);46.Tabu(i,j)=to_visit;47.end48.end49.ifNC=250.Tabu(1,:)=R_best(NC-1,:);51.end52.%recordthebestroute53.L=zeros(m,1);54.fori=1:m55.R=Tabu(1,:);56.

41、forj=1:(n-1)57.L(i)=L(i)+D(R(j),R(j+1);58.end59.L(i)=L(i)+D(R(1),R(n);60.end61.L_best(NC)=min(L);62.pos=find(L=L_best(NC);63.R_best(NC,:)=Tabu(pos(1),:);64.L_ave(NC)=mean(L);65.NC=NC+1;66.%refresh67.Delta_Tau=zeros(n,n);68.fori=1:m;69.forj=1:(n-1);70.Delta_Tau(Tabu(i,j),Tabu(i,j+1)=Delta_Tau(Tabu(i,

42、j),Tabu(i,j+1)+Q/L(i)71.end72.Delta_Tau(Tabu(i,n),Tabu(i,1)=Delta_Tau(Tabu(i,n),Tabu(i,1)+Q/L(i);73.end74.Tau=(1-Rho).*Tau+Delta_Tau;75.%emptytabu76.Tabu=zeros(m,n);77.end78.Pos=find(L_best=min(L_best);79.shortest_Route=R_best(Pos(1),:)80.Shorest_Length=L_best(Pos(1)81.subplot(1,2,1)82.N=length(R);8

43、3.scatter(C(:,1),C(:,2);84.holdon85.plot(C(R(1),1),C(R(N),1),C(R(1),2),C(R(N),2)86.forii=2:N87.plot(C(R(ii-1),1),C(R(ii),1),C(R(ii-1),2),C(R(ii),2)88.holdon89.end90.subplot(1,2,2)91.plot(L_best)92.holdon93.plot(L_ave)2.各个景点的高斯坐标（3 分度）江苏徐州常州中华恐龙园青岛市崂山北京八达岭长城山西祁县乔家大院洛阳市石门石窟黄山市黄山武汉市黄鹤楼西安市秦始皇兵马俑九江市庐山舟山市

44、普陀山3.各城市之间的距离江常州中苏距离华恐龙徐园州江苏徐州0454常州中华4540恐龙园青岛市崂473714山北京八达7791209岭长城山西祁县7751198乔家大院洛阳市石528864门石窟黄山市黄640452山武汉市黄687738鹤楼西安市秦始皇兵马8101212俑九江市庐631595山舟山市普840396陀山青岛市崂山47371407249479339561146123110401029北京八达岭长城7791209724060188814211328113814711599山西祁县乔家大院77511989476010430130693153711601578洛阳市石门石窟528864

45、933黄山市黄山640452956武汉市黄鹤楼6877381146132893160452808142431009西安市秦始皇兵马俑8101212九江市庐山631595舟山市普陀山8403961029159915781235490100916037790123110401138147153711603591242814817298243888142143013060963604963052835912428171235298490010411041160307794.各城市之间的最低旅行价格江常州中青岛北京八山西祁洛阳市黄山武汉西安市秦九江舟山苏华恐龙市崂达岭长县乔家石门石市黄市黄始皇兵马市庐

46、市普徐园山城大院窟山鹤楼俑山陀山州江苏徐州0471410392412449348335517600常州中华620490433503423414445600574恐龙园青岛市崂705590418503535627445740810山北京八达995494650382431532459430575792岭长城山西祁县3870472517390321乔家大院洛阳市石345344653463820468373308492609门石窟黄山市黄994825254754554960440419475527山武汉市黄395146584433694424810411500541鹤楼西安市秦始皇兵马55574505

47、4433294064894400511654俑九江市庐875796504384403953793610554山舟山市普1405236906255274173904745240陀山5.各城市之间的车旅时间江苏徐州常州中华恐龙园青岛市崂山北京八达岭长城山西祁县乔家大院洛阳市石门石窟黄山市黄山西安武汉市秦市黄始皇鹤楼兵马俑九江市庐山舟山市普陀山江苏徐州常州中华恐龙园青岛市崂山北京八达岭长城山西祁县乔家大院洛阳市石门石窟黄山市黄山武汉001210090900500市黄鹤楼西安市秦始皇兵马俑九江市庐山舟山市普陀山00906.各城市之间的无量纲化整合权值江常州中青岛北京八山西祁洛阳市黄山武汉西安市秦九江舟山苏华恐龙市崂达岭长县乔家石门石市黄市黄始皇兵马市庐市普徐园山城大院窟山鹤楼俑山陀山州江苏徐州0常州中华0恐龙园青岛市崂0山北京八达0岭长城山西祁县0乔家大院洛阳市石0门石窟黄山市黄0山武汉市黄0鹤楼西安市秦始皇兵马0俑九江市庐0山舟山市普0陀山