B题最佳旅游路线设计.doc

2011年第八届苏北数学建模联赛 承 诺 书 我们仔细阅读了第八届苏北数学建模联赛的竞赛规则。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。 我们的参赛报名号为： 参赛组别本科 参赛队员 (签名) ： 队员1： 队员2： 队员3： 获奖证书邮寄地址： 2011年第八届苏北数学建模联赛 编 号 专 用 页 参赛队伍的参赛号码： 竞赛统一编号（由竞赛组委会送至评委团前编号）： 竞赛评阅编号（由竞赛评委团评阅前进行编号）： 2011年第八届苏北数学建模联赛 题 目 摘要 随着我国全面建设小康社会的推进，人民的生活质量不断提高，旅行游览活动作为一种新型的高级社会消费形式 建模过程中，首先用科学分析的方法，确定主要因素并对其作数学抽象，再针对各因素综合运用多种数学方法进行分析求解。第一，我们用主要目标法建立了“离散型单目标优化模型”，并分别确定了五个问题的目标函数以及约束条件；第二，我们将旅游景点看作地图中的点，利用图论中著名的哈密顿回路问题和顺序递推的方法建立了“动态优化模型”；第三，通过查询数据，并利用数理统计的方法求解模型中的参数，从而得出一个与实际接近的完整数学模型。 求解问题过程中，首先把路途时间（路费）、景点停留时间（门票）、住宿时间（住宿费用）和其它时间（其它费用）综合考虑，借鉴历史上著名的货郎担问题的解法巧妙的将路程优化问题转化旅游时间和旅游费用的优化问题，在利用“Floyd算法”时分别将旅游时间和旅游费用作为权成功解决问题一与问题二。然后采用“蚁群算法”在景点个数不确定的条件下求解出任意景点个数的优化路线，并与约束条件校核，确定出最多可以旅行景点数目的行程，从而解决问题三、问题四和问题五。 最后对模型进行优缺点分析，为提高模型的可靠性和模型的改进提供依据。 关键词 离散型目标优化 动态规划模型 货郎担问题 Floyd算法 蚁群算法 一、问题的重述 随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点，如下表所示。 预选的十个省市旅游景点 省市 景点名称 在景点的最短停留时间 江苏 常州市恐龙园 4小时 山东 青岛市崂山 6小时 北京 八达岭长城 3小时 山西 祁县乔家大院洛阳龙门石窟 6小时 问题： 根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。 (1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。 (2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。 (3) 如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。 (4) 如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。 (5) 如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。 二、问题的分析 此问题是在一定约束条件下的离散型目标优化问题，即从旅游时间、旅游费用、以及旅游景点数目这三个因素来优化旅游线路。 旅游时间由交通时间、景点停留时间、住宿时间以及其他时间组成。旅游费用由交通费用、门票费用、住宿费用以及其他费用组成。 将各个旅游景点视为平面上不同位置的点，从徐州出发最后回到徐州形成一闭合回路，从而利用图论的相关知识求解。 旅游景点的平面图 各景点门票价格表 景点 恐龙园 崂山 长城 乔家大院龙门石窟 选择第i条路线总费用 选择第i条路线总时间 c+1 个点可选择路线的总数 a 吃饭等其他费用 第i条路线到景点j间的路费 第条路线第个景点的门票 第条