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

实用文案 标准文档 2011年第八届苏北数学建模联赛 承 诺 书 我们仔细阅读了第八届苏北数学建模联赛的竞赛规则。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。 我们的参赛报名号为： 参赛组别（研究生或本科或专科）： 本科组 参赛队员 (签名) ： 队员1：唐文辉 队员2：徐玲 队员3：涂杰 获奖证书邮寄地址： 摘要 本文就旅游线路的优化设计问题，根据旅游者在旅行中的旅游时间，旅游费用，旅游地点，交通状况，住宿等因素的约束，借助图论，蚁群算法，建立最优化数学模型。在最短路路线的基础上，综合考虑交通，用费，时间对问题（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 最优 问题重述 江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。他预选了十个省市旅游景点，如表1所示。 省市 景点名称 在景点的最短停留时间 江苏 常州市恐龙园 4小时 山东 青岛市崂山 6小时 北京 八达岭长城 3小时 山西 祁县乔家大院 3小时 河南 洛阳市龙门石窟 3小时 安徽 黄山市黄山 7小时 湖北 武汉市黄鹤楼 2小时 陕西 西安市秦始皇兵马俑 2小时 江西 九江市庐山 7小时 浙江 舟山市普陀山 6小时 问题： 根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。 (1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。 (2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。 (3) 如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。 (4) 如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。 (5) 如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。 问题分析 2.1 问题(1) 游客旅游费用包括交通费、住宿费、景点门票、饮食其他费用三个方面。首先，每个景点的门票费用与路线选取无关。通过考虑路程最短，可以让城市之间的交