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