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

《蚁群算法解决旅游线路问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、用蚁群算法，得到一条最短闭合路线。根据最短路线，查找合适时间的车次，距车站或景点一定围的最便宜的宾馆，达到费用最小。结合实际，得出最优路线：->->->->庐山->->->->祁县->->->，得到行程表和旅游最小费用3551元。针对问题（2），采用衔接最得当，城市间交通时间和最少的交通方式，由此找出交通方式的时间最优化配置，进而得到最优路线：->->->->->->->->祁县->->->，并得到行程表和最短旅游时间9天。针对问题（3）在问题（1）的基础上，对每个旅游景区最短停留时间，门票费用加权赋值建立权向量。运用层次分析

4、法，分别求出权重。根据权重，分别求出每个景点综合花销。在2000元旅费的限制下，在最短路线上删除耗时长，费用高的城市。重新查找删去城市后城市间的交通费，得到旅游行程表和最多旅游景点7个，旅行线路：->->->祁县->->->->。针对问题（4），在基于问题（2）的结果下，首先，将问题（2）中停留时间（离开时刻与到达时刻之差）较长的城市从路线中删除，直到满足小于5天为止。重新查找删去城市后城市间的交通时间，对路线进行微调后，得到旅游行程表和最多旅游景点7个，分别是：->->->祁县->->->->->。针对问题（5），对问题（3

5、）和问题（4）综合考虑，找出其中时间相对长，旅游费用相对大的城市，进行排名并逐个剔除，并做适当调整。当满足条件时，得出行程表和费时5天、总费用1798元的结论，具体路线：->->->祁县->->->->。最后，对模型的优缺点进行了分析，提出改进方案。关键字：TSP问题蚁群lingo最优1问题重述有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到。他预选了十个省市旅游景点，如表1所示。省市景点名称在景点的最短停留时间市恐龙园4小时市崂山6小时八达岭长城3小时祁县乔家大院3小时市龙门石窟3小

6、时市7小时市黄鹤楼2小时市始皇兵马俑2小时市庐山7小时市普陀山6小时问题：根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。(1)如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。(2)如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。(3)如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数

7、学模型并设计旅游行程表。(4)如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(5)如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。1问题分析2.1问题(1)游客旅游费用包括交通费、住宿费、景点门票、饮食其他费用三个方面。首先，每个景点的门票费用与路线选取无关。通过考虑路程最短，可以让城市之间的交通费用达到最小，同时可以缩小旅游时间，由此减少住宿费用。旅游路线的费用与旅游路线的长度正相关，因此选取最短的旅游路线和离每个景点最近的火车站

8、，可以令交通费用最少。其次，在距离景点一定围，选取最便宜的旅馆入住，尽量减少住宿费。且规定，游客在晚上12点之前不能坐上离开城市的交通工具，则住宿，在旅客不能在早上6点之后到达下一个城市，则在该城市住宿。因此，运用蚁群算法，将旅游路线规划为最短；查找离景区一定距离围最便宜的旅