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

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

1、-数学建模王迪 B09010601 通信工程郑佳佳 B09010603 通信工程孟天舒 B09010604 通信工程题 目 旅游线路的优化设计摘要本题为典型的旅行商问题（TSP），是组合数学中一个古老而又困难的问题，它易于描述却难以完全解决，属于NP完全问题。对于规模较小的旅行商问题，可以通过穷举得到最优解，但随着问题规模的增大空间复杂度急剧增加，需要通过启发式算法求解。由意大利学者M.Dorigo于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点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点。省市景点名称在景点的最短停留时间江苏常州市恐龙园4小时山东青岛市崂山6小时北京八达岭长城3小时山西祁县乔家大院3小时河南洛

5、阳市龙门石窟3小时安徽黄山市黄山7小时湖北武汉市黄鹤楼2小时陕西西安市秦始皇兵马俑2小时江西九江市庐山7小时浙江舟山市普陀山6小时假设：(A) 城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。(B) 市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。(C) 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。(D) 假设景点的开放时间为8:00至18:00。问题：根据以上要求，针对如下的几种情况，

6、为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。(1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。(2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。(3) 如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(4) 如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(5) 如果这位游客只有5天的时间和2000元的旅游费

7、用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。二、 模型假设与符号说明2.1 模型的基本假设（1） 每个景点仅经过一次。（2） 只考虑问题中提供的11个旅游景点，不考虑其他中转地点作为TSP的需求点。（3） 为使问题一定程度上简约化，将城市与路径抽象成点与直线的图论问题。在问题（2）中承认旅行中的车旅费用以及时间与两景点之间距离成正比，以距离的TSP替代时间的TSP。不考虑绕路等特殊情况。在建模时认为两地之间往返的费用时间差异可忽略。（4） 在求解费用最少问题时，模型假设时认为住宿，门票，车旅及餐费都必须包含在内。（5）认为网上公布的机票与车票均可以在任意时刻获得，且班次误点等特

8、殊情况不予考虑，忽略转站中的不合理因素。（6）不考虑天气原因对选择交通工具的影响。（7）关于两地间距离仅作比较参考，一切以路径为准。2.2 符号说明符号名称G 赋权图矩阵C 图中的元素（景点）n 景点的个数D 赋权图的描述矩阵T 访问顺序集合L 最优解（最小费用或最短路程）dti,ti+1 时间ti到ti+1的TSP描述m 蚂蚁的总数量k蚂蚁的编号bi(t) t时刻位于城市i的蚂蚁数目ij(t)t时刻路径（i,j）上的信息量 t时刻C中两两景点之间的残留信息素浓度集合P 初始时刻各路径上的信息素量g(C,L,) 寻优有向图tabuk 第k只蚂蚁的禁忌搜索表pkij(t) 蚂蚁k在t时刻由i城市

9、转向j城市的转移概率 信息启发式因子 期望启发式因子ij(t) 启发函数 信息素挥发系数kij(t) t时刻k蚂蚁在路径ij上留下的信息素量Q 蚂蚁携带的信息素量Lk 本次循环中第k只蚂蚁所走的路程长度NC 所记录的循环次数NCmax 最大循环次数三 模型的建立与求解3.1 基本蚁群算法求解权值不变时单一目标值TSP问题的最优化模型3.1.1 TSP问题的图论阐述 将旅游景点图优化成完全带权图，问题即可抽象成图论问题：令赋权图为G=(C,L)，其中C=C1,C2,Cn为节点，表示各个景点的集合；L=Lij|Ci，CjC表示各个景点之间的路径，每两个景点间的路径lij都有相关的权值dij与之对应

10、，从而建立起一个D=（dij）矩阵，权值可以表示距离、费用、路径等。由于题目的相关要求可以抽象出一个典型旅行商问题的数学模型：minL=i=1nd ti,ti+13.1.2 基本的蚁群算法模型基本思想：蚁群算法是一种通过模拟自然界蚂蚁寻径的行为的进化算法。蚂蚁群找到食物时,它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素，当它们碰到一个还没有走过的路口时,就随机地挑选一条路径前行，与此同时释放出与路线长度有关的信息素，路径越长,释放的激素浓度越低，当后来的蚂蚁再次碰到这个路口的时候,选择激素浓度较高路径概率就会相对较大，这样形成了一个正反馈。

11、最优路径上的激素浓度越来越大,而其它的路径上激素浓度却会随着时间的流逝而消减。这样,整个蚁群最终会找出最优路径。用bi(t)表示城市i的蚂蚁数目，表示t时段路径（i，j）上的信息量，n表示景点的个数，m为蚂蚁的总数量，则m=i=1nbit初试时刻，各条路径上信息量相等，均为P，（0）=P。又因为蚂蚁不能重复经过同一个城市，因此建立禁忌表（或记录未走过的路径Jk）tabuk(k取正整数)来记录蚂蚁走过的城市，并随时间做动态调整。被随机分散在个节点的只蚂蚁同时出发，按照下面的概率公式逐次访问各个城市节点：蚂蚁以概率访问下一个节点： 在这里，有表示边上的信息素强度。表示由节点到节点的启发函数，显然距

12、离越长期望度越低，所以在此将设为。随着时间的推移, 可能会出现两种情况: 之前各蚂蚁留下的信息素逐渐消失；经过多次循环后，路径上的残留信息素过多，淹没了期望程度对蚂蚁选择路径的影响。为了避免这两种情况, 在每一只蚂蚁完成一次循环后，我们对引入参数对残留的信息素进行更新。为信息素的挥发速率，是在0,1间取值的可变量,用于控制两种信息素的比重。设经过个时间单位后, 蚂蚁完成一次循环, 各路径上的信息素的量根据以下式子作出调整：蚂蚁在本次循环中留在路径上的信息素强度。：蚂蚁留在路径上的信息素强度。当蚁群完成了所有的节点的访问后，在原路返回的过程中，根据所得的解的好坏去修改路径上的信息素强度，以此来引

13、导其他蚂蚁对该路径的选择，从而达到群体协作的目的，最后判断系统是否满足停止的条件（停止条件可以是最大的迭代次数，计算机运行时间，或者是达到系统所要达到的数据精度等），如果条件不满足，则蚁群又重新开始搜索路径，建立新的解；否则，系统将退出运行，将所得的结果输出。从上面可以看出，蚁群优化算法的基本思想就是质量越好的解和距离越短的路径就越能吸引更多的蚂蚁。蚁群正是通过这种反复记忆和学习的过程，得到了最短路径，即全局最优解。我们将各城市的经纬度通过球面坐标系的转化分别投影到一个二维平面上点的横纵坐标，在求解的时候可直接求出两地的直线距离，即为。3.1.3基本蚁群算法的算法流程在本题中，基本蚁群算法的具

14、体实现步骤如下：1. 参数初始化：令t=0；设置最大循环次数NcMax，循环次数Nc=0；将m只蚂蚁置于n个节点上，在每个节点i放置bi(t)只蚂蚁；初始化每条边(i,j)上的信息素量tij(0)=c为一个常量，初始时刻Dtijk(0)=0；初始化禁忌表tabuk和路径表Lk。2. 设置索引号s=1，对k=1m将蚂蚁k的起始城市放入禁忌表中，并重复以下步骤直至禁忌表填充完整：对k=1m，利用公式计算转移概率pij，根据伪随机比例规则选择下一景点，将蚂蚁k移动到下一景点j并将其填入禁忌表，同时记录蚂蚁k的路线，索引号自增。3. 对k=1m，根据Lk的记录计算蚂蚁k所走循环路径的总长度，找到最佳路

15、线4.计算每只蚂蚁的信息素增量Dkij(t)5. 更新每条路径上的信息素量kij(t+n)6. 清空禁忌表及路线表。7. Nc+，若NcNcMax，返回步骤2，否则，循环结束。开始初始化索引号s=1k=k+1蚂蚁k=1计算转移概率pij，选择下一节点j修改禁忌表，记录路线s=s+1根据记录计算权值，记录最优路径更新每条路径上的信息素量k蚂蚁总数mNYsnNY清空禁忌表及路线表NcNcMaxNc+输出结果，结束YN图1 基本蚁群算法的程序流程图3.2 蚁群算法的模型求解3.2.1问题（1）费用TSP问题的求解根据蚁群算法的解题思路，编写MATLAB程序。将各个景点的经纬度坐标转化为高斯坐标，便于

16、MATLAB的作图。建立文本输入参数，其中权值为两两景点之间的车费，旅游景点门票，住宿费以及餐费等。在车费的选择上在两景点拥有的航班，列车以及长途客运之中选择费用最低的。考虑到住宿的不确定性，以最坏的情况假设每天都需要住宿。首先对参数进行初始化。时间t=0，循环次数NC=0，最大循环次数NCMAX=200，蚂蚁所携带的信息素量为100，初始时刻kij(0)=0，蚂蚁数量m=11，景点数n=11，信息启发式因子为1，期望启发式因子为5，信息素挥发系数为0.7，程序运行5次，取相对最优解。MATLAB运行结果为：Shortest_Route=11 8 1 6 9 5 3 4 10 7 2Shoet

17、est_Length=750.5对运行结果的数据进行处理，可以得到以下结论：（1） 最省钱的旅行方案为：徐州出发洛阳市龙门石窟西安市秦兵马俑山西祁县乔家大院青岛市崂山北京八达岭长城江西九江庐山黄山市黄山常州中华恐龙园舟山市普陀山武汉市黄鹤楼返回徐州，反向亦可。（2） 具体行程：时间事件费用5.1 13:40-5.1 19:25从徐州出发，乘1085普快（硬座）到达洛阳34元5.1 19:25-5.2 8:00入住于洛阳东宣假日酒店198元+60元（吃饭等其他费用）5.2 8:00-5.2 11:00在洛阳市龙门石窟游玩3小时120元5.2 17:55-5.2 23:06从洛阳出发，乘1184/

18、1181普快（硬座）到达西安28元5.2 23:06-5.3 08:00入住于西安西安华清豪泰商务会所130元+60元5.3 08:00-5.3 10:00在西安市秦始皇兵马俑游玩2个小时90元5.3 20:52-5.4 07:45从西安出发，乘2670普快（硬座）到达太原45元5.4 08:30-5.4 09:44从太原出发，乘L7815（硬座）到达祁县13元5.4 09:44-5.4 12:44在祁县乔家大院游玩3个小时40元+60元5.4 14:55-5.4 16:08从祁县出发，乘4626次列车（硬座）返回太原7元5.4 21:36-5.5 08:45从太原出发，乘K884/K881

19、K-快速 （硬座）到达青岛120元5.5 08:45-5.5 14:45在青岛市崂山游玩6个小时100元+60元5.5 20:07-5.6 05:38从崂山出发，乘T26 T-特快 （硬座）到达北京116元5.6 08:00-5.6 11:00在北京八达岭长城游玩3个小时45元+60元5.6 12:14-5.7 04:14从北京出发，乘坐1453普快（硬座）到达九江145元5.7 08:00-5.7 15:00在九江市庐山游玩7个小时180元+60元5.7 19:42-5.7 23:07从庐山出发，乘坐K13/K12 K-快速 （硬座）到鹰潭41元5.7 23:11-5.8 04:08从鹰潭出

20、发，乘坐K156 K-快速（硬座）到黄山51元5.8 08:00-5.8 15:00在黄山市黄山游玩7个小时230元+60元5.8 19:10-5.9 04:46从黄山出发，乘K8420/K8417 K-快速 （硬座）到常州73元5.9 08:00-5.9 12:00在常州市恐龙园游玩4个小时160元+60元5.9 22:30-5.10 05:19从常州出发，乘坐K57/K78 K-快速 （硬座）到宁波73元5.10 06:30-5.10 08:40从宁波出发，乘坐大巴+快艇到达普陀山70元5.10 08:40-5.10 14:40在舟山市普陀山游玩6个小时160元+60元5.10 14:40

21、-5.10 16:50从普陀山出发，乘坐大巴+快艇返回宁波70元5.10 21:28-5.11 07:16从宁波出发，乘坐Z32/Z33 Z-直特（硬卧）到武昌143元5.11 08:00-5.11 10:00在武汉市黄鹤楼游玩2个小时80元+60元5.11 16:54-5.12 04:13从汉口出发，乘坐2614/2615普快（硬座）返回徐州39元总计：3201元表1 问题1的具体行程3.2.2问题（2）时间TSP问题的求解在本问题这一经典的TSP问题模型中，通过对于模型之中城市的集合L= Lij|Ci，CjC ，可以建立一个与之对应的描述矩阵D=(dij)描述。由于问题中的限制条件以及时间

22、的不可控性，在假设中选择使用距离的TSP替代时间的TSP。根据网络上的数据可知，若选择单一交通工具，旅途中的时间与旅途的长度成正比，而在本题的情况下可以乘坐的航班较少，在不考虑费用的情况下，可以近似认为选择的交通工具只有长途汽车与火车两种，且不同车种和班次之间的速度差异可以忽略。那么，仍然根据蚁群算法的解题思路，使用各个城市的经纬度，转化为高斯坐标进行定位，而两两景点之间的有向线段的权值用城市之间的距离表示，根据一些既定的班次并对距离做了调整（可参见附录）。在MATLAB算法中对参数初始化后运行程序，运行5次得相对最优解如下：Shortest_Route=1 2 11 7 10 8 6 9 5

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

24、到达常州70元5.1 15:19-5.2 08:00入住于常州福兰特连锁旅店晋陵店189元+60元（吃饭等其他费用）5.2 08:00-5.2 12:00在常州市恐龙园游玩4小时160元5.2 14:40-5.2 16:25从常州出发，乘东方航空公司MU5692到达北京960元5.2 19:10-5.2 21:15从北京机场换乘中国南方航空股份有限公司CZ3185到达宁波1180元5.2 21:15-5.3 08:00入住于宁波格调时尚宾馆148元5.3 06:30-5.3 08:40从宁波出发，乘坐大巴+快艇到达普陀山70元5.3 08:40-5.3 14:40在舟山市普陀山游玩6个小时20

25、0元+60元5.3 14:40-5.3 16:50从普陀山出发，乘坐大巴+快艇返回宁波70元5.3 16:50-5.4 09:02入住于宁波格调时尚宾馆148元5.4 09:02-5.4 18:25从宁波出发，乘K8498 K-快速（硬座），中转K70/K67 K-快速（硬座）到达黄山92元5.4 18:25-5.5 08:00入住黄山宏村清和丹客栈60元5.5 08:00-5.5 15:00在黄山市黄山游玩7个小时230元+60元5.5 18:28-5.6 03:02从黄山市出发，乘K70/K67(硬座)，中转1586/1587 普快（硬座）到达庐山92元5.6 08:00-5.6 15:0

26、0在九江市庐山游玩7个小时180元+60元5.6 19:33-5.6 21:46从庐山出发，乘坐D3230 D-动车（二等软座）到达汉口80元5.6 21:46-5.7 08:00入住于武汉尚果创意酒店169元5.7 08:00-5.7 10:00在武汉市黄鹤楼游玩2个小时80元+60元5.7 10:10-5.7 16:35从武汉出发，乘中国南方航空公司CZ8189，中转杭州，转乘G52717到达洛阳1620元5.7 16:35-5.8 08:00入住于洛阳东宣假日酒店198元5.8 08:00-5.8 11:00游玩3个小时在洛阳市龙门石窟120元+60元5.8 11:01-5.8 16:0

27、5从洛阳出发，乘坐K1130/K1131 K-快速 （硬座）到达西安55元5.8 16:05-5.9 08:00入住于西安华清豪泰商务会所130元5.9 08:00-5.9 10:00在西安市秦始皇兵马俑游玩2个小时90元+60元5.9 10:50-5.9 12:00从西安出发，乘坐中国南方航空公司CZ6319到达太原310元5.9 12:27-5.9 13:41从太原出发，乘坐2602/2603到达祁县（硬座）13元5.9 13:41-5.9 16:41在祁县乔家大院游玩3个小时40元+60元5.9 16:49-5.9 18:07从祁县出发，乘坐L7816（硬座）到达太原7元5.9 18:1

28、5-5.9 19:35从太原出发，乘坐中国海南航空公司HU7371到达北京300元5.9 19:35-5.10 08:00入住于北京新宇桥宾馆188元5.10 08:00-5.10 11:00在八达岭长城游玩3个小时45元+60元5.10 13:45-5.10 15:05从北京出发，乘坐中国国际航空公司CA1575到达青岛651元5.10 15:05-5.11 08:00入住于青岛海利鑫凤凰山庄180元5.11 08:00-5.11 14:00在青岛市崂山游玩6小时100元5.11 15:25-5.11 20:20从青岛出发，乘坐山东航空股份有限公司SC4823，中转徐州，乘坐中国四川航空公司

29、3U8814到达徐州1390元表2 问题2的具体行程3.2 试探法求解权值不变时有约束条件TSP问题的最优化模型3.2.1 在约束条件下TSP问题的模型建立在问题3、4中增加了“费用在两千元以内”和“时间在5天以内”的约束条件，问题转化为求解汉密尔顿图子集在给定条件下的最优解，使得问题复杂度增加。与无约束条件的单一权值问题相同，首先建立以图为基础的模型。其中：D=D11D1nDn1Dnn为加权描述矩阵；X=x11x1nxn1xnn为决策的0-1矩阵对于（3）（4）问之中对于游览景点数最多的要求，0-1规划矩阵及其子集规模庞大，因此必须具体问题具体分析，结合本题实际情况，寻找行之有效的算法。由于

30、约束条件，应该先依据权值分配每个景点的优先级，再依据优先级对TSP问题进行动态分析，选取优先级高的景点试探满足一定条件之下的最优路线，并由蚁群算法得出固定的子集的路径最优解。3.2.2 模型的求解1.问题（3）存在费用约束条件下的最优解本题先用最小元素法进行估计，再由蚁群算法得到最优解，并用试探法验证合理性。（1） 改进的最小元素法最小元素法的宗旨是每一步都取当前的最优值。算法步骤为对费用矩阵D做n次下列循环：在D中找到一个最小值Dij，令xij=1:；将D的第i列所有数据改为无穷大，如果i=1nxij=n，可将D的i行数据全部改为正无穷大。在循环过程中记录满足条件的xij和xij的个数。由贪

31、婪法，可得满足条件的最优解为徐州北京祁县西安洛阳武汉徐州，最小费用为1913元。可以近似认为满足条件时最多的游览景点数为5.由于存在时间上的不确定导致费用的波动，将子集的元素个数从5个可以扩大至6个。根据每个景点的费用，为每个景点加权值，选择其中权值最低的5至6个景点，用蚁群算法模拟出最优化的解。各个景点的权值可以简化为：Xj=i=1nCi（2） 调整优化调整优化指的是将一个离最优解很近的初始解调整到调整算法下无法更优的程度。调整法主要是用试探法对子集的个数进行优化，也可以通过对蚁群算法的设置优化图形的路线。采用试探法可以列举出游览不同个数个景点时的费用变化。确定子集个数时的算法仍然由蚁群算法

32、实现。其结果如下：Shortest_Route=4 1 7 3 6 5 2Shortest_Length=2390图3 MATLAB运行结果对所得的数据进行处理，可得以下结果：（1） 具体行程：时间事件费用5.1 14:05-5.2 02:05从徐州出发，乘K1354/K1351（硬座）到达常州113元5.2 08:00-5.2.10:00 在西安市秦始皇兵马俑游玩2个小时90元+60元（吃饭等其他费用）5.2 20:52-5.3 06:19从西安出发，乘2670（硬座）到达山西祁县39元5.3 08:00-5.3 11:00在山西祁县乔家大院游玩3个小时40元+60元5.3 13:47-5.

33、3 21:29从山西出发，乘K237/K240（硬座）到达武汉67元5.3 21:19-5.4 08:00入住于武汉尚果创意酒店169元5.4 08:00-5.4 10:00在武汉市黄鹤楼游玩2个小时80元+60元5.4 12:47-5.4 15:02从武汉出发，乘动车D3024/D3021（二等软座）到达合肥112元5.4 15:17-5.4 21:10从合肥出发，乘2025普快（硬座）到达黄山49元5.4 21:10-5.5 08:00入住于黄山宏村清和丹客栈60元5.5 08:00-5.5 15:00在黄山市黄山游玩7个小时230元+60元5.5 15:00-5.6 09:00入住于黄山

34、宏村清和丹客栈69元5.6 09:21-5.7 05:07从黄山出发，乘K46快车（硬座）到达北京182元5.7 08:00-5.7 11:00在八达岭长城游玩3个小时45元+60元5.7 16:55-5.8 01:55从北京出发，乘T231特快列车（硬座）到达洛阳106元5.6 08:00-5.6 11:00在洛阳市龙门石窟游玩3个小时120元+60元5.6 12:47-5.6 18:43从洛阳出发，乘1086列普快（硬座）返回徐州34元总计：1839元表3 问题3的具体行程2.问题（4）存在时间约束条件下的最优解本题与问题（3）类似，仍然是先根据贪婪法求得子集中元素个数的近似解，依据加权后

35、每个景点的优先级筛选优先级高的景点。用蚁群算法实现最优解。其结果如下：图4 MATLAB运行结果时间事件费用5.1 09:35-5.1 10:45从徐州出发，乘KN2904航班到达北京550元5.1 12:00-5.1 15:00 在八达岭长城游玩3个小时45元+60元（吃饭等其他费用）5.1 19:20-5.1 21:05从北京出发，乘MU5695到达洛阳机场787元5.1 22:00-5.2 08:00入住于洛阳东宣假日酒店198元5.2 08:00-5.2 11:00在洛阳市龙门石窟游玩3个小时120元+60元5.2 14:53-5.2 20:13从洛阳出发，乘K128/125快车（硬座

36、）到达西安55元5.2 21:00-5.3 08:00入住于西安华清豪泰商务会所130元5.3 08:00-5.3 10:00在西安市秦始皇兵马俑处游玩2个小时90元+60元5.3 11:50-5.3 12:55从西安咸阳机场，乘MF8218航班到达武汉天河机场608元5.3 14:00-5.3 16:00在武汉市黄鹤楼游玩2个小时90元+60元5.3 22:20-5.3 23:40从武汉天河机场出发，乘MU2364航班到达太原武宿机场540元5.4 05:00-5.4 06:08从太原出发，乘2462/2463普快（硬座）到达祁县7元5.4 08:00-5.4 11:00在祁县乔家大院游玩3

37、个小时40元+60元5.4 12:29-5.4 13:47从祁县出发，乘1096普快（硬座）到达太原7元5.4 17:53-5.5 12:58从太原出发，乘K374/371快车（软卧）到达常州458元5.5 14:00-5.5 18:00在常州恐龙园游玩3个小时160元+60元5.6 00:09-5.6 05:48从常州出发，乘K76/77快车（硬座）返回徐州70元表4 问题4的具体行程3.3 求解多目标TSP问题3.3.1多目标TSP问题的模型建立为综合衡量费用TSP与时间TSP问题，建立以下模型评价：（1） 确定多目标TSP问题的优化模型，本题中只考虑费用与时间两个因素的优化；（2） 给定

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

39、进行模拟，所得相对最优解如下：图5 MATLAB运行结果具体行程如下：时间事件费用5.1 09:35-5.1 10:45从徐州出发，乘坐中国联合航空公司KN2904航班到达北京550元5.1 10:45-5.1 13:46在北京八达岭长城游玩3个小时45元+60元5.1 22:48-5.2 07:38从北京出发，乘坐T25 T-特快（硬座）到达青岛116元5.2 08:00-5.2 14:00在青岛市崂山游玩6个小时100元+60元5.2 15:16-5.3 05:28从青岛出发，乘坐1112/1113普快（硬坐）到达中转站郑州123元5.3 06:02-5.3 12:42从中转站郑州出发，乘

40、坐K1363 K-快速（硬坐）到达西安73元5.3 12:24-5.3 14:24在西安市秦始皇兵马俑游玩2个小时90元+60元5.3 18:20-5.4 03:32从西安出发，乘坐T42 T-特快（硬座）到达太原站103元5.4 05:00-5.4 06:08从太原出发，乘2462/2463 普快（硬座）到达祁县7元5.4 08:00-5.4 11:00在祁县乔家大院游玩3小时40+60元5.4 12:29-5.4 13:47从祁县出发，乘坐1096普快返回太原7元5.4 18:01-5.5 09:44从太原出发，乘K520/K521 K-特快（硬坐）到达武汉150元5.5 09:44-5.

41、5 11:44在武汉市黄鹤楼游玩2个小时80元+60元5.5 18:40-5.6 04:23从武汉出发，乘2614/2615 普快（硬坐）返回徐州39元总计：1823元表5 问题5的具体行程四 模型的评价4.1模型的优点(1)算法表示借助了MATLAB语言，分析精度高，节约时间，简介形象；（2）蚁群算法与遗传算法，Floyd算法相比，准确度高；（3）给出的方案具体，详实并且可行。4.2模型的缺点（1）算法具有一定局限性；（2）未详细考虑旅途中的安排与时间的衔接问题；（3）蚁群算法耗时较长。参考文献1 徐 莉. 基于改进遗传算法的多目标TSP问题研究D .武汉： 武汉理工大学2 李 闻. 蚁群优

42、化算法及其应用研究D.长沙：湖南大学，2005.3 朱 杰. 蚁群算法解决TSP问题的浅析J.上海：同济大学，2008；1009- 3044(2008)22- 724-02.4 夏国成，赵佳宝.智能蚂蚁算法求解多目标TSP问题的改进研究.南京：南京大学，2006.5 游道明，陈坚.用蚂蚁算法解决多目标TSP问题J.上海 ,2003(10)18080.6 燕忠，袁春伟.用蚁群优化算法求解中国旅行商问题J.南京：东南大学.7 汪林林.对“货郎担问题”的研究.重庆：重庆邮电学院.8 刘峙麟，李臣，王露.基于层次分析和图论模型的旅游线路设计及其评估.南京：南京大学.9 周康，强小利，同小军，许进.求解TSP算法.武汉：华中科技大学.10 李敏，吴浪，张开碧.求解旅行商问题的几种算法的比较研究.重庆：重庆邮电大学.11 王宇平,李英华. 求解TSP的量子遗传算法J. 计算机学报, 2007, 30 (5) : 7482755.12 马良，蒋馥多目标旅行售货员问题的蚂蚁算法求解系统程理论方法应用，1999；8(4)：232713 杨忠, 鲍明, 张阿舟. 求解中国旅行商问题的新结果 J. 数据采集与处理, 1993, 8(3): 177-184.14唐建清，邹国霞. 基于Floyd算法的旅游路径智能选择系统.上海：华东师范大学15许峰，杜军平.改进蚁群算法在旅游线路规划中的应用研究.北京