《C最佳旅游路线设计 孟建龙》由会员分享，可在线阅读，更多相关《C最佳旅游路线设计 孟建龙（29页珍藏版）》请在金锄头文库上搜索。
1、安徽工程大学安徽工程大学 数学建模数学建模 课程设计论文课程设计论文题目：最佳旅游路线设计题目：最佳旅游路线设计指导老师：指导老师：周金明周金明成成 绩：绩： 完成日期：完成日期： 2013 年年 7 月月 3 日日0摘 要：旅游的最佳线路的选择会直接决定旅行者的旅行时间和金钱的花费，设计 合理可行的旅游线路则使这一费用的唯一标准，由于实际纷繁复杂的景点，交 通，时间等对方面因素的综合影响和相互作用下，通过“点线图”将复杂的现 实景点和路线表示在便于处理的简单的只有点和线组成的图中，便于我们运用 一定的数学工具进行最优化处理。 通过综合各方面的信息、资源，并对其进行相应的处理整合如“点线图”
2、， 在保证合理，准确，有效，详实的同时，将抽象的，复杂的实际概念和数据量， 转化为有价值的，精确的时间和费用值。这样“点线图”中每一个点就对应地 包含其最佳停留时间和花费情况，其中为了合理的表示花费，构造“城市分” 的概念来表示。而每一条线也都对应地包含所花费的时间和费用，这些数量通 过表格给出，在求取最优解时视为相应点或线的特性。为了难保证这种转化的 实际意义和有效性，准确性，通过多方数据的综合分析、平均，共同得到的综 合得到。 在“点线图”的基础上，做出必要假设和的基础上，将图形做进一步的简 化分区，将一个图形分成若干个子图，对图进行处理，把问题拆减。利用已经 比较成熟的 Dijstra
3、算法，找到其它城市距离中心城市（这里使乌鲁木齐）的最 小距离，然后利用避图法找到最小树，这样在路线周围，结合图形特点，围绕 近似路线周围作局部搜索，在大大减少数据运算的情况下，得到相对最优解。 对得到的最优解进行检验，验证其确实是比较优的线路。即基本处理过程为：抽象图形 分解图 找到近似算法 子图中在近似算法得到路径 周围搜索 调整边界 检验路线 分析建模、解模的整个过程，合理地分析可以得到，方法可以被推广到其 它更加复杂的环境。【关键词】 ： 点线图 城市分 旅行推销员问题 哈密顿 Dijkstra 算法， 避图法 1一、一、 问题重述问题重述王先生夫妇是华东某高校的年轻教师，打算暑假中到新
4、疆旅游。受文学作品的影响，天 池、达坂城、吐鲁番、楼兰古城、伊犁都是他们十分向往的地方，新疆的其他地方对他们也 有很大的吸引力。 1.请你们为他们设计合适的旅游路线，使他们在今年暑假一个月的时间里花最少的钱游 尽可能多的地方，并估算除吃饭之外的费用。 2.如果他们打算今、明两年暑假完成对新疆的旅游，请你们为他们设计合适的旅游路线， 使在新疆境内的交通费用尽量地节省。 3.如果华东某高校的少数民族研究所组织对新疆文化考察，考察分三组进行，用于交通 的时间和前两种情况相同，但考察时间是旅游观光时间的四倍，请你们为他们设计合适的考 察路线，以便尽早完成考察任务。 4.新疆自治区旅游部门为迎接“五一旅
5、游黄金周” （考虑到远途旅游，自治区内游程延 长为十二天）准备为自治区外的游客组织多条旅游路线以分散游客，提高接待的质量。在假 设参加你们设计的各条路线的游客人数与整条路线的接待能力成比例的条件下，请你们为新 疆自治区旅游部门设计合适的、准备向游客推介的全部旅游路线。二、 问题的假设问题的假设1、为了尽量节约费用，由于飞机的价格要远高于铁路和公路，而后两者基本相同。所 以在新疆境内的交通费用，以铁路票价为主，没有开通铁路的线路，则以公路票价为主； 2、对于公路的收费没有明确标价的路段，以两个旅游点之间的公路里程（km）除以平 均时速（60km/h）进行估算。对于少数公路也欠发达的地区，则以速度
6、折半为 30km/h 估算；3、假设在新疆的所有景点中，对任何的 A、B 两个景点，从 A 到 B 所需花在路上的时 间与从 B 到 A 的相同，即忽略例如由于列车停靠站不同所造成的运行时间上的一些差异； 4、暑假的一个月为 31 天，考虑到往返新疆的时间，故花费在新疆境内的旅游时间以 30 天计； 5、在新疆境内各旅游景区的住宿费用均为一个定值：RMB 150 /标准间（两人）/天； 6、设旅游途中的休息调整时间合并在每个景点的观光逗留时间之内，不再予以单独的 计算； 7、不考虑交通费用在白天和夜晚的区别， （如火车硬座与卧铺价格上的差异等）均以最 低价格即硬座票价计算。 8、对于旅行社推出
7、的旅游线路的设计，与自助游不同，我们认为其主要目标不在于节 省费用而在于多游览美景和旅途的舒适，因此假设在新疆省内白天的时间都用来游玩，景区 间的行程则采用飞机（时间短故可忽略）连接或在晚间乘车抵达。 9、假设铁路和公路交通费用的票价，与行驶的里程近似成线性关系，而又因为列车或 汽车时速也是一定的，这样，某一段路程需要的交通费用也与其时间呈近似的线性关系，这 样，求最小费用，也即求最短路线。 注：假设 9 的依据： 我们对部分景点间往返的时间和费用进行采样，并作回归分析如下页图所示： （R 平方为 0.9819，F 值为 595.6604，说明两者呈很强的线性关系。几乎可以认为交通301001
8、2费用与路程成正比。 ）（图（图 1：价格：价格距离采样关系图）距离采样关系图）三、三、 符号的约定符号的约定编号景区（景点） 名称编号景区（景点） 名称1乌市11天鹅湖2石河子12喀什、香妃 墓3伊犁13和田4天池14民丰5吐鲁番15博乐6火焰山16楼兰、罗布 泊7哈密17阿勒泰8库尔勒18克拉玛依9库车19奎屯市10阿克苏20天鹅湖 1.在所规划的旅游行程中,可能重复经过某些景点,对于经过而不停留的景点,采用景点表3010013示; 2.总路程 S 3.不均衡度3.旅游推荐总天数tD4.考察总天数kcD四、四、 模型建立与求解模型建立与求解4.1 模型模型 一一1.1.问题一问题一一、问题
9、分解：1.以旅游景点逗留的天数作为自变量，以单位天数所用的钱为目标函数，取最小值。ptPpM t2.选择最优巡回路，我们参考了如下两个定义： 巡回路：过各个节点，每个节点至少经过一次的回路。 哈密尔顿回路：每个节点只经过一次的回路。 总长度最小的巡回就是最优巡回路。 最优巡回赂和最优哈密尔顿回路在如下条件下是等价的；定理：定理：回路中，任 2 个节点，若能满足下列三角不等式：,G V E W,ijV VijikjkWWW,;ijkkikjijV V VV VV VV VV则最优巡回路与哈密尔顿回路相同。 理论模型建立的基本思想是：首先，对于任意一个无向网络，利用任意节点之间的最短路算法构建一个
10、等价网络,G V E W，在网络中个节点之间的距离用最短路代替。据此，解得的最优哈密尔顿0000,G V E W0000,G V E W回路就可以很方便的还原为最优巡回路，实质是 TSP 问题。而解最优哈密尔顿回路的方法可以才用最优 二叉树法（参考书164 页） 、DijKstra（见参考书2336 页）法等。解 TSP 问题也有相应的软件求解，更 为方便。 基于以上对问题 1 的分析，要解决问题 1 的关键在于每种旅行路线方案的最优解的获得，而获得最 优解的关键则在于确定网络的最优巡回路。第 1 步 将图变换为。,G V E W0000,G V E W第 2 步 为方便表示，将图中各节点进行
11、编号如表 1-1编号景区（景点） 名称编号景区（景点） 名称1乌市11天鹅湖2石河子12喀什、香妃3010014墓3伊犁13和田4天池14民丰5吐鲁番15博乐6火焰山16楼兰、罗布 泊7哈密17阿勒泰8库尔勒18克拉玛依9库车19奎屯市10阿克苏20天鹅湖表 1-1第 3 步 根据达坂城（位于乌鲁木齐） 、天池、 、吐鲁番、楼兰古城、伊宁五个点组成的网络求其完备图，其中任意两点间的最短距离可表示如表 1-2：A AC CD DE EP PA A0 05805801831837557554242C C5805800 0763763889889622622D D1831837637630 0590
12、590225225E E7557558898895905900 0797797P P42426226222252257977970 0表 1-2 第 4 步 求解最优哈密顿回路，此处应用 WINQSB 软件中的 Networking model 模块求解得Solution for 5 place: Minimization (Traveling Salesman Problem) From Node Connect ToDistance/CostFrom NodeConnect ToDistance/Cost 1 AC580 4DP225 2 CE889 5PA42 3 ED590 Total
13、Minimal TravelingDistance or Cost=2326 (ResultfromBranchand BoundMethod) 即最优哈密尔顿回路为：ACEDPA 即：乌鲁木齐伊宁楼兰古城吐鲁番天池乌鲁木齐 其最短距离为 2326 KM。 仅对此五个地点进行游览，则有：，116345116345140120901201500.1 2326minttttt ttttt 3010015116345116345 t1=4;t2=1;t3=4;t4=4;t5030. .030(P=1,16,3,4=,5,)4;ppttttttttttsttt 取整数至此完成了对第一组路线的建模，接下
14、来可用 LINGO 解此非线性规划（原程序及详细结果见附录 2） ， 求得目标函数的最优解。解得：Objective value=117.42 116345t =4 t =1 t =17 t =4 t =4由此可见，上述非线性规划建模的结果实质是证明了，目标函数在以下条件下成取得最优解： （1）各个景点所用的时间总和正好等于 30 天。 （2）在各景点间满足交通距离最短的前提下，应该在单位时间花费最小的景点逗留时间长，而其 余单位时间花费较大的景点只要满足推荐逗留时间即可。 根据上述结论队之前的问题1模型的假设进行修正与简化。经简化与修正后，模型可陈述如下：在一 个月的时间里，至少保证分配给以
15、上五个地点推荐逗留时间，在剩余的时间里优先考虑离上述各景点距 离最近、单位时间消费较少的景点。同时保证各景点推荐天数少于30天。 这样就不必如之前的假设一样，每加一个景点计算一次最优解。而只需选出具备上述条件的景点， 与前五个景点构成新图，求新图的完备图的，继而求其最优哈密尔顿回路，最后将所求结果回带到相应 的目标函数中。 按照上述方法求解，则： 第1步 按要求选出其余合适的点。图1-2 优先考虑达坂城（位于乌鲁木齐） 、天池、 、吐鲁番、楼兰古城、伊宁这五个点连通后沿途的点。将 选出的点与此五点组成新图，如图1-2。 第2步 求图1-2的完备图，其中任意两点间的最短距离可表示为：301001
16、6ABCDEFHKOPS A0160 580 42183 221 555 392 488 755 286 B160 0420 202 343 381 562 232 328 915 126 C580 420 0622 736 616 518 188 247 710 294 D42202 622 0225 263 592 722 908 797 328 E183 343 736 225 038390 720 671 590 469 F221 381 616 263 380428 758 709 628 507 H555 562 518 592 390 428 0330 638 200 436 K392 232 188 722 720 758 330 0308 530
