蚁群算法解决旅游线路问题.doc

1、2011年第八届苏北数学建模联赛承 诺 书我们仔细阅读了第八届苏北数学建模联赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。我们的参赛报名号为： 参赛组别（研究生或本科或专科）：本科组参赛队员 (签名) ：队

2、员1：唐文辉队员2：徐玲队员3：涂杰 获奖证书邮寄地址： 摘要本文就旅游线路的优化设计问题，根据旅游者在旅行中的旅游时间，旅游费用，旅游地点，交通状况，住宿等因素的约束，借助图论，蚁群算法，建立最优化数学模型。在最短路路线的基础上，综合考虑交通，用费，时间对问题（2）、（3）、（4）、（5）的影响，给出旅游路线，并用lingo程序对结论进行检验，确保结论的全局最优性。针对问题（1），首先，由城市经纬度建立城市和城市之间距离的有向图图论模型，在建立图论模型的基础上，建立在城市之间距离矩阵，采用蚁群算法，得到一条最短闭合路线。根据最短路线，查找合适时间的车次，距车站或景点一定范围内的最便宜的宾馆，

3、达到费用最小。结合实际，得出最优路线：徐州-常州-舟山-黄山-庐山-武汉-洛阳-西安-祁县-北京-青岛-徐州，得到行程表和旅游最小费用3551元。针对问题（2），采用衔接最得当，城市间交通时间和最少的交通方式，由此找出交通方式的时间最优化配置，进而得到最优路线：徐州-舟山-黄山-武汉-九江-常州-洛阳-西安-祁县-青岛-北京-徐州，并得到行程表和最短旅游时间9天。针对问题（3）在问题（1）的基础上，对每个旅游景区最短停留时间，门票费用加权赋值建立权向量。运用层次分析法，分别求出权重。根据权重，分别求出每个景点综合花销。在2000元旅费的限制下，在最短路线上删除耗时长，费用高的城市。重新查找删去

4、城市后城市间的交通费，得到旅游行程表和最多旅游景点7个，旅行线路：徐州-青岛-北京-祁县-西安-洛阳-武汉-九江。针对问题（4），在基于问题（2）的结果下，首先，将问题（2）中停留时间（离开时刻与到达时刻之差）较长的城市从路线中删除，直到满足小于5天为止。重新查找删去城市后城市间的交通时间，对路线进行微调后，得到旅游行程表和最多旅游景点7个，分别是：徐州-北京-青岛-祁县-西安-洛阳-武汉-常州-徐州。针对问题（5），对问题（3）和问题（4）综合考虑，找出其中时间相对长，旅游费用相对大的城市，进行排名并逐个剔除，并做适当调整。当满足条件时，得出行程表和费时5天、总费用1798元的结论，具体路线

5、：徐州-北京-青岛-祁县-西安-洛阳-常州-徐州。最后，对模型的优缺点进行了分析，提出改进方案。关键字：TSP问题 蚁群 lingo 最优1 问题重述江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。他预选了十个省市旅游景点，如表1所示。省市景点名称在景点的最短停留时间江苏常州市恐龙园4小时山东青岛市崂山6小时北京八达岭长城3小时山西祁县乔家大院3小时河南洛阳市龙门石窟3小时安徽黄山市黄山7小时湖北武汉市黄鹤楼2小时陕西西安市秦始皇兵马俑2小时江西九江市庐山7小时浙江舟山市普陀山6小时问题：根据以上要求，针对如下的几种情况，为该旅游爱好者设

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

7、览景点，请建立相关数学模型并设计旅游行程表。2 问题分析2.1 问题(1)游客旅游费用包括交通费、住宿费、景点门票、饮食其他费用三个方面。首先，每个景点的门票费用与路线选取无关。通过考虑路程最短，可以让城市之间的交通费用达到最小，同时可以缩小旅游时间，由此减少住宿费用。旅游路线的费用与旅游路线的长度正相关，因此选取最短的旅游路线和离每个景点最近的火车站，可以令交通费用最少。其次，在距离景点一定范围内，选取最便宜的旅馆入住，尽量减少住宿费。且规定，游客在晚上12点之前不能坐上离开城市的交通工具，则住宿，在旅客不能在早上6点之后到达下一个城市，则在该城市住宿。因此，运用蚁群算法，将旅游路线规划为最

8、短；查找离景区一定距离范围内最便宜的旅馆入住，达到旅游费用最少。2.2 问题(2)影响旅游时间的因素主要是城市之间的交通时间和在城市内停留的时间。要想实现城市交通时间最短，可以在最短旅游距离，最快交通工具，可以在对端旅游路线下，尽可能通过选择时间匹配的快捷交通方式飞机、高铁，来节约旅行时间。2.3 问题(3)想要限制费用在2000元下，进可能多的游览多的景点，首先要去考虑删去停留时间长，门票费用高的城市。因为停留时间长，必定会增加食宿等费用。然而，时间和旅费不能统一进行比较，因此，针对每一个旅游景区，以旅游费用为目标，时间和门票费用为决策层，利用层次分析法，得到每个景区的综合费用，由此排除花销

9、相对大的城市。对于总体而言，旅游时间影响食宿等费用，旅行的路线越长，则旅游天数就越多，随之，食宿费用就越多。并且城市之间的交通费用也会增加。因此，仍然采用问题（1）中得最短路线，在最短路的基础上，删去排除在外的城市。重新查找路线上相邻城市已经改变的城市间的车费，对旅游路线作最后微调。2.4 问题(4)旅游路线、交通方式影响旅游时间的两个重要因素。因此，该问题可以基于问题（2）在最短路线下最优的交通乘坐方式下再根据时间限定寻找最多旅游城市。首先，将问题（2）中停留时间（离开时刻-到达时刻）较长的城市从路线中删除，知道基本满足时间5天为止。最后重新查找删去城市后城市间的交通时间，对路线进行微调。2

10、.5 问题(5)该题同时考虑到时间以及费用的限制。可以基于问题（3）和问题（4），对问题进行综合考虑。因既要时间在5天内，又要旅游费用2000元以内的条件条设计旅游行程，不妨找出其中时间相对长，旅游费用相对大的城市，进行排名并逐个剔除，并做适当调整。知道满足条件为止。3 模型假设和符号说明3.1模型的假设1. 城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。2. 市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。3. 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超

11、过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。4. 假设景点的开放时间为8:00至18:00。5. 假设除去乘坐汽车，公交，旅游的时间，旅游者在每个城市寻找站点以及吃饭等其他因素引起的逗留时间算与停留时间内。3.2 符号说明；是的Euclidean距离；表示t时刻位于元素i的蚂蚁数目；为t时刻路径(i, j)上的信息量；表示TSP规模，即城市数；为蚁群中蚂蚁总数；，(k=1,2,m)表示第k蚂蚁只蚂蚁；表示记录蚂蚁k的11阶1方正矩阵的禁忌表；表示信息素强度；表示第k只蚂蚁在本次循环中所走路径的总长度；4 建模前准备4.1蚁群算法模型蚁群算法是模拟蚁群在不知道食物在

12、什么地方下需找食物的过程。当有每只蚂蚁找到食物时会释放信息素吸引更多蚂蚁。当一些另辟蹊径的蚂蚁找到更短的路会逐渐吸引更多蚂蚁过来，如此往复，找到最短路。在蚁群需找食物的过程中，每只蚂蚁在只关心的范围内遍历空间上的点，要以适当的地形躲避障碍，计算所有可能路径并比较它们。因此，蚁群算法包括： 范围，蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。 环境，蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的

13、信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。 觅食规则，在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁都会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。 移动规则，每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如

14、果发现要走的下一点已经在最近走过了，它就会尽量避开。避障规则，如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。播撒信息素规则，每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。4.2 数据的预处理 实现

15、运用谷歌地图将11各城市的经纬度坐标并对11个城市见费用最小、耗费时间最短的交通方式和消耗进行查阅对城市间无交通的进行预处理。5 模型建立与求解5.1.1 模型的建立1) 对城市建立图论模型设：是的Euclidean距离，即G=(C, L)是一个有向图，TSP的目的是从有向图G中寻出长度最短的Hamilton圈，即一条对C=c1, c2, , cn中个元素（城市）访问且只访问一次的最短封闭曲线，存在(n-1)!/2条不同闭合路径2) 蚁群模型设表示t时刻位于元素i的蚂蚁数目，为t时刻路径(i, j)上的信息量，n表示TSP规模，m为蚁群中蚂蚁总数则是t时刻集合C中元素（城市）两两连接上残留信息

16、量的集合，在初始时刻各条路径上的信息量相等，并设 =const, 基本蚁群算法通过有向图g=(C, L, )寻找优化路线。蚂蚁k(k=1,2,m)在运动过程中，根据各条路径上的信息量决定其转移方向。这里用禁忌表tabuk来记录蚂蚁k当前所走过的城市，集合随着tabuk进化过程做动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。在t时刻蚂蚁k由元素（城市）i转移到元素（城市）j的状态转移概率： （1）其中allowedk=C-tabuk表示蚂蚁k下一步允许选择的城市；为信息启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中积累的信息在蚂蚁运动时所起的作用

17、，其值越大，则该蚂蚁越倾向于选择其它蚂蚁经过的路径，蚂蚁之间的协作性越强；为期望启发式因子，表示能见度的相对重要性，反映蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越大，则该状态转移概率越接近于贪心规则:为启发函数; 对蚂蚁k而言,越小，则越大，也就越大。显然，该启发函数表示蚂蚁从元素（城市）i转移到元素（城市）j的期望程度。为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步或者完成对所有n个城市的遍历(也即一个循环结束)后，要对残留信息进行更新处理。这种更新策略模仿了人类大脑记忆的特点，在新信息不断存人大脑的同时，存储在大脑中的旧信息随着时间的推移逐渐淡化，甚至

18、忘记。由此，t+n时刻在路径(i, j)上的信息量可按如下规则进行调整 (2) (3)上式中，表示信息素挥发系数，则1-表示信息素残留因子，为了防止信息的无限积累，的取值范围为0，1),ij(t)表示本次循环中路径(i, j)上的信息素增量，初始时刻表示第k只蚂蚁在本次循环中留在路径(i, j)上的信息量。 （4）Q表示信息素强度，它在一定程度上影响算法的收敛速度；Lk表示第k只蚂蚁在本次循环中所走路径的总长度。3) TSP的蚁群算法步骤输出程序计算结果按式（2）和式（3）进行信息量更新修改禁忌表按式（1）选择下一元素蚂蚁k=1循环次数Nc Nc+1初始化开始结束Km满足结束条件蚂蚁k=k+1

19、NYYN上图步骤阐述：(1)参数初始化。令时间t=0和循环次数Nc=0，设置最大循环次数Ncmax, 将m个蚂蚁置于n个元素(城市)上，令有向图上每条边(i, j)的初始化信息量ij(t)=const, 其中const表示常数，且初始时刻(0)=0(2)循环次数Nc Nc+1。(3)蚂蚁的禁忌表索引号k=1。(4)蚂蚁数目 kk+1。(5)蚂蚁个体根据状态转移概率公式(1)计算的概率选择元素(城市) j 并前进，jC - tabuk。(6)修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素(城市)，并把该元素(城市)移动到该蚂蚁个体的禁忌表中。(7)若集合C中元素(城市)未遍历完，即km，则跳转

20、到第(4)步，否则执行第(8)步。(8)根据公式(2)和式(3)更新每条路径上的信息量。(9)若满足结束条件，即如果循环次数Nc Ncmax 则循环结束并输出程序计算结果，否则清空禁忌表并跳转到第(2)步。4）对约束条件下旅游城市的选择针对每个景点，按对目标旅游费用的影响程度，分别对对停留时间和景点门票分别赋予权值1和3。建立层次结构模型：旅游费用停留时间门票费用目标层准则层根据权，构造矩阵B：用matlab计算得到矩阵最大特征根l=2；n=2权向量(特征向量)w =（0.3162，0.9487)；一致性指标CI=(l-n)/(n-1) CI=(2-2)/4=0；随机一致性指标 ：RI=1.1

21、2 (查表)；一致性比率CR=0/1.12=00.1,通过一致性检验。设停留时间向量T，赋权后的值为Y；门票费用为向量P，赋权后的值为P,则：T=0.3161*T； P=0.9487*P将权重向量相加T+P=（0，115.1088，77.7932，43.6401，38.8966，114.7926，220.4144，76.5284，86.0154，172.9794，191.6372）。根据用费2000元的限制，删除向量中值较大的分量所对应的城市：浙江，江西，安徽。重新查找删去城市后城市间的交通费，稍做调节，得到行程表。5.2.问题的结论问题（1）的结论根据所建立的模型，在matlab中设计程序并

22、运行，得到出游闭合的局部最优路线，并经过lingo检验确保结论全局最优性。得到路线图:根据路线图，查取各城市的铁路，汽车信息等交通信息，再根据路线图、在景点停留时间和住宿等信息选择车次，最后给出如下行程安排表：日期时间交通信息及行程安排住行费（元）景点门票5.18:20-10:49乘坐D5431次火车（徐州常州）14211:00-18：00乘公交去中华恐龙园，游玩中华恐龙园81205.4-5.221：01-10：02乘坐k75/k78次火车（常州-宁波东）13010:02-12：00乘长途客运（宁波-普陀）去普陀山302005.2-5.320:00-6:00在普陀山附近住舟山昌源大酒店1685

23、.3-5.46:10-15:00乘坐长途客运车（定海-沈家门-杭州客运中心-黄山景区） 18023022:07-5:45乘坐k434/k431（黄山-南昌）705.47：00-8：01乘坐D6342次列车（南昌-九江）428:10-20：00在九江乘公交车去庐山41805.4-5.520:10-6：30在庐山附近住庐山夏都宾馆1805.57：00-10：30在九江乘坐长途客运车（九江-武汉）7210：30-14：30在武汉乘公交车去黄鹤楼48015：30-23：44乘坐k864/k861c次列车（武汉-洛阳）875.5-5.623：50-8：00在洛阳火车站住洛阳凌守快捷酒店1008：00-1

24、5：00在洛阳乘坐公交车到龙门石窟41205.617:15-22:47乘坐k134/k131次列车(洛阳-西安)335.6-5.722:50-8:00在西安火车站附近住西安陕西出版宾馆1588:00-19:00在西安火车站乘坐公交车到秦始皇兵马俑8905.7-5.820:46-6:19乘坐2670次（西安-祁县）397:00-18:00在祁县乘坐公交车到东观即可到乔家大院4405.8-5.922:05-10:23乘坐1164次（祁县-北京）火车8110：40-20：00在火车站乘坐公交车到八达岭成城游玩4455.9-5.1022:22-10:08乘坐k712/k709(北京西-青岛)11310

25、:10-18:00乘车到崂山游玩4805.10-1119:28-04:52乘坐k60/k67次火车（青岛-徐州）回到徐州99共10天总计：（元）17461185最小费用统计如下：项目项目费用合计交通费用1766景点门票1185吃饭费用600费用总计（元）3551问题(2) 的结论在各城市间交通时间为价值矩阵的程序得出时间最优路线的结论下，通过查找个城市航班、高铁时间信息，得到以下行程安排表：旅游行程表：日期时间信息5.1-5.210：10-11：31乘坐航班（徐州-舟山） FM924212：00-18：00游览普陀山19：00-8：00在普陀山附近住宿舟山昌源大酒店5.28：55-10：45乘

26、坐航班（舟山-黄山）MU942411：00-18：00游览黄山22：00-24：00乘坐航班（黄山-武汉） PN63015.39:00-11:00游览黄鹤楼15：20-20：17乘坐列车（武汉-九江） K7525.4-5.58:00-15:00游览庐山15：30-18：00乘坐列车（九江-常州） G36719:00-8:00在常州附近住宿常州世纪大公馆5.58：00-13：00常州市恐龙园14：00-20：00乘坐航班（常州-洛阳） CA45905.6-5.78：00-12：00游览龙门石窟14：31-16：15乘坐航班（洛阳-西安 ）CZ336417:00-8:00在西安机场附近住宿西安申鹏

27、酒店5.78：00-10：00游览兵马俑1：50-12：00乘坐列车（西安-太原 ）267012：00-13：00乘坐的士（太原-祁县） 13：30-16：30游览乔家大院16：30-17：00乘坐的士（祁县-太原） 18：15-19：35乘坐航班（太原-北京） HU73715.88：00-11：00游览八达岭长城16：45-18：00乘坐航班（北京-青海） CA15175.98：00-14：00游览崂山16：35-20：37乘坐列车（青岛-徐州） G236由表可知，游览完10个景区旅行时间为最少为9天。问题(3) 的结论 在问题（1）的结论下，剔除部分花费较多的旅游城市后经过matlab得出

28、路线吐下：路线图：在查阅相关交通信息后得到行程表：日期（月.日）时间交通信息及行程安排住行费用（元）门票（元）每日花销（元）5.1-5.222:36-06:53乘坐k68/k69次列车（徐州-青岛）99607:00-15:00乘坐公交车到崂山旅游48017:25-22:36乘坐D60次列车（青岛-北京南站）2505.2-5.322:40-7:00在北京南站住北京轻联富润饭店60607:00-20:00乘公交车到八达岭长城游玩8455.3-5.423:42-13:41乘坐2602次列车（北京-祁县）946014:00-18:00乘公交车到乔家大院游玩4405.4-5.520:29-7:05乘坐1

29、095次列车（祁县-西安）41607:10-12:00乘坐公交车到秦始皇兵马俑游玩49012:45-14:45乘坐D1012次列车（西安北-洛阳龙门）12014:50-18:00乘坐公交车到龙门石窟游玩41205.5-5.622:20-7:11乘坐k792/k789次列车（洛阳-武汉）87607:30-14:00乘坐公交车到黄鹤楼游玩4805.6-5.715:16-20:17乘坐k752/k753次列车（武汉-九江）516020:30-7;00在九江附近九江玉渊宾馆608:00-16:00乘公交车去庐山游玩41805.7-5.817:02-5:23乘坐k612/k613次列车（九江-徐州）回家

30、86即在2000元内，最多可以游览7个景点。问题(4) 的结论在问题（2）在结论下经过适当处理肯程序验证得到以下路线：行程表：日期时间行程5.19：:4-12.40乘坐火车（徐州-北京） G10413.00-16.00游玩长城22.20-3.40乘坐航班（北京-青岛） SC46005.28.00-14.0游玩崂山15.25-17.05乘坐航班（青岛-太原） SC460719.14-20.27乘坐列车（太原-祁县） 109520.30-8.00这住宿祁县5.38.00-11.00游玩乔家大院20.29-7.05乘坐列车（祁县-西安） 10957.10-8.00住宿西安5.48.00-10.00游

31、玩秦始皇兵马俑12.05-13.36乘坐列车（西安-洛阳 ）G20615.00-18.00游玩龙门石窟22.00-7.11乘坐列车（洛阳-武汉） K7925.58.00-11.00游览黄鹤楼17.39-21.5乘坐（武汉-常州） D307014.00-18.00游玩常州恐龙园20.42-23.01乘坐列车（常州-徐州） D5432问题(5) 的结论利用问题3）及问题4）的结论，考虑到时间以费用的限制，首先将费用较多的城市：北京，九江，黄山，舟山去除后，得出结论为：五天可旅游完其余城市且费用为1368与费用上限2000差距较远，故考虑增加一个城市。因为第一天出发时间为晚上故增加北京，经过计算后，

32、总费用1798元且在第五天夜间回到徐州，满足题意，得到旅行路线和行程表。路线图：行程表：日期（月.日时间交通信息及行程安排交通费用及住宿费用（元）门票（元）每日花销（元）5.18.58-13.55乘坐列车（徐州-北京） D2162156015.00-18.00乘公交到长城游玩4455.1-5.222.22-10.08乘坐k712（徐州-青岛）1136011:00-17:00乘坐公交车到崂山旅游4805.2-5.319.38-7:03乘坐列车（青岛-太原） K882120607.40-8.47乘坐列车（太原-祁县） K868 159.00-12.00乘公交车到乔家大院游玩4405.3-5.420

33、:29-7:05乘坐1095次列车（祁县-西安）43607:10-12:00乘坐公交车到秦始皇兵马俑游玩49012:45-14:45乘坐D1012次列车（西安北-洛阳龙门）12014:50-18:00乘坐公交车到龙门石窟游玩41205.4-5.521.20-10.17乘坐列车（洛阳-常州） K7361296011.30-15.30乘公交车到中华恐龙园游玩412016.28-18.16乘坐列车（常州-徐州） G44回家2146 模型的评价及改进6.1 问题的优缺点在解决问题（1）中认为城市间交通费用与距离成正比或将城市间交通时间、费用作为权向量，运用蚁群算法得出局部最优值，后经lingo遍历所有

34、可行点后得到全局最优解与蚁群算法所得最优解相一致，验证了结论的正确性。 在解决解决问题（3）（4）（5）时运用问题（1）（2）已有结论，在特定约束下，将部分耗费（时间、费用）较多的城市事先剔除结合实际交通状况做出检验后迭代最终得出最优结论。在解决约束性条件较多的问题时，将对结论影响较大的城市预先剔除时具有较强的主观性。并且在交通工具的选择时难免会有失误，得到的交通路线可能不是最优。参考文献1党林立,孙晓群.数学建模简明教程.西安电子科技大学.20092姜启源.数学模型（第三版）,高等教育出版社.20033唐焕文,贺明峰.数学模型引论.高等教育出版社.20034谢金星,薛毅.优化建模与LINDO

35、/LINGO软件.清华大学出版社，北京20065李志林,欧宜贵.数学建模及典型案例分析.化学工业出版社,北京20066吴孟达,成礼智.数学建模的理论与实践.国防科技大学出版社.20027徐全智,杨晋浩.数学建模入门.电子科技大学出版社.2003【1】附录：1. matlab中城市经纬度文件 city.m1 117.11 4.15 2 117.11 31.47 3 120.18 36.03 4 116.24 39.55 5 112.51 35.30 6 112.27 34.41 7 118.18 29.43 8 114.17 30.35 9 108.57 34.17 10 115.58 29.4

36、3 11 122.06 30.012. 蚁群算法matlab程序%function = Shortest( )%UNTITLED2 Summary of this function goes here%Detailed explanation goes heretic;%preparation of ant agorithm:path=0; %A=load(city.m); %CityNumber=size(A,1); %money=0 70 70 106 107.5 51 76 95 95 50 13070 0 455 140 240 125 73 223 165 87 7370 455 0

37、 113 218 150 182 172 191 175 214106 140 113 0 94 106 182 281 150 165 322107.5 240 218 94 0 52 271 140 41 151 26651 125 150 106 52 0 80 87 49 72 20976 73 182 182 271 80 0 71 170 43 7695 223 172 281 140 87 71 0 137 41 24695 165 191 150 41 49 170 137 0 96 19450 87 175 165 151 72 43 41 96 0 94130 73 214

38、 322 160 209 76 246 194 94 0; time=0 322 320 70 660 280 602 562 521 528 724 322 0 944 85 1140 735 583 250 110 840 272 320 944 0 75 100 914 1395 115 110 1015 90 70 85 75 0 75 105 120 110 105 135 130 660 1140 100 75 0 701 994 80 65 731 960 280 735 914 105 701 0 1750 423 270 696 1320 602 583 1395 120 9

39、94 1750 0 467 1300 484 490 562 250 115 110 80 423 467 0 70 215 75 521 110 110 105 65 270 1300 70 0 967 170 528 840 1015 135 731 696 484 215 967 0 828 724 272 90 130 960 1320 490 75 170 828 0;%Step 1:%for i=1:CityNumber for j=i:CityNumber %solve two points distance distance(i,j)=(A(i,3)-A(j,3)2+(A(i,

40、2)-A(j,3)2)(1/2); if i=j % eita(i,j)=0; else eita(i,j)=1/distance(i,j); %eita(i,j)=1/money(i,j); %eita(i,j)=1/time(i,j); end endenddistance=distance+distance; %eita=eita+eita; % %Step 1_01:%r=1; %Information heuristic factorbeta=2; %Heuristic factor expectedbestpath=1000000000;%rou=0.7;tao=ones(City

41、Number); %initlitalize every paths informationdeta_tao=zeros(CityNumber); %Step 2:%NumMax=1; %The problems to be the number of iterationsAntNumber=50;for i=1:NumMax %Step 2_01: % Info=ones(CityNumber); % for j=1:CityNumber for k=1:CityNumber % Info(j,k)=(tao(j,k)r)*(eita(j,k)beta); %Information between any two cities end end AntPath=ones(AntNumber,CityNumber); % for ant=1:AntNumber % % StartCity=round(1+rand*(CityNumber-1); % City=StartCity; PathLength=0; tabu=ones(CityNumber); %Initialize each element of taboo list p=zeros(CityNumber); % %Step 2_02: % tabu(:,City)=0; % Count=1; % Ant