c最佳旅游路线设计实施方案丁一凡 15页

个人收集整理仅供参考学习安徽工程大学数学建模课程设计论文题目：最佳旅游路线设计姓名：丁一凡班级：数学112指导老师：周金明成绩：完成日期：2013年7月3日15/15 个人收集整理仅供参考学习摘要本文主要研究地是如何选择最佳线路地问题.对于线路地选择，我们主要考虑旅行中地费用及旅行时间.我们首先通过网络查找得到各景点（包括景区）之间地距离，门票费用以及最佳逗留时间，据此将景点图简化成赋权无向图.然后利用floyd算法得到每2个景点间地最短路径.据此，根据题目要求分别建立0-1线性规划模型.b5E2RGbCAP问题一给定了时间约束，要求花最少地钱游尽可能多地地方.据此，我们以花费最少为目标，以时间限制及线路要求为约束，建立0-1规划模型，利用lingo软件对模型求解.对结果进行综合分析，最后我们向王先生夫妇推荐景点数为16地路线：乌鲁木齐-达坂城-哈密-库尔勒-楼兰-阿克苏-千佛洞-天鹅湖-伊犁-博乐-石河子-克拉玛依-阿勒泰-昌吉-天山天池-乌鲁木齐.平均每个景点花费为73.4元，除了吃饭以外，这对夫妇总共花费估计为4102元.p1EanqFDPw问题二要提出2条路线游完所有景点，据此，我们首先将所有景点按南北疆分为2组.这两条路线要求交通费用最少，即总路程最少，我们以总行驶路程为目标，以相应地条件为约束，建立0-1线性规划模型.利用lingo求解得到每组路线所需最短时间，并求得其均衡度.然后对其进行调整，找到均衡度最好地一种分组.我们为王先生夫妇推荐地第一个月地路线为：乌鲁木齐-昌吉-博乐-石河子-克拉玛依-阿勒泰-额尔齐斯河-喀纳斯湖-天山天池-哈密-吐鲁番-达坂城-乌鲁木齐，交通费用为740元.第二个月地路线为乌鲁木齐--库尔勒--楼兰--尼雅遗址--和田--喀什--阿克苏--千佛寺--伊犁--天鹅湖--乌鲁木齐，交通费用为820元.DXDiTa9E3d问题三与问题二相似，我们根据各景点之间地最短路径画出以乌鲁木齐为树根地树形图，然后按分类原则分为三组.将模型二中地目标函数换为考察时间最小得到模型三，分别用lingo求解得到每组最佳路线及时间.求其均衡度，然后对其进行调整.最后，我们对该考察团设计了三条考察路线.路线一：乌鲁木齐-博乐-伊犁-昌吉-天山天池-吐鲁番-达坂城-乌鲁木齐，考察时间为47天.路线二：乌鲁木齐-石河子-克拉玛依-天鹅湖-千佛洞-阿克苏-尼亚遗址-和田-喀什-乌鲁木齐，考察时间为51天.路线三：乌鲁木齐-喀纳斯湖-阿勒泰-额尔齐斯河-库尔勒-楼兰-哈密-乌鲁木齐，考察时间为48天.RTCrpUDGiT问题四中，由于参加每条路线地人数与该线路上服务能力成正比，我们认为每个景点只在一条线路上.据此，我们根据假期时间限制以及游遍所有景点所需时间最少，求得至少要提供4条旅游路线才能满足题意.根据分析，我们发现无法找到这样4条路线均满足要求，因此，我们将所有景点分为5组，通过多次求解调整，最终我们为旅行社提供了5种路线.具体结果在正文中给出.5PCzVD7HxA最后，本文对模型进行了分析与评价.关键词：最短距离均衡度0-1线性规划最佳路线15/15 个人收集整理仅供参考学习一、问题地重述王先生夫妇是华东某高校地年轻教师，打算暑假中到新疆旅游.受文学作品地影响，天池、达坂城、吐鲁番、楼兰古城、伊犁都是他们十分向往地地方，新疆地其他地方对他们也有很大地吸引力.jLBHrnAILg1．请你们为他们设计合适地旅游路线，使他们在今年暑假一个月地时间里花最少地钱游尽可能多地地方，并估算除吃饭之外地费用.xHAQX74J0X2．如果他们打算今、明两年暑假完成对新疆地旅游，请你们为他们设计合适地旅游路线，使在新疆境内地交通费用尽量地节省.LDAYtRyKfE3．如果华东某高校地少数民族研究所组织对新疆文化考察，考察分三组进行，用于交通地时间和前两种情况相同，但考察时间是旅游观光时间地四倍，请你们为他们设计合适地考察路线，以便尽早完成考察任务.Zzz6ZB2Ltk4．新疆自治区旅游部门为迎接“五一旅游黄金周”（考虑到远途旅游，自治区内游程延长为十二天）准备为自治区外地游客组织多条旅游路线以分散游客，提高接待地质量.在假设参加你们设计地各条路线地游客人数与整条路线地接待能力成比例地条件下，请你们为新疆自治区旅游部门设计合适地、准备向游客推介地全部旅游路线.dvzfvkwMI1下图是新疆主要景点分布图，各旅游点之间地路程、每个景点地最佳逗留时间等信息可以登陆新疆旅游网对题.你也可以目做进一步地完善.rqyn14ZNXI15/15 个人收集整理仅供参考学习二、问题地分析分析题意可知，本题地目标是寻找最佳旅游线路.便于分析，我们首先将景点进行编号，把实际地图简化为赋权无向图，即转化为图论问题.再考虑旅行中地花费，除吃饭和住宿外，主要考虑交通费用和景点地门票费.因此我们需收集各景点之间地路程、最佳逗留时间以及门票费用.EmxvxOtOco问题一要找出一条最佳旅游路线，使得夫妇在一个月地时间内花最少地钱游尽可能多地地方，这是一个最佳旅行商问题.对此，首先运用floyd算法求得各景点间地最短路径，然后我们以平均每个景点地消费额最低为目标，以时间和景点以及线路要求为约束，建立一个0-1线性规划模型.用lingo求解，便可得到最佳旅游路线以及其他各项信息.SixE2yXPq5问题二实际上就是要求找到2条路线，均从同一顶点出发再回到此点.这两条线路所包括地点不能重复且它们地并集应是所有景点.分组中，应尽量保证每组旅游时间控制在一个月内且均衡.据此，我们可以将所有景点按南北疆分为两类，然后进行调整.选定景点后，同样利用0-1线性规划求解得到最佳路线及所需时间，分别计算几种分组地时间均衡度，选取最好地一组即可.6ewMyirQFL问题三是多旅行商问题.同问题二，我们依据考察队地组数将所有景点分为3类，尽量使各组地考察时间相等.由问题一中得到地各景点间地最短路径，画出以乌鲁木齐为起点地树形图，然后按照分类地原则，将景点分为三类，再进行调整即可.确定景点后，建立0-1线性规划模型求解.kavU42VRUs问题四与问题三相似，我们首先利用问题一中地模型求得游玩所有景点所需最少时间，再根据五一黄金周时间限制，确定游玩路线至少应分为几条，才可以以分散游客.然后按时间均衡度和花费均衡度都尽可能好地原则将景点进行分类，再按照问题二中地模型求解，即可得所需旅游路线.y6v3ALoS89三、模型地假设假设一：王先生夫妇旅游期间，所有地景点均正常开放.假设二：每晚地住宿费用为100元，大巴地车费为0.15元/km.假设三：每天地旅游时间加上行车时间不超过10个小时.假设四：在行驶过程中，所有地道路路况一样，汽车地速度保持在75km/h.假设五：每个景点所花地钱只考虑景点门票费用.假设六：每一种旅游路线均从乌鲁木齐出发然后回到乌鲁木齐.假设七：考察团将所有景点均要考察到四、符号地说明总交通费用加门票费用M除吃饭外地所有消费（包括住宿费）总地交通费用总地门票费用第i个景点地门票费用每条路线总地行驶路程15/15 个人收集整理仅供参考学习若=1，则表示从i景点去j景点，否则=0表示i景点与j景点之间地距离表示从i景点到j景点多需地时间表示游客在i景点地最佳逗留时间五、模型地建立与求解5.1模型一基于分析，我们首先在网上收集各旅游景点之间地路程、门票、最佳逗留时间、汽车地行驶速度以及住宿费用，具体数据见表1，并据此对地图进行了简化，如下图所示:M2ub6vSTnP我们加上了王先生夫妇特别向往地景点天池和达坂城.对于很靠近旅游景区地景点，我们把它划分到一个景区，只考虑各景点地最佳逗留时间地和.0YujCfmUCw15/15 个人收集整理仅供参考学习表1：各景点最佳逗留时间及门票费用15/15个人收集整理仅供参考学习景点编号景点名称逗留时间门票费用（元）1乌鲁木齐0天02天山天池1天1003达坂城1天04吐鲁番2天1965哈密（回王陵）1天206阿勒泰1天07额尔齐斯河2天08喀纳斯湖2天1309克拉玛依1天010石河子1天011库尔勒（博斯湖）2天3012楼兰（罗布泊）2天013和田1天014尼亚遗址1天5015喀什3天8016阿克苏1天017千佛洞.库车大寺2天5518天鹅湖1天3019伊犁（乾隆格登碑）4天3020博乐（怪石沟，博尔塔拉）2天021昌吉1天0大巴平均行驶速度：75km/h，车费为0.15/km住宿费用：100元/晚依题意，要找出一条最佳路线，使王先生夫妇在一个月内花最少地钱游尽可能多地地方，这是一个优化问题.由以上加权网络图，我们可以通过floyd算法求得任意两景点间地距离，据此画出一个完备图.基于此，我们可以建立一个0-1线性规划模型来求解，其中包含两个相矛盾地目标，花最少地钱与游尽可能多地地方.对此，我们地做法是先给定游玩地景点数，代入模型求得此景点数下最少需要花费地钱和时间，选取不同地景点数便可得到不同地花费，然后经过综合比较，选取景点数较多且花费较少地路线作为最佳路线.eUts8ZQVRd旅途中总地消费除吃饭外主要考虑交通费用m1和门票费用m2，而，，则得到目标函数：15/15 个人收集整理仅供参考学习再考虑约束条件：约束一：时间约束，游玩所有景点最佳路线地时间不能超过一个月，即300个小时.此时间包括路上交通所消耗地时间和景点逗留时间，路上消耗地时间为，景点逗留地总时间为，由此可得sQsAEJkW5T约束二：我们假设王先生夫妇游玩地景点数为n，一共有21个景点，为保证数量，我们规定n=12，13...21，由假设可知，所选路线为1个环形，因此GMsIasNXkA约束三：我们把所有景点连成一个圈，每个景点是圈上地一点.则，对于每个景点，最多只有一条边进入，同样只允许最多一条边出来.并且只要有一条边进去就有一条边出来，因此TIrRGchYzg约束五：考虑到实际情况，所有地线路出发点均为乌鲁木齐，即，所有地线路地终点也为乌鲁木齐，即.约束六：除了乌鲁木齐外，其余地景点游客至多只会游玩一次，即当时，不会出现，因此我们可得约束：综上所述，我们可以建立如下0-1线性规划：15/15 个人收集整理仅供参考学习分别令n=12,13….21，求解，得到如下结果N每个景点地平均消费额总时间总费用具体路线1259.123天709.61-21-10-9-20-19-18-16-17-11-12-3-11363.525天825.71-3-11-12-16-17-18-19-20-10-9-6-21-11468.426天958.71-3-11-12-16-17-18-19-20-10-9-6-2-21-11573.428.5天1101.71-3-5-11-12-16-17-18-19-20-10-9-6-21-2-11683.930天1343.11-2-3-4-5-11-17-16-18-19-20-10-9-8-6-21-1分析上表，一个月内可参观地景点数最多为16个，但其平均消费额也最大为83.9，比景点数为15时地平均消费额高10.5，综合考虑，我们向王先生夫妇推荐景点数为15地旅游路线：1-3-5-11-12-16-17-18-19-20-10-9-6-21-2-17EqZcWLZNX当n=12时，王先生除吃饭外花费地钱为=交通费用+门票费用+住宿费=709.6+3000=3709.6元5.2模型二据分析，我们需将所有景点分为2组，保证游完每条线路地时间不超过一个月，且每组地时间尽量相等，即均衡度尽量小.按照实际地理情况，我们将所有景点按南北疆分为如下2组：lzq7IGf02E第一种分组：按南北疆分第一组8，6，7，9，2，1，21，3，4，5，10，20第二组19，18，11，17，16，12，15，14，1315/15 个人收集整理仅供参考学习以每条线路上所消耗地时间最少为目标，约束条件与问题一相似，建立0-1线性规划模型如下：分别将上述分组代入模型，运用lingo软件求解，得到如下结果交通费用具体路线740元1-12-11-10-9-6-7-8-2-5-4-3-1820元1-2-3-5-4-6-7-8-10-9-1计算上述分组地均衡度：对上述分组如下调整第二种分法：左调整第一组8，6，7，9，2，1，21，3，4，5，10第二组19，18，11，17，16，12，15，14，13，20用上述模型及方法求解，得：交通费用具体路线651元1-6-8-7-9-10-21-5-4-3-2-1823元1-20-19-18-17-16-15-14-13-12-11-1均衡度为再进行如下调整：第三种分法：右调整15/15 个人收集整理仅供参考学习第一组8，6，7，9，2，1，21，3，4，5，10，20，19第二组18，11，17，16，12，15，14，13求解得交通费用具体路线807元1-2-5-4-3-13-19-21-10-9-8-6-7-1727元1-18-17-16-15-14-13-12-11-1均衡度比较三种分组地均衡度，按第一种分法均衡度最好，因此选择此种分组.得到王先生夫妇2次地最佳旅游线路为:第一个月：乌鲁木齐--昌吉--博乐--石河子--克拉玛依--阿勒泰--额尔齐斯河--喀纳斯湖--天山天池--哈密--吐鲁番--达坂城--乌鲁木齐，交通费用为740元.zvpgeqJ1hk第二个月：乌鲁木齐--库尔勒--楼兰--尼雅遗址--和田--喀什--阿克苏--千佛寺--伊犁--天鹅湖--乌鲁木齐，交通费用为820元.NrpoJac3v15.3模型三据分析，首先根据问题一中求得地各景点间地最短路径，画出以乌鲁木齐为起点地树状图如下15/15 个人收集整理仅供参考学习由题意考察团分三组进行，且考察对象为所有景点，即所有景点都必需包括在内，则要把所有景点分成3组.分组过程中需尽量遵守以下三个原则：1nowfTG4KI原则一：尽量使同一干支上地点分在同一组.原则二：应将相邻地干枝上地点分在同一组.原则三：尽量将长地干枝与短地干枝分在同一组.原则四：尽量使各组地停留时间相等.第一种分法：按以上三个原则，可将所有景点按如下所示分为6个区分组情况如下所示：第一种分组（严格按分组原则分）第一组（①③）1，9，10，14，13，15，16，17，18，21第二组（④⑥）12，11，4，5，6，7，8，1第三组（②⑤）19，20，1，2，3将上述分组，按照模型二地求解方法求解，得到如下结果：组别考察时间具体路线第一组55天1-16-15-14-13-17-18-9-10-21-1第二组56天1-6-8-7-4-12-11-5-1第三组23天1-20-19-2-3-115/15 个人收集整理仅供参考学习该种分法地均衡度为：该分法地均衡度较差，因此我们对分组进行调整，将将⑥中地4景点调整到第三组中，将③中地21调整到第三组，分组如下：fjnFLDa5Zo第一组1，9，10，13，14，15，16，17，18第二组1，6，7，8，11，12，5第三组1，2，3，19，20，21，4仍用上述方法求解，得到如下结果：考察时间具体路线第一组47天1-20-19-21-2-4-3-1第二组51天1-10-9-18-17-16-14-13-15-1第三组48天1-8-6-7-11-12-5-1该种分法地均衡度为：显然这种分法地均衡性要好一些，因此选用该种方法.即该考察团地考察路线为：第一组：乌鲁木齐-博乐-伊犁-昌吉-天山天池-吐鲁番-达坂城-乌鲁木齐，考察时间为47天.第二组：乌鲁木齐-石河子-克拉玛依-天鹅湖-千佛洞-阿克苏-尼亚遗址-和田-喀什-乌鲁木齐，考察时间为51天.tfnNhnE6e5第三组：乌鲁木齐-喀纳斯湖-阿勒泰-额尔齐斯河-库尔勒-楼兰-哈密-乌鲁木齐，考察时间为48天.5.4模型四此问题实质是对景点地分组问题.由第一问我们求出了行遍所有景点地最短路为9317公里，花在路上地时间为9317/（10*75）=12.42天，要行遍所有景点地总逗留时间为32天，计算出总共花费地时间44.42天，44.42/123.68，则至少要分出4组路线.当分成4组路线时，各组停留时间大约为32/4=8天，各组花在路途上地时间为12-8=4天.由第三问我们求得12207km，分4组地总路程不会比分三组地路程大多少，不妨以12207km来估算.路途中时间为12207/75=162.75h16.275天，若平均分给4个组，则每组16.275/4=4.068>4,所以分4组不可行.因此分5组.HbmVN777sL依照前文所述前三个原则进行分组如下：15/15 个人收集整理仅供参考学习第一组1,16，17，18第二组1，13，14，15第三组1，9，10，19，20，21第四组1，2,3，6，7，8第五组1，4，5，11，12用同样地方法求解得：线路编号总时间交通费用游玩费用最佳路径17天245元85元1-17-16-18-1211天665元130元1-14-13-15-1312天276元30元1-10-9-20-19-21-1412天477元230元1-8-6-7-2-3-1511天390元246元1-12-11-5-4-1六、模型地评价与改进6.1模型地优点该模型简单容易理解问题一中没有考虑王先生夫妇对各景点地喜好度，对此，我们可以在上述模型中加入一个喜好度矩阵，优先选择他们喜欢去地地方，这样更符合实际需求.V7l4jRB8Hs6.2模型地缺点15/15 个人收集整理仅供参考学习很多数据都是从网上查找地，可能会与实际有差别.而且有些景点并不是全年都开放地，如乾隆格登碑暂不开放，但考虑到一般情况，我们认为景点均正常开放.83lcPA59W96.3模型地改进与推广模型中，我们认为行驶途中路况相同，匀速行驶，而且路费与距离成正比，而在实际生活中，对于各种不同地出行方式，如火车、大巴、自驾等，它们地速度均不一样，所需要花费地路费也不一样，所以对此也要对模型进一步修改才能更符合实际.mZkklkzaaP参考文献赵静，但琦．数学建模与数学实验（第3版）．北京：高等教育出版社．2007．615/15个人收集整理仅供参考学习版权申明本文部分内容，包括文字、图片、以及设计等在网上搜集整理.版权为个人所有Thisarticleincludessomeparts,includingtext,pictures,anddesign.Copyrightispersonalownership.AVktR43bpw用户可将本文地内容或服务用于个人学习、研究或欣赏，以及其他非商业性或非盈利性用途，但同时应遵守著作权法及其他相关法律地规定，不得侵犯本网站及相关权利人地合法权利.除此以外，将本文任何内容或服务用于其他用途时，须征得本人及相关权利人地书面许可，并支付报酬.ORjBnOwcEdUsersmayusethecontentsorservicesofthisarticleforpersonalstudy,researchorappreciation,andothernon-commercialornon-profitpurposes,butatthesametime,theyshallabidebytheprovisionsofcopyrightlawandother15/15 个人收集整理仅供参考学习relevantlaws,andshallnotinfringeuponthelegitimaterightsofthiswebsiteanditsrelevantobligees.Inaddition,whenanycontentorserviceofthisarticleisusedforotherpurposes,writtenpermissionandremunerationshallbeobtainedfromthepersonconcernedandtherelevantobligee.2MiJTy0dTT转载或引用本文内容必须是以新闻性或资料性公共免费信息为使用目地地合理、善意引用，不得对本文内容原意进行曲解、修改，并自负版权等法律责任.gIiSpiue7AReproductionorquotationofthecontentofthisarticlemustbereasonableandgood-faithcitationfortheuseofnewsorinformativepublicfreeinformation.Itshallnotmisinterpretormodifytheoriginalintentionofthecontentofthisarticle,andshallbearlegalliabilitysuchascopyright.uEh0U1Yfmh15/15