《开封到凤凰的旅游路线优化问题毕业论文.doc》由会员分享，可在线阅读，更多相关《开封到凤凰的旅游路线优化问题毕业论文.doc（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、开封到凤凰的旅游路线优化问题 摘要随着当代工作、生活节奏的加快，“旅游”，这个健康，休闲，积极，快乐的生活方式，逐步成为了大家生活中必不可少的一部分。如何合理安排旅游路线，以最小的资源消耗，换取最大的回报，成为了“驴友”们考虑的关键问题。就理所当然的产生了最佳旅游路线优化问题。本文主要研究的是如何选择最佳线路的问题。所谓最佳旅游路线，即是通过选择旅游线路，达到以相对最少的资源消耗，换取游客或者旅行团最大的游览效益。对于线路的选择，下面将用湖南省著名景区凤凰古城的多方面进行讨论，设计适合不同人群，从开封到凤凰相对来讲性价比最高的旅游线路。本篇论文中，我们主要考虑旅行中的费用及旅行时间。运用运筹学
2、中的破圈法和多维数理统计中的马氏路径两种思路,进行研究和结果讨论与两种方法的优缺点评价。并且基于对此类问题的研究，设计出最佳的旅游路线。并且可以推广到不同地区景点之间的转换。关键词：最优路径 ；马氏距离；避圈法1， 引言随着生活水平的提高，人们不只满足衣食上的富足，有了更高的精神追求和自我实现的需求。同时，生活压力也在增大，人们需要减压以应对生活上的烦恼。诚然，旅游成为实现人们自我成长和身心放松的途径。随着人民生活水平的提高，使旅游日益成为现代人类社会的生活方式和社会经济活动之一。旅游业以其强劲的势头成为全球经济产业中比较具活力的“朝阳产业”。随着我国国民可支配收入和闲暇时间的增多，随着市场经
3、济的蔓延。居民的生活压力越来越达，人们需要减压和休闲，应运而生，旅游业就迎来了一个又一个春天；国内旅游需求日益扩大应运而生，出现了“驴友”，“自驾游”，“跟团游”等新名词。为了更好地实现放松的目的，规划驴友路线成为驴友和旅行团出发前的头等大事。很多游客都有这样的感慨“没怎么看，排队和等车的时间太长”，“人太多，没来得及拍照”，“下雨了，耽误了行程”，“住宿吃饭临时找，太耽误时间”。引起这些后果的原因无非是，没合理规划旅游路线，没预定好酒店，不关注当地天气与客流状况，对于突发事件没想好应急措施。为了避免没有合理规划旅游路线的问题，做好旅游路线规划对于驴友和旅行团的重要性就体现出来了。这就我做此类
4、问题的目的。本文浅谈一下，从开封到凤凰的旅游路线安排，主要从时间和金钱两方面讨论。以此为例，可以推广到其他地区和景点之间的旅游路线安排。本文搜集了从开封到达凤凰乘坐几种不同的交通（这里每种交通工具只举一个例子）所需要消耗的时间和金钱等资料。运用运筹学中的避圈法和多元数理统计中的马氏变换两种不同的方法，去探究从开封到达凤凰的最佳旅游路线。避圈法中赋权图的权系数，承载了价格和时间的关系。针对不同人群对于时间和金钱的态度也是不同的额，权系数对于不同的人也是不同的。这使得避圈法更加具有人性化，实用性更加广泛。通过引用马氏距离，计算出哪条路径更加合理。将两种方法做出来的结果加以对比，来评价此类问题运用马
5、氏距离和避圈法来解决的优劣。本文首先以图表的形式，列出从开封到达凤凰几种方式所需要的时间和金钱，给出已知量。提出本文所要解决的主要问题，如何把时间和金钱统一起来。为了解决这一问题，查阅资料发现，可以使用避圈法和马氏变换两种方式。交代最小支撑树的概念与避圈法的步骤与马氏距离的做法等相关知识。通过相应求解来判断哪条路径为最优。把所得结果加以对比，从而研究出马氏距法和避圈法在解决这一问题中，优点在哪里，缺点在哪里。推广之，在以后的此类选择最佳旅游路线问题中，用哪种方法更加合理。1， 提出问题表一：从开封到达凤凰的可选路线的价格耗时表 开封-郑州 郑州-长沙 长沙-吉首 吉首-凤凰车次/航班价格车次/
6、航班价格车次/航班价格车次/航班价格坐飞机前往机场大巴40元南航CZ39441120元长途客车110元中巴15元所需时间 1小时 1小时15分钟 4小时 1小时坐火车前往 火车K1159 230元K903181元中巴15元所需时间 14小时 8小时 1小时坐火车前往（方式2）郑开公交 7元 火车K267 240元中巴15元所需时间 1小时30分钟 15小时 1小时坐客车前往郑开公交 7元长途客车260元长途客车110元中巴15元所需时间1小时30分钟12小时 4小时1小时车次/航班价格车次/航班2.1图表二：（从开封到达吉首不同路径的价格与耗时线形图） 注释：（1）从吉首到达凤凰的途径只有一条
7、，所以，忽略这段，故只考虑从开封到达吉首。（2）两点之间的线段代表从起始点到终点的路径，其具有两个价值量，一个是耗时，一个是价格，可以用坐标的形式表示出来。例如AB=（x,y）,其中x代表价格；y代表时间。B C A C D B CCD= (110,1) BD=(240，15) CD=(110，4 ) CD=(81, 8) AB= (40，1) BC=(260，12) AC=(230，14) AB=(7 ,1.5) BC=(1120，1.25)要计算从A到D的最优路径，我们考虑两个方面，耗时和金钱，先分开考虑，首先考虑金钱问题，由于路径很少，我们不难得出：价格最低路线：ABDE即：从开封出发坐
8、郑开公交到郑州，从郑州坐火车道吉首，从吉首坐中巴到凤凰。价格为262元，耗时17.5个小时。再考虑时间问题，同理可得出，时间最短路线:ABCDE 即：从开封出发坐机场大巴到达郑州，从郑州乘飞机到达长沙，从长沙到吉首坐长途客车，从吉首到达凤凰坐中巴。耗时：4.25小时，花费:1285元。 如何把时间和价格统一到一起考虑成为关键，单纯考虑价格和时间都是不完善的，不具有实际应用意义。把价格和时间统一到一起考虑，有两种思路。一，赋予价格和时间不同的权系数，利用运筹学中的破圈法求解。二，利用多元数理统计中的马氏距离来计算路径，求得最优路径。3.理论模型定义1：给图G=(V,E),对G中的每一条边v,v,
9、相应地有一个数w,则这样的图G称为赋权图，w称为边v,v上的权。 1我们问题提出环节可知，图表二是一个赋权图，它的权可以为其价格，也可以为其时间。定义2：如果T=（V,E）是G的一个支撑树，称E中所有边的权之和为支撑树的权，记为w(T)。如果支撑树T的权w(T),是所有支撑树的权中最小的权最小的，则称T为G的最小支撑树。 图表二中使得价格最低或者时间最短就是求最小支撑树问题。求最小支撑树问题，可以用避圈法。3.1避圈法开始选一条最小权的边，以后每步中，总从与已选边不构成圈的那些未选边中，选一条权最小的。（每步中，如果有两条或者两条以上的边都是权最小的边，则从中任选一条）。算法具体步骤如下：第一
10、步：令i=1，为空集第二步：选一条边属于E，使是使不含圈的所有边e（）中权最小的边。令,如果这样的边不存在，则是最小树。第三步，把i换成i+1，转入第二步。 3.2马氏距离当不同类别中样本点的分散程度不同时，用通常的欧式距离来比较样本点之间的远近是不合适的。因此有必要通过变换把不同类别样本点的分散程度变成一致的，这样才可以便于同一的量来比较。为此我们采用马氏变换。 2我们研究的问题是如何统一时间和价格两个量，马氏变换可以满足条件。为此，我们研究如何马氏变换来解决问题。马氏变化的定义：设为一数据阵，为它的协方差阵，如果Sx可逆的,则为马氏变换，其中为中心化阵。即经过马氏变换后数据阵的协方差总为一
11、单位阵。如果视X的行为样本，列为变量，则经过变换后得到Z。一个数据的协方差矩阵表现它样本点的分散程度，这样样本点的分散程度都成一致的，即用单位阵反应分散结构。由此我们引入判别方法 。 设 i=1,2分别为一给的两类样本点组成数据阵，S,S分别为样本协方差矩阵，u，u分别为两类样本的均值（即重心），对于任意给定的一个样本，我们称 i=1,2 马氏距离是由印度统计学家马哈拉诺比斯提出的，表示数据的协方差距离。它是一种有效的计算两个未知样本集的相似度的方法。 3与欧氏距离不同的是它考虑到各种特性之间的联系，即独立于测量尺度。马氏距离的其它定义：马氏距离也可以定义为两个服从同一分布并且其协方差矩阵为的
12、随机变量的差异程度。 4 模型求解4.1避圈法从开封到达凤凰所有路线中价格最高的为ABCDE,价格为40+1120+110+15=1285元，把1285元作为基数一，用每段路程的价格除以1285元，所得就是每段路程的相对价格。这么做的目的是使每段的价格有个统一的标准，利于相互比较和运算。我们称计算得到价格为相对价格，用p来表示。计算可得到，各段上的相对价格如下（所得数据保留到小数点后四位）： 开封到达凤凰的路线中，时间最久的为ACDE，时间为14+8+1=23小时，把23作为基数一，每段的时间去除以23，所得为每段相对的时间。这么做的目的是使时间有个一个统一的标准，利于比较和计算。我们称这么做
13、所得的结果为相对时间，用t来表示。计算可知，各段上的相对价格如下： 因为对于不同的人，他们对于时间和价格的态度不同，即他们所定义的权系数个不同。推广之，设对价格的权系数为A，对于时间的权系数B。每段的相对价格为p,相对时间为t。同时假设p和t变化相同量时，所带来的影响是相同的。每段的关于时间和价格的权系数就应该为A*p+B*t,由于p，t是已知的，只需要根据不同人定义的权系数A,B来讨论即可。计算ABCDE的所有路线的系数和为A+0.1359B计算ACDE的所有路线的系数和为0.2537A+0.9993B计算ABDE的所有路线的系数和为0.3043A+0.7609B计算ABCDE的所有路线的系
14、数和0.3046A+0.8043B1若第一条路线为最优路线，即它的系数为最小，A+0.1359B0.2537A+0.9993B,可知AB1.1569A+0.1359B0.3043A+0.7609B,可知AB0.8984A+0.1359B0.3046A+0.8043B,可知AB0.9612取其交集，即AB0.89842若第二条路线为最优路线，即它的系数最小，0.2537A+0.9993BA+0.1359B，可知AB1.115690.2537A+0.9993B0.3043A+0.7609B,可知AB4.71150.2537A+0.9993B0.3046A+0.8043B,可知AB3.8310取其交
15、集，即AB4.71153若第三条路线为最优路线，即它的系数最小，0.3043A+0.7609BA+0.1359B，可知AB0.89840.3043A+0.7609B0.2537A+0.9993B，可知AB4.71150.3043A+0.7609B0.3046A+0.8043B, 显然成立取其交集，即0.8984AB4.71154若第四路线为最优路线，即它的系数最小，0.3046A+0.8043BA+0.1359B，可知AB0.96120.3046A+0.8043B0.2537A+0.9993B,可知AB3.83100.3046A+0.8043B0.3043A+0.7609B，可知AB4.711
16、5取其交集，为空集，第四条路线在任何条件下都不可能为最优路线综上所述，对于不同的AB的范围，选取不同的路线当AB4.7115时，选择第二条路线当0.8984AB4.7115，选择第三条路线当0AB0.8984，选择第三条路线4.2用马氏距离的方法，计算所得数据保留到小数点后两位。从A到E一共有四条路线，分别设为a,b,c,d，路线a的价格应为40+1120+110+15=1285元，路线b的价格为230+81+15=326元，路线c的价格应为7+240+15=262元，路线d的价格应为7+260+110+15=392元，路线a的时间应为4.25小时，路线b的时间为23小时，路线c的时间为17.
17、5小时，路线d的时间18.5小时。abcd四条路线的价格可设为x,时间设为y(i=1,2,3,4) ,可知其均值向量为u=（566， 16.94），其中两个分量分别为时间和价格的平均值。再求其协方差矩阵： 其中用估计值来做。 4 带入数据，通过计算可得到 D(X) 带入数据，计算 通过比较可知最小，即用马氏距离判断可得到第三条路线为最优路线。5.讨论与结果马氏路径方法与避圈法优缺点及其评价马氏路径计算出来结果是唯一的，符合大众标准的，准确性高它不受量纲的影响，两点之间的马氏距离与原始数据的测量单位无关；由标准化数据和中心化数据(即原始数据与均值之差）。缺点是没有考虑不同人看待时间和价格的态度是
18、不同的，相对避圈法而言不具备人性化和多样化。避圈法的方法没有考虑到时间和金钱同时变化一个单位时带来的影响是相同，但其的思路清晰简单，运算起来，也不麻烦，对于在数学上，造诣不太高的人，可以很好地理解和运用，更加人性化，针对马氏距离的缺点，考虑到不同的人，赋予金钱和时间不同的权系数。 总而言之，马氏距离方法精确，经典，被前人验证过，缺点是运算出来的结果是唯一的；避圈法更加实际，人性化，考虑到不同人群，不同的价值观，虽然不是很精确，但比较贴近实际。尽管方法不同，思路不同，但在本文讨论的问题中，其最终结果是有一致的地方。总归，目的都是更好的为人类服务，选择最佳旅游路线马氏距离方法与避圈法所得结果如下，
19、马氏距离：第三条路径为最优。避圈法：不同权系数决定不同的路径。相比较而言，在某一程度上，避圈法更加好些，值得推广。6.结论与展望本文旨在利用运筹学理论，运用两种方法，将复杂的旅游线路的时间和价格因素条理化。使得以往我们印象中的旅游跟随旅行社的盲目性和随从性，变得更加理智，更加效率。本文解决的关键问题是如何把时间和金钱统一起来看待。避圈法中通过权系数来平衡这一问题。避圈法优点在于考虑到不同人群看待时间和金钱不同，使得此类问题可以大众推广；缺点是计算时没有考虑相对时间和相对价格变化同等量带来的影响是否相同。马氏距离优点是两点之间的马氏距离与原始数据的测量单位无关；由标准化数据和中心化数据，计算出的
20、二点之间的马氏距离相同。相比较而言，避圈法更有优势。通过这样的研究，可以使资金投入规避和减少了无谓的开支和预算，时间也得到了有效的控制和改善，能够使以后的针对性的景区旅游线路，更加精细化，明确化，合理化，规范化。这是我写下本文所希望达到的目的。也希望本文能够对开封去往凤凰日后景区旅游线路的设计和优化，起到一定的作用。参考文献：1甘应爱.运筹学（第三版）.清华大学出版社.20052胡国定 ,张润楚.多元数据分析方法纯代数处理.南开大学出版社.19903汪西莉.一种基于马氏距离的支持向量快速提取法.西安电子科技大学学报.20044，宋运红.河北三沟地区水系沉积物数据马氏距离处理与应用. 吉林大学硕士论文 .2009