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

12011年第八届苏北数学建模联赛承诺书我们仔细阅读了第八届苏北数学建模联赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。我们的参赛报名号为：参赛组别（研究生或本科或专科）：本科组参赛队员(签名)：队员1：唐文辉队员2：徐玲队员3：涂杰获奖证书邮寄地址：2摘要本文就旅游线路的优化设计问题，根据旅游者在旅行中的旅游时间，旅游费用，旅游地点，交通状况，住宿等因素的约束，借助图论，蚁群算法，建立最优化数学模型。在最短路路线的基础上，综合考虑交通，用费，时间对问题（2）、（3）、（4）、（5）的影响，给出旅游路线，并用lingo程序对结论进行检验，确保结论的全局最优性。针对问题（1），首先，由城市经纬度建立城市和城市之间距离的有向图图论模型，在建立图论模型的基础上，建立在城市之间距离矩阵，采用蚁群算法，得到一条最短闭合路线。根据最短路线，查找合适时间的车次，距车站或景点一定范围内的最便宜的宾馆，达到费用最小。结合实际，得出最优路线：徐州-常州-舟山-黄山-庐山-武汉-洛阳-西安-祁县-北京-青岛-徐州，得到行程表和旅游最小费用3551元。针对问题（2），采用衔接最得当，城市间交通时间和最少的交通方式，由此找出交通方式的时间最优化配置，进而得到最优路线：徐州-舟山-黄山-武汉-九江-常州-洛阳-西安-祁县-青岛-北京-徐州，并得到行程表和最短旅游时间9天。针对问题（3）在问题（1）的基础上，对每个旅游景区最短停留时间，门票费用加权赋值建立权向量。运用层次分析法，分别求出权重。根据权重，分别求出每个景点综合花销。在2000元旅费的限制下，在最短路线上删除耗时长，费用高的城市。重新查找删去城市后城市间的交通费，得到旅游行程表和最多旅游景点7个，旅行线路：徐州-青岛-北京-祁县-西安-洛阳-武汉-九江。针对问题（4），在基于问题（2）的结果下，首先，将问题（2）中停留时间（离开时刻与到达时刻之差）较长的城市从路线中删除，直到满足小于5天为止。重新查找删去城市后城市间的交通时间，对路线进行微调后，得到旅游行程表和最多旅游景点7个，分别是：徐州-北京-青岛-祁县-西安-洛阳-武汉-常州-徐州。针对问题（5），对问题（3）和问题（4）综合考虑，找出其中时间相对长，旅游费用相对大的城市，进行排名并逐个剔除，并做适当调整。当满足条件时，得出行程表和费时5天、总费用1798元的结论，具体路线：徐州-北京-青岛-祁县-西安-洛阳-常州-徐州。最后，对模型的优缺点进行了分析，提出改进方案。关键字：TSP问题蚁群lingo最优1问题重述江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。他预选了十个省市旅游景点，如表1所示。省市景点名称在景点的最短停留时间江苏常州市恐龙园4小时3山东青岛市崂山6小时北京八达岭长城3小时山西祁县乔家大院3小时河南洛阳市龙门石窟3小时安徽黄山市黄山7小时湖北武汉市黄鹤楼2小时陕西西安市秦始皇兵马俑2小时江西九江市庐山7小时浙江舟山市普陀山6小时问题：根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。(1)如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。(2)如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。(3)如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(4)如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(5)如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。2问题分析2.1问题(1)游客旅游费用包括交通费、住宿费、景点门票、饮食其他费用三个方面。首先，每个景点的门票费用与路线选取无关。通过考虑路程最短，可以让城市之间的交通费用达到最小，同时可以缩小旅游时间，由此减少住宿费用。旅游路线的费用与旅游路线的长度正相关，因此选取最短的旅游路线和离每个景点最近的火车站，可以令交通费用最少。其次，在距离景点一定范围内，选取最便宜的旅馆入住，尽量减少住宿费。且规定，游客在晚上12点之前不能坐上离开城市的交通工具，则住宿，在旅客不能在早上6点之后到达下一个城市，则在该城市住宿。因此，运用蚁群算法，将旅游路线规划为最短；查找离景区一定距离范围内最便宜的旅馆入住，达到旅游费用最少。42.2问题(2)影响旅游时间的因素主要是城市之间的交通时间和在城市内停留的时间。要想实现城市交通时间最短，可以在最短旅游距离，最快交通工具，可以在对端旅游路线下，尽可能通过选择时间匹配的快捷交通方式—飞机、高铁，来节约旅行时间。2.3问题(3)想要限制费用在2000元下，进可能多的游览多的景点，首先要去考虑删去停留时间长，门票费用高的城市。因为停留时间长，必定会增加食宿等费用。然而，时间和旅费不能统一进行比较，因此，针对每一个旅游景区，以旅游费用为目标，时间和门票费用为决策层，利用层次分析法，得到每个景区的综合费用，由此排除花销相对大的城市。对于总体而言，旅游时间影响食宿等费用，旅行的路线越长，则旅游天数就越多，随之，食宿费用就越多。并且城市之间的交通费用也会增加。因此，仍然采用问题（1）中得最短路线，在最短路的基础上，删去排除在外的城市。重新查找路线上相邻城市已经改变的城市间的车费，对旅游路线作最后微调。2.4问题(4)旅游路线、交通方式影响旅游时间的两个重要因素。因此，该问题可以基于问题（2）在最短路线下最优的交通乘坐方式下再根据时间限定寻找最多旅游城市。首先，将问题（2）中停留时间（离开时刻-到达时刻）较长的城市从路线中删除，知道基本满足时间5天为止。最后重新查找删去城市后城市间的交通时间，对路线进行微调。2.5问题(5)该题同时考虑到时间以及费用的限制。可以基于问题（3）和问题（4），对问题进行综合考虑。因既要时间在5天内，又要旅游费用2000元以内的条件条设计旅游行程，不妨找出其中时间相对长，旅游费用相对大的城市，进行排名并逐个剔除，并做适当调整。知道满足条件为止。3模型假设和符号说明3.1模型的假设1.城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），5并且车票或机票可预订到。2.市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。3.旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。4.假设景点的开放时间为8:00至18:00。5.假设除去乘坐汽车，公交，旅游的时间，旅游者在每个城市寻找站点以及吃饭等其他因素引起的逗留时间算与停留时间内。3.2符号说明表示城市编号),...,(1121cccC；两两连接与为城市；jiijijccljilL11,....2,1,},{；)11,...2,1,(,jidij是ijl的Euclidean距离；)(tbi表示t时刻位于元素i的蚂蚁数目；)(tij为t时刻路径(i,j)上的信息量；n表示TSP规模，即城市数；m为蚁群中蚂蚁总数；k，(k=1,2,…,m)表示第k蚂蚁只蚂蚁；tabuk表示记录蚂蚁k的11阶1方正矩阵的禁忌表；Q表示信息素强度；kL表示第k只蚂蚁在本次循环中所走路径的总长度；4建模前准备4.1蚁群算法模型蚁群算法是模拟蚁群在不知道食物在什么地方下需找食物的过程。当有每只蚂蚁找到食物时会释放信息素吸引更多蚂蚁。当一些另辟蹊径的蚂蚁找到更短的路会逐渐吸引更多蚂蚁过来，如此往复，找到最短路。在蚁群需找食物的过程中，每只蚂蚁在只关心的范围内遍历空间上的点，要6以适当的地形躲避障碍，计算所有可能路径并比较它们。因此，蚁群算法包括：范围，蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。环境，蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。觅食规则，在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁都会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。移动规则，每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。避障规则，如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。播撒信息素规则，每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。4.2数据的预处理实现运用谷歌地图将11各城市的经纬度坐标并对11个城市见费用最小、耗费时间最短的交通方式和消耗进行查阅对城市间无交通的进行预处理。5模型建立与求解5.1.1模型的建立1)对城市建立图论模型设：舟山），武汉，西安。九江，京，晋城，洛阳，黄山徐州，常州，青岛，北(),...,(1121cccC两两连接与为城市；jiijijccljilL11,....2,1,},{7)11,...2,1,(,jidij是ijl的Euclidean距离，即22)()(jijiijyyxxdG=(C,L)是一个有向图，TSP的目的是从有向图G中寻出长度最短的Hamilton圈，即一条对C={c1,c2,…,cn}中n个元素（城市）访问且只访问一次的最短封闭曲线，存在(n-1)!/2条不同闭合路径2)蚁群模型设)(tbi表示t时刻位于元素i的蚂蚁数目，)(tij为t时刻路径(i,j)上的信息量，n表示TSP规模，m为蚁群中蚂蚁总数则)(tij是t时刻集合C中元素（城市）两两连接ijl上残留信息量的集合，在初始时刻各条路径上的信息量相等，并设)0(ij=const,基本蚁群算法通过有向图g=(C,L,Γ)寻找优化路线。蚂蚁k(k=1,2,…,m)在运动过程中，根据各条路径上的信息量决定其转移方向。这里用禁忌表tabuk来记录蚂蚁k当前所走过的城市，集合随着tabuk进化过程做动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。在t时刻蚂蚁k由元素（城市）i转移到元素（城市）j的状态转移概率：