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

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

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

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

4、4天21小时48分。(5)第五问寻求综合因素优化的问题，通过计算给出评价模型，将价格和费用整合 到一个无量纲描述矩阵中。再通过试探法得出最优的方案。最佳路线为：徐 州一一北京一一青岛一一西安一一祁县一一武汉一一徐州，总时长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替代时间的TSR不考虑绕路等特殊情况。在建模时认为两地之间往 返的费用时间

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

9、的残留信息素浓度集合p初始时刻各路径上的信息素量g(C,L,)寻优有何图tabu k第k只蚂蚁的禁忌搜索表pkj (t)蚂蚁k在t时刻由i城市转向j城市的转移概率a信息启发式因子B期望启发式因子4j启发函数P信息素挥发系数k T j (t)t时亥ij k蚂蚁在路径ij上留下的信息素量Q蚂蚁携带的信息素量Lk本次循环中第k只蚂蚁所走的路程长度Nd所记录的循环次数Nmax最大循环次数三模型的建立与求解3.1 基本蚁群算法求解权值不变时单一目标值 TSP问题的最优化模型3.1.1 TSP问题的图论阐述将旅游景点图优化成完全带权图，问题即可抽象成图论问题：令赋权图为G=(C,L),其中C=G,C2,G

10、为节点，表示各个景点的集合；L=Lj|Ci , Cj £C表示各个景点之间的路径，每两个景点间的路径lj都有相关的权值dj与之对应， 从而建立起一个D= (dj)矩阵，权值可以表示距离、费用、路径等。由于题目的相关要 求可以抽象出一个典型旅行商问题的数学模型：minL上 lI til 1 13.1.2 基本的蚁群算法模型基本思想：蚁群算法是一种通过模拟自然界蚂蚁寻径的行为的进化算法。蚂蚁群找 到食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径 时会在路径上释放出一种特殊的信息素，当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行，与此同时释放出与路线

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

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

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

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

15、径表Lk。2 .设置索引号s=1,对k=1m#蚂蚁k的起始城市放入禁忌表中，并重复以下步骤直至 禁忌表填充完整：对k=1m利用公式计算转移概率pj ,根据伪随机比例规则选择下一景点，将蚂蚁 k移 动到下一景点j并将其填入禁忌表，同时记录蚂蚁 k的路线，索引号自增。3 .对k=1m根据Lk的记录计算蚂蚁k所走循环路径的总长度，找到最佳路线4 .计算每只蚂蚁的信息素增量？ r kj (t)5 .更新每条路径上的信息素量 r kj (t+n)6 .清空禁忌表及路线表。7 .Nc+,若Nc<N®ax,返回步骤2,否则，循环结束。图1基本蚁群算法的程序流程图3.2蚁群算法的模型求解3.2

16、.1 问题(1)费用TSP问题的求解根据蚁群算法的解题思路，编写 MATLA勰序。将各个景点的经纬度坐标转化为高斯坐 标，便于MATLAB勺作图。建立文本输入参数，其中权值为两两景点之间的车费，旅游 景点门票，住宿费以及餐费等。在车费的选择上在两景点拥有的航班，列车以及长途客 运之中选择费用最低的。考虑到住宿的不确定性，以最坏的情况假设每天都需要住宿。首先对参数进行初始化。时间t=0 ,循环次数NC=0最大循环次数NCMAX=200蚂蚁所 携带的信息素量为100,初始时刻 r kj （0）=0 ,蚂蚁数量m=11景点数n=11,信息启 发式因子为1,期望启发式因子为5,信息素挥发系数为0.7,

17、程序运行5次，取相对最 优解。MATLA运行结果为：Shortest_Route=1181695341072Shoetest_Length=750.5对运行结果的数据进行处理，可以得到以下结论：（1）最省钱的旅行方案为：徐州出发一一洛阳市龙门石窟一一西安市秦兵马俑一一山 西祁县乔家大院一一青岛市崂山一一北京八达岭长城一一江西九江庐山一一黄 山市黄山一一常州中华恐龙园一一舟山市普陀山一一武汉市黄鹤楼一一返回徐州，反向亦可。（2）具体行程：时间事件费用5.113:40-5.119:25从徐州出发，乘1085普快（硬座）到达 洛阳34元5.119:25-5.28:00入住于洛阳东宣假日酒店198兀+

18、60兀（吃饭等其他 费用）5.28:00-5.211:00在洛阳市龙门石窟游玩3小时120元5.217:55-5.223 :06从洛阳出发，乘1184/1181普快（硬座） 到达西安28元5.223:06-5.308 :00入住于西安西安华清彖泰商务会所130元+60元5.308:00-5.310 :00在西安市秦始皇兵马俑游玩2个小时90元5.320:52-5.407 :45从西安出发，乘2670普快（硬座）到达 太原45元5.408:30-5.409 :44从太原出发，乘L7815 （硬座）到达祁县13元5.409:44-5.412 :44在祁县乔家大院游玩3个小时40元+60元5.414

19、:55-5.416:08从祁县出发，乘4626次列车（硬座）返 回太原7元5.421:36-5.508 :45从太原出发，乘K884/K881K-快速（硬座） 到达青岛120元5.508:45-5.514 :45在青岛市崂山游玩6个小时100元+60元5.520:07-5.605:38从崂山出发，乘T26T-特快（硬座）到达 北京116元5.608:00-5.611 :00在北京八达岭长城游玩3个小时45元+60元5.612:14-5.704 :14从北京出发，乘坐1453普快（硬座）到 达九江145元5.708:00-5.715 :00在九江巾庐山游玩7个小时180元+60元5.719:42

20、-5.723:07从庐山出发，乘坐K13/K12K-快速（硬座） 到鹰潭41元5.723:11-5.804 :08从鹰潭出发，乘坐K156K-快速（硬座） 到黄山51元5.808:00-5.815 :00在黄山市黄山游玩7个小时230元+60元5.819:10-5.904 :46从黄山出发，乘K8420/K8417K-快速（硬座）到常州73元5.908:00-5.912 :00在常州市恐龙园游玩4个小时160元+60元5.922:30-5.1005:19从常州出发，乘坐K57/K78K-快速（硬座） 到宁波73元5.1006:30-5.1008:40从宁波出发，乘坐大巴+快艇到达普陀山70元5

21、.1008:40-5.10 14:40在舟山巾普陀山游玩6个小时160元+60元5.1014:40-5.1016:50从普陀山出发，乘坐大巴+快艇返回宁波70元5.1021:28-5.1107:16从宁波出发，乘坐Z32/Z33Z-直特（硬卧） 到武昌143元5.1108:00-5.1110:00在武汉市黄鹤楼游玩2个小时80元+60元5.1116:54-5.1204:13从汉口出发，乘坐2614/2615普快（硬座） 返回徐州39元总计：3201元表1问题1的具体行程时间TSP问题的求解在本问题这一经典的TSP问题模型中，通过对于模型之中城市的集合 L=Lj |C, C C, 可以建立一个与

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

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

24、间事件费用5.109:355.115:19从徐州出发，乘K58/K55 （硬座）到达常州70元5.115:195.208:00入住于常州福兰特连锁旅店晋陵店189元+60元（吃 饭等具他费用）5.208:005.212:00在常州市恐龙园游玩4小时160元5.214:405.216:25从常州出发，乘东方航空公司 MU5692SJ达北京960元5.219:105.221:15从北京机场换乘中国南方航空股份有限公司CZ3185IJ达宁波1180 元5.221:155.308:00入住于宁波格调时尚宾馆148元5.306:305.308:40从宁波出发，乘坐大巴+快艇到达普陀山70元5.308:4

25、05.314:40在舟山巾普陀山游玩6个小时200元+60元5.314:405.316:50从普陀山出发，乘坐大巴+快艇返回宁波70元5.316:505.409:02入住于宁波格调时尚宾馆148元5.409:025.418:25从宁波出发，乘K8498K-快速（硬座）,中转K70/K67K- 快速（硬座）到达黄山92元5.418:255.508:00入住黄山宏村清和丹客栈60元5.508:005.515:00在黄山市黄山游玩7个小时230元+60元5.518:285.603:02从黄山市出发，乘K70/K67（硬座），中转1586/1587普快（硬座）到达庐山92元5.608:00-在九江巾庐

26、山游玩7个小时180元+60元5.615:005.619:335.621:46从庐山出发，乘坐D3230D动车（二等软座）到达汉口80元5.621:465.708:00入住于武汉尚果创意酒店169元5.708:005.710:00在武汉市黄鹤楼游玩2个小时80元+60元5.710:105.716:35从武汉出发，乘中国南方航空公司CZ8189中转杭州，转乘G52717到达洛阳1620 元5.716:355.808:00入住于洛阳东宣假日酒店198元5.808:005.811:00游玩3个小时在洛阳市龙门石窟120元+60元5.811:015.816:05从洛阳出发，乘坐K1130/K1131K

27、-快速（硬座）到达西 安55元5.816:055.908:00入住于西安华清彖泰商务会所130元5.908:005.910:00在西安巾秦始皇兵马俑游玩2个小时90元+60元5.910:505.912:00从西安出发，乘坐中国南方航空公司 CZ631S0达太原310元5.912:275.913:41从太原出发，乘坐2602/2603到达祁县（硬座）13元5.913:415.916:41在祁县乔家大院游玩3个小时40元+60元5.916:495.918:07从祁县出发，乘坐L7816 （硬座）到达太原7元5.918:155.919:35从太原出发，乘坐中国海南航空公司 HU7371到达北京300

28、元5.919:355.1008:00入住于北京新宇桥宾馆188元5.1008:00 -5.1011:00在八达岭长城游玩3个小时45元+60元5.1013:45 -5.1015:05从北京出发，乘坐中国国际航空公司 CA1575&J达青岛651元5.1015:05 -5.1108:00入住于青岛海利鑫凤凰山庄180元5.1108:00 -5.1114:00在青岛市崂山游玩6小时100元5.1115:25从青岛出发，乘坐山东航空股份有限公司 SC4823中1390 元-5.1120:2转徐州，乘坐中国四川航空公司 3U8814至IJ达徐州0表2问题2的具体行程3.2试探法求解权值不变时有

29、约束条件 TSP问题的最优化模型3.2.1 在约束条件下TSP问题的模型建立在问题3、4中增加了 “费用在两千元以内”和“时间在5天以内”的约束条件，问题转化为求解汉密尔顿图子集在给定条件下的最优解，使得问题复杂度增加。与无约束条件的单一权值问题相同，首先建立以图为基础的模型。其中：fDll ? DimD=Dnl :为加权描述矩阵；rxll ? xlm77?X'rii 7为决策的0-1矩阵i f xrni/对于(3) (4)问之中对于游览景点数最多的要求，0-1规划矩阵及其子集规模庞大， 因此必须具体问题具体分析，结合本题实际情况，寻找行之有效的算法。由于约束条件， 应该先依据权值分配

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

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

32、如下：Shortest_Route=4173652Shortest_Length=2390图3MATLA运行结果对所得的数据进行处理，可得以下结果:（1）具体行程:时间事件费用5.114:05-5.202:05从徐州出发，乘K1354/K1351 （硬座）到达 常州113元在西安巾秦始皇兵马俑游玩2个小时90元+60元（吃饭等具他 费用）5.220:52-5.306:19从西安出发，乘2670 （硬座）到达山西祁县39元5.308:00-5.311:00在山西祁县乔家大院游玩3个小时40元+60元5.313:47-5.321:29从山西出发，乘K237/K240 （硬座）到达武 汉67元5.3

33、21:19-5.408:00入住于武汉尚果创意酒店169元5.408:00-5.410:00在武汉市黄鹤楼游玩2个小时80元+60元5.412:47-5.415:02从武汉出发，乘动车D3024/D3021 （二等软 座）到达合肥112元5.415:17-5.421:10从合肥出发，乘2025普快（硬座）到达黄 山49元5.421:10-5.508:00入住于黄山宏村清和丹客栈60元5.508:00-5.515:00在黄山市黄山游玩7个小时230元+60元5.515:00-5.609:00入住于黄山宏村清和丹客栈69元5.609:21-5.705:07从黄山出发，乘K46快车（硬座）到达北京1

34、82元5.708:00-5.711:00在八达岭长城游玩3个小时45元+60元5.716:55-5.801:55从北京出发，乘T231特快列车（硬座）至I 达洛阳106元5.608:00-5.611:00在洛阳市龙门石窟游玩3个小时120元+60元5.612:47-5.618:43从洛阳出发，乘1086列普快（硬座）返回 徐州34元总计：1839元表3问题3的具体行程2 .问题（4）存在时间约束条件下的最优解本题与问题（3）类似，仍然是先根据贪婪法求得子集中元素个数的近似解，依据加权 后每个景点的优先级筛选优先级高的景点。用蚁群算法实现最优解。其结果如下：图4MATLA运行结果时间事件费用5.

35、109:35-5.110:45从徐州出发，乘KN2904航班到达北京550元5.112:00-5.115:00在八达岭长城游玩3个小时45元+60元（吃饭等其他 费用）5.119:20-5.121:05从北京出发，乘MU569利达洛阳机场787元5.122:00-5.208:00入住于洛阳东宣假日酒店198元5.208:00-5.211:00在洛阳市龙门石窟游玩3个小时120元+60元5.214:53-5.220:13从洛阳出发，乘K128/125快车（硬座）到 达西安55元5.221:00-5.308:00入住于西安华清彖泰商务会所130元5.308:00-5.310:00在西安巾秦始皇兵马

36、俑处游玩2个小时90元+60元5.311:50-5.312:55从西安咸阳机场，乘 MF8218亢班到达武汉 天河机场608元5.314:00-5.316:00在武汉市黄鹤楼游玩2个小时90元+60元5.322:20-5.323:40从武汉天河机场出发，乘 MU2364亢班到达 太原武宿机场540元5.405:00-5.406:08从太原出发，乘2462/2463普快（硬座）到 达祁县7元5.408:00-5.411:00在祁县乔家大院游玩3个小时40元+60元5.412:29-5.413:47从祁县出发，乘1096普快（硬座）到达太 原7元5.417:53-5.512:58从太原出发，乘K3

37、74/371快车（软卧）至I 达常州458元5.514:00-5.518:00在常州恐龙园游玩3个小时160元+60元5.600:09-5.605:48从常州出发，乘K76/77快车（硬座）返回 徐州70元表4问题4的具体行程3 .3求解多目标TSP问题为综合衡量费用TSP与时间TSP问题，建立以下模型评价：（1）确定多目标TSP问题的优化模型，本题中只考虑费用与时间两个因素的优化；（2）给定各个目标因素的优先级。本题中，以费用为第一优先级，时间为第二优先级（3）对给定的指标进行无量纲化处理，使得各个指标具有可比性。由费用和时间两个描述矩阵，给定无量纲处理为：D' =D/dmin其中，

38、D'为处理过后的无量纲矩阵，dmin为描述矩阵中的最小元素。（4）对费用与时间两个矩阵，取相同位置坐标的无量纲量进行整合形成一个新的无量 纲量，定为求解矩阵。（5）用最小元素法确定在满足费用以及时间同时约束时，有向图包涵的原图的子集的元素个数。给定各个景点的优先级，用试探法选取可能为最优的路径。其中每个 景点的权值为：X=%ci3.3.2问题（5）多目标TSP问题模型求解处理数据后用MATLA皿行模拟，所得相对最优解如下：图5MATLAB!行结果具体行程如下：时间事件费用5.109:35-5.110:45从徐州出发，乘坐中国联合航空公司 KN2904亢班至IJ达 北京550元5.110

39、:45-5.113:46在北京八达岭长城游玩3个小时45元+60元5.122:48-5.207:38从北京出发，乘坐T25T-特快（硬座）到达青岛116元5.208:00-5.214:00在青岛市崂山游玩6个小时100 元+60元5.215:16-5.305:28从青岛出发，乘坐1112/1113普快（硬坐）到达中转 站郑州123元5.306:02-5.312:42从中转站关B州出发，乘坐K1363K-快速（硬坐）到达西 安73元5.312:24-5.314:24在西安巾秦始皇兵马俑游玩2个小时90元+60元5.318:20-5.403:32从西安出发，乘坐T42T-特快（硬座）到达太原站10

40、3元5.405:00-5.406:08从太原出发，乘2462/2463普快（硬座）到达祁县7元5.408:00-5.411:00在祁县乔家大院游玩3小时40+60元5.412:29-5.413:47从祁县出发，乘坐1096普快返回太原7元5.418:01-5.509:44从太原出发，乘K520/K521K-特快（硬坐）到达武汉150元5.509:44-5.511:44在武汉市黄鹤楼游玩2个小时80元+60元5.518:40-5.604:23从武汉出发，乘2614/2615普快（硬坐）返回徐州39元总计：1823元表5问题5的具体行程 四模型的评价4.1 模型的优点(1)算法表示借助了 MATL

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

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

43、目标旅行售货员问题的蚂蚁算法求解系统程理论方法应用，1999； 8(4) ： 23 2713 杨忠 , 鲍明 , 张阿舟 . 求解中国旅行商问题的新结果J. 数据采集与处理 ,1993,8(3):177-184.14 唐建清，邹国霞. 基于 Floyd 算法的旅游路径智能选择系统. 上海：华东师范大学15 许峰，杜军平. 改进蚁群算法在旅游线路规划中的应用研究. 北京：北京邮电大学16 杨志江，李国欣，张敏. 管道订购与运输问题. 徐州：中国矿业大学附录1. 基本蚁群算法的MATLA殴现2. m=11;3. alpha=1;4. beta=5;5. rho=0.7;6. nc_max=200;

44、7. q=100;8. c=load( 'd:zb.txt');9. d=load( 'd:jl.txt');10. n=11;11. eta=1./d;12. tau=ones(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. while nc<=nc_max19. %putants20. randpos=;21. for i=1:(ceil(m/n);22. r

45、andpos=randpos,randperm(n);23. end24. tabu(:,1)=(randpos(1,1:m);25. %completetraveling26. for j=2:n27. for i=1:m28. visited=tabu(i,1:(j-1);29. j=zeros(1,(n-j+1);30. P=J;31. jc=1;32. for k=1:n33. if length(find(visited=k)=034. j(jc)=k;35. jc=jc+1;36. end37. end38. for k=1:length(j)39. P(k)=(Tau(visit

46、ed(end),J(k)Alpha)*(Eta(visited(end),J(k)ABeta);40. end41. p=p/(sum(p);42. %selectthenextcity43. pcum=cumsum(p);44. select=find(pcum>=rand);45. to_visit=j(select(1);46. tabu(i,j)=to_visit;47. end48. end49. if nc>=250. tabu(1,:)=r_best(nc-1,:);51. end52. %recordthebestroute53. l=zeros(m,1);54.

47、for i=1:m55. r=tabu(1,:);56. for j=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. for i=1:m;69. for j=1:(n-1);70. Del

48、ta_Tau(Tabu(i,j),Tabu(i,j+1)=Delta_Tau(Tabu(i,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. Shore

49、st_Length=L_best(Pos(1)81. subplot(1,2,1)82. N=length(R);83. scatter(C(:,1),C(:,2);84. hold on85. plot(C(R(1),1),C(R(N),1),C(R(1),2),C(R(N),2)86. for ii=2:N87. plot(C(R(ii-1),1),C(R(ii),1),C(R(ii-1),2),C(R(ii),2)88. hold on89. end90. subplot(1,2,2)91. plot(L_best)92. hold on93. plot(L_ave)2 .各个景点的高斯

50、坐标（3分度）江苏徐州3793326.773常州中华恐龙园3519739.016青岛市崂山3985613.305北京八达岭长城4474604.565山西祁县乔家大院4138111.493洛阳市石门石窟3842336.821黄山市黄山3342855.143武汉市黄鹤楼3377492.083西安市秦始皇兵马 俑3793717.098九江市庐山3289211.33舟山市普陀山3320681.8823 .各城市之间的距离江常州青 岛北京山西祁洛阳黄 山武汉西安市九江舟山距离苏中华八达市后巾更秦始皇市叱徐市岭长县乔家市恐龙崂大院门后黄鹤楼兵马俑庐陀山州园山城窟山山江苏徐 州0454473779775528640687810631840常州中 华恐龙 园4540714120911988644527381212595396青岛市 崂山473714072494793395611461231104 01029北京八 达岭长 城7791209724060188814211328113814711599山西祁 县乔家 大