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) 城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。
(B) 市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。
(C) 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。
晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。
吃饭等其它费用60元/天。
(D) 假设景点的开放时间为8:00至18:00。
（E ）忽略地域差异，假设市内乘车时间和费用相同并以平均值计算，住宿费用相同设为50元/夜。
（F)假设所有城市交通状况良好，不出现堵车、晚点情况。
三、符号说明C 旅游景点的个数F i选择第i 条路线总费用 Ti 选择第i 条路线总时间 n c 1+ c+1 个点可选择路线的总数 a 吃饭等其他费用b ij 第i 条路线到景点j 间的路费g ij 第i 条路线第j 个景点的门票k ij第i 条路线第j 个景点的住宿费用 l ij 第i 条路线到第j 个景点的路上时间mij 第i 条路线第j 个景点的停留时间 q ij 第i 条路线第j 个景点的住宿时间u 其他时间，包括吃饭、等待时间等x ij 第i 条路线第j 个景点是否需要住宿 (0--1变量)以上时间的单位均为小时，费用的单位均为元四、 基本模型的建立模型一 离散型单目标优化模型经分析，此题属于单目标优化问题，一到五问要求在不同的约束条件下对不同的目标进行优化，考虑到实际问题，我们可以建立离散型目标优化模型来解决问题。
我们从十个景点中选择C 个景点，首先写出第i 条路线的总费用与总时间的表达式 我们引入住宿决策变量⎩⎨⎧=个景点不需要住宿条路线在第第个景点需要住宿条路线在第第j i 0j i 1x ij则uT a q x m l T k x g b ij ij ij c j ij i ij ijij c j ij +++=+++=∑∑==)*(24/*)*(11i F i = 1,2,3,4···n c我们引入函数h 来描述时间和费用与可以选择旅游景点个数的关系 ()T F h c ,=由于旅游的路费和路上时间是由交通方式的选取和实际中的交通系统有关的，我们将这些信息收集并放到集合W 中，将可选择的路线放到集合V 中。
下面我们结合一到五问中的问题分别确定优化目标和约束条件。
第一问以旅游总费用为作为优化目标，要求它越小越好，而要求将10个景点旅游玩，对时间没有限制。
可用下面模型来描述。
10..)min(=C t s F i最终在集合W 和V 中确定最优的i 与交通方式。
第二问以旅游总时间为作为优化目标，要求它越小越好，而要求将10个景点旅游玩，对旅游总费用没有限制。
可用下面模型来描述。
10..)min(=C t s T i最终在集合W 和V 中确定最优的i 与交通方式。
第三问以可以旅游的景点个数为优化目标，要求它越大越好，而要求旅游总费用不超过2000元，对旅游总时间没有限制。
可用下面模型来描述。
2000..)),(max(<=F i t s T F h最终在集合W 和V 中确定所有满足条件的i 与交通方式。
第四问与第三问有相同的优化目标，但是要求旅游总时间不超过五天，而对旅游总费用没有要求。
模型可以改写如下12024*5..)),(max(=<=T i t s T F h第五问则是三四问的综合，模型如下 2000..12024*5..)),(max (<==<=F T i i t s t s T F h模型二 动态规划模型把每个旅游景区景点看做途中的一个节点，各景区景点之间的公路看做途中对应节点间的边，相对应的行程距离看做对应边上的权，所给各景区景点间的交通路线网就转化为加权网络图G ，遍游各个景区景点的最佳旅游路线问题就转化为在给定的加权网络图中寻找从给定出发点出发，行遍所有顶点至少一次且只有一次再回到定点，使得总权（路程）最小，此即TSP 问题。
对于本问题：[,,]{(,)|,},{(.)|,}{0,1,,11}G N E W E i j i j N W w i j i j N N L ==∈=∈=设V1，V2，V3..........，Vc 是要旅游的景点，景点Vi 到景点Vj 的距离为dij ，现在求从V0（徐州）出发，经各景点一次且仅一次返回V0的最短路程，这让我们联想到著名的货郎担问题，可以建立如下动态规划模型。
设S 表示从V0到Vi 中间可能经过的景点集合，S 实际上是包含除V0和Vi 两个点之外的其余点的集合，但S 点中的个数是随问题改变的。
用状态变量（i ，s)表示从V0出发，经过S 集合中所有点一次最后到达Vi 。
用最优指标函数fk(i ，s)表示从V0出发，经过S 集合中所有点一次最后到达Vi 。
决策变量Pk (i ，s) 表示从V0经K 个中间城镇的S 集合到Vi 城镇的最短路线上邻接Vi 的前一个城镇，则动态规划的顺序递推关系为：⎪⎪⎩⎪⎪⎨⎧===⎢⎣⎡⎥⎦⎤+=)...2,1,,.......2,1(,(),(min ),(10c i c k i S j s i d f d f f i ji k k 空集） j 属于SC<=10 且C 为整数根据上述的递推模型，我们只要提供一个输入就可以规划出最优的路线。
五、 问题解答根据实际情况，每个旅游景点只能去一次，而且要求所有景点距离之和最小，即按照最短路径方式设计旅游路线。