2022年最佳旅游路线设计实用 .pdf

最佳旅游路线设计摘要本文主要研究的是如何选择最佳线路的问题。对于线路的选择， 我们主要考虑旅行中的费用及旅行时间。 我们首先通过网络查找得到各景点（包括景区） 之间的距离， 门票费用以及最佳逗留时间，据此将景点图简化成赋权无向图。然后利用 floyd 算法得到每 2 个景点间的最短路径。 据此，根据题目要求分别建立0-1线性规划模型。问题一给定了时间约束， 要求花最少的钱游尽可能多的地方。据此，我们以花费最少为目标， 以时间限制及线路要求为约束，建立 0-1 规划模型，利用 lingo软件对模型求解。对结果进行综合分析，最后我们向王先生夫妇推荐景点数为16 的路线：乌鲁木齐 -达坂城 -哈密-库尔勒 -楼兰 -阿克苏 -千佛洞-天鹅湖 -伊犁-博乐-石河子 -克拉玛依 -阿勒泰 -昌吉-天山天池 -乌鲁木齐。平均每个景点花费为73.4元，除了吃饭以外，这对夫妇总共花费估计为4102 元。问题二要提出 2 条路线游完所有景点， 据此，我们首先将所有景点按南北疆分为 2 组。这两条路线要求交通费用最少，即总路程最少， 我们以总行驶路程为目标，以相应的条件为约束，建立0-1 线性规划模型。利用lingo 求解得到每组路线所需最短时间， 并求得其均衡度。 然后对其进行调整， 找到均衡度最好的一种分组。我们为王先生夫妇推荐的第一个月的路线为：乌鲁木齐 -昌吉-博乐-石河子-克拉玛依 -阿勒泰 -额尔齐斯河 -喀纳斯湖 -天山天池 -哈密 -吐鲁番 -达坂城 -乌鲁木齐，交通费用为 740元。第二个月的路线为乌鲁木齐-库尔勒 -楼兰-尼雅遗址-和田-喀什-阿克苏 -千佛寺 -伊犁-天鹅湖 -乌鲁木齐，交通费用为820 元。问题三与问题二相似， 我们根据各景点之间的最短路径画出以乌鲁木齐为树根的树形图， 然后按分类原则分为三组。 将模型二中的目标函数换为考察时间最小得到模型三，分别用lingo 求解得到每组最佳路线及时间。求其均衡度，然后对其进行调整。最后，我们对该考察团设计了三条考察路线。路线一：乌鲁木齐-博乐-伊犁-昌吉-天山天池 -吐鲁番-达坂城 -乌鲁木齐，考察时间为47 天。路线二： 乌鲁木齐 -石河子 -克拉玛依 -天鹅湖 -千佛洞-阿克苏 -尼亚遗址 -和田-喀什-乌鲁木齐，考察时间为51 天。 路线三：乌鲁木齐 -喀纳斯湖 -阿勒泰 -额尔齐斯河 -库尔勒-楼兰-哈密-乌鲁木齐，考察时间为48 天。问题四中，由于参加每条路线的人数与该线路上服务能力成正比，我们认为每个景点只在一条线路上。 据此，我们根据假期时间限制以及游遍所有景点所需时间最少， 求得至少要提供 4 条旅游路线才能满足题意。 根据分析， 我们发现无法找到这样 4 条路线均满足要求， 因此，我们将所有景点分为5 组，通过多次求解调整，最终我们为旅行社提供了5 种路线。具体结果在正文中给出。最后，本文对模型进行了分析与评价。关键词最短距离均衡度 0-1 线性规划最佳路线名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 13 页 - - - - - - - - - 一、问题的重述王先生夫妇是华东某高校的年轻教师，打算暑假中到新疆旅游。 受文学作品的影响，天池、达坂城、吐鲁番、楼兰古城、伊犁都是他们十分向往的地方，新疆的其他地方对他们也有很大的吸引力。1请你们为他们设计合适的旅游路线，使他们在今年暑假一个月的时间里花最少的钱游尽可能多的地方，并估算除吃饭之外的费用。2如果他们打算今、明两年暑假完成对新疆的旅游，请你们为他们设计合适的旅游路线，使在新疆境内的交通费用尽量地节省。3如果华东某高校的少数民族研究所组织对新疆文化考察，考察分三组进行，用于交通的时间和前两种情况相同，但考察时间是旅游观光时间的四倍，请你们为他们设计合适的考察路线，以便尽早完成考察任务。4新疆自治区旅游部门为迎接“五一旅游黄金周” （考虑到远途旅游，自治区内游程延长为十二天）准备为自治区外的游客组织多条旅游路线以分散游客，提高接待的质量。在假设参加你们设计的各条路线的游客人数与整条路线的接待能力成比例的条件下， 请你们为新疆自治区旅游部门设计合适的、准备向游客推介的全部旅游路线。下图是新疆主要景点分布图， 各旅游点之间的路程、 每个景点的最佳逗留时间等信息可以登陆新疆旅游网对题。你也可以目做进一步的完善。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 13 页 - - - - - - - - - 二、问题的分析分析题意可知，本题的目标是寻找最佳旅游线路。便于分析，我们首先将景点进行编号， 把实际地图简化为赋权无向图，即转化为图论问题。 再考虑旅行中的花费，除吃饭和住宿外， 主要考虑交通费用和景点的门票费。因此我们需收集各景点之间的路程、最佳逗留时间以及门票费用。问题一要找出一条最佳旅游路线， 使得夫妇在一个月的时间内花最少的钱游尽可能多的地方，这是一个最佳旅行商问题。对此，首先运用floyd 算法求得各景点间的最短路径， 然后我们以平均每个景点的消费额最低为目标，以时间和景点以及线路要求为约束，建立一个0-1 线性规划模型。用lingo 求解，便可得到最佳旅游路线以及其他各项信息。问题二实际上就是要求找到2 条路线，均从同一顶点出发再回到此点。 这两条线路所包括的点不能重复且它们的并集应是所有景点。分组中，应尽量保证每组旅游时间控制在一个月内且均衡。据此，我们可以将所有景点按南北疆分为两类，然后进行调整。选定景点后，同样利用0-1 线性规划求解得到最佳路线及所需时间，分别计算几种分组的时间均衡度，选取最好的一组即可。问题三是多旅行商问题。 同问题二，我们依据考察队的组数将所有景点分为3 类，尽量使各组的考察时间相等。由问题一中得到的各景点间的最短路径，画出以乌鲁木齐为起点的树形图，然后按照分类的原则， 将景点分为三类， 再进行调整即可。确定景点后，建立0-1 线性规划模型求解。问题四与问题三相似， 我们首先利用问题一中的模型求得游玩所有景点所需最少时间， 再根据五一黄金周时间限制，确定游玩路线至少应分为几条，才可以以分散游客。然后按时间均衡度和花费均衡度都尽可能好的原则将景点进行分类，再按照问题二中的模型求解，即可得所需旅游路线。三、模型的假设假设一：王先生夫妇旅游期间，所有的景点均正常开放。假设二：每晚的住宿费用为100 元，大巴的车费为0.15 元/km。假设三：每天的旅游时间加上行车时间不超过10 个小时。假设四：在行驶过程中，所有的道路路况一样，汽车的速度保持在75km/h。假设五：每个景点所花的钱只考虑景点门票费用。假设六：每一种旅游路线均从乌鲁木齐出发然后回到乌鲁木齐。假设七：考察团将所有景点均要考察到四、符号的说明m总交通费用加门票费用M 除吃饭外的所有消费（包括住宿费）1m总的交通费用2m总的门票费用ic第 i 个景点的门票费用w每条路线总的行驶路程名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 13 页 - - - - - - - - - ijc若ijx =1，则表示从 i 景点去 j 景点，否则ijx =0 ijr表示 i 景点与 j 景点之间的距离ijt表示从 i 景点到 j 景点多需的时间it表示游客在 i 景点的最佳逗留时间五、模型的建立与求解问题一基于分析，我们首先在网上收集各旅游景点之间的路程、门票、最佳逗留时间、汽车的行驶速度以及住宿费用， 具体数据见表 1，并据此对地图进行了简化，如下图所示 : 8哈纳斯湖6阿勒泰5哈密4吐鲁番3达坂城1乌鲁木齐21昌吉10石河子20博乐19伊犁18天鹅湖11库尔勒12楼兰17千佛洞16 阿克苏15喀什14 尼雅遗址13和田7额尔齐斯河2天山天池9克拉玛依14341011010066231131135053513034376704373942272434271093868297231199600著名景点之间的连线图我们加上了王先生夫妇特别向往的景点天池和达坂城。对于很靠近旅游景区的景点，我们把它划分到一个景区，只考虑各景点的最佳逗留时间的和。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 13 页 - - - - - - - - - 表 1：各景点最佳逗留时间及门票费用景点编号景点名称逗留时间门票费用（元）1 乌鲁木齐0 天0 2 天山天池1 天100 3 达坂城1 天0 4 吐鲁番2 天196 5 哈密（回王陵）1 天20 6 阿勒泰1 天0 7 额尔齐斯河2 天0 8 喀纳斯湖2 天130 9 克拉玛依1 天0 10 石河子1 天0 11 库尔勒（博斯湖）2 天30 12 楼兰（罗布泊）2 天0 13 和田1 天0 14 尼亚遗址1 天50 15 喀什3 天80 16 阿克苏1 天0 17 千佛洞。库车大寺2 天55 18 天鹅湖1 天30 19 伊犁（乾隆格登碑）4 天30 20 博乐（怪石沟，博尔塔拉）2 天0 21 昌吉1 天0 大巴平均行驶速度： 75km/h，车费为 0.15/km 住宿费用： 100元/晚依题意，要找出一条最佳路线， 使王先生夫妇在一个月内花最少的钱游尽可能多的地方，这是一个优化问题。由以上加权网络图，我们可以通过floyd 算法求得任意两景点间的距离，据此画出一个完备图。基于此，我们可以建立一个0-1 线性规划模型来求解，其中包含两个相矛盾的目标，花最少的钱与游尽可能多的地方。 对此，我们的做法是先给定游玩的景点数，代入模型求得此景点数下最少需要花费的钱和时间， 选取不同的景点数便可得到不同的花费，然后经过综合比较，选取景点数较多且花费较少的路线作为最佳路线。旅途中总的消费除吃饭外主要考虑交通费用m1 和门票费用m2，而2121111ijijijmrc，212111122ijijijmrcc，则得到目标函数：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 13 页 - - - - - - - - - 21212121111112ijijijijijijmrcrcc再考虑约束条件：约束一：时间约束，游玩所有景点最佳路线的时间不能超过一个月，即300个小时。此时间包括路上交通所消耗的时间和景点逗留时间，路上消耗的时间为212111ijijijrt ，景点逗留的总时间为21211112ijijijrtt，由此可得21212121111113002ijijijijijijrtrtt约束二：我们假设王先生夫妇游玩的景点数为n，一共有 21 个景点，为保证数量，我们规定n=12，13。 。 。21，由假设可知，所选路线为1 个环形，因此212111,12,13.,21ijijrn n约束三：我们把所有景点连成一个圈，每个景点是圈上的一点。则，对于每个景点，最多只有一条边进入， 同样只允许最多一条边出来。并且只要有一条边进去就有一条边出来，因此1, ,1,2,.,21ijijijrri j约束五：考虑到实际情况，所有的线路出发点均为乌鲁木齐，即11iijr，所有的线路的终点也为乌鲁木齐，即11jijr。约束六：除了乌鲁木齐外，其余的景点游客至多只会游玩一次，即当,2, 3,.,21i j时，不会出现1jiijrr，因此我们可得约束：0, ,2,3,.,21ijjirri j综上所述，我们可以建立如下0-1 线性规划：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 13 页 - - - - - - - - - 212121211111212121211111212111111min213002,12,13.,21.1, ,1,2,.,211,10, ,2,3,.ijijijijijijijijijijijijijijijijijijijijijjimrcrccrtrttrn nstrri jrrrri j,21分别令 n=12,13.21，求解，得到如下结果N 每个 景点的平 均消费额总时间总费用具体路线12 59.1 23 天709.6 1-21-10-9-20-19-18-16-17-11-12-3-1 13 63.5 25 天825.7 1-3-11-12-16-17-18-19-20-10-9-6-21-1 14 68.4 26 天958.7 1-3-11-12-16-17-18-19-20-10-9-6-2-21-1 15 73.4 28.5 天1101.7 1-3-5-11-12-16-17-18-19-20-10-9-6-21-2-1 16 83.9 30 天1343.1 1-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-1 当 n=12 时，王先生除吃饭外花费的钱为=交通费用 +门票费用 +住宿费 =709.6+3000=3709.6元问题二：据分析，我们需将所有景点分为2 组，保证游完每条线路的时间不超过一个月，且每组的时间尽量相等，即均衡度尽量小。按照实际地理情况，我们将所有景点按南北疆分为如下2 组：第一种分组：按南北疆分第一组8，6，7，9，2，1，21，3，4，5，10，20 第二组19，18，11，17，16，12，15，14，13 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 13 页 - - - - - - - - - 以每条线路上所消耗的时间最少为目标，约束条件与问题一相似，建立0-1线性规划模型如下：2121112121212111111111min13002.1, ,1,2,.,211,10, ,2,3,.,21nijijijijijijijijijnnijijijijijijijijijjimrcrtrttrnstrri jrrrri j，将所选景点重新编号为 1.n其中 的取值按所分组中景点个数确定分别将上述分组代入模型，运用lingo 软件求解，得到如下结果交通费用具体路线740元1-12-11-10-9-6-7-8-2-5-4-3-1 820元1-2-3-5-4-6-7-8-10-9-1 计算上述分组的均衡度：|(1)(2) |19.7%max( )www i对上述分组如下调整第二种分法：左调整第一组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-1 823元1-20-19-18-17-16-15-14-13-12-11-1 均衡度为|(1)(2) |220.9%max( )www i再进行如下调整：第三种分法：右调整第一组8，6，7，9，2，1，21，3，4，5，10，20，19 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 13 页 - - - - - - - - - 第二组18，11，17，16，12，15，14，13 求解得交通费用具体路线807元1-2-5-4-3-13-19-21-10-9-8-6-7-1 727元1-18-17-16-15-14-13-12-11-1 均衡度|(1)(2) |39.9%max( )www i比较三种分组的均衡度，按第一种分法均衡度最好，因此选择此种分组。得到王先生夫妇 2 次的最佳旅游线路为 : 第一个月：乌鲁木齐 -昌吉-博乐-石河子 -克拉玛依 -阿勒泰 -额尔齐斯河 -喀纳斯湖 -天山天池 -哈密-吐鲁番 -达坂城 -乌鲁木齐，交通费用为740 元。第二个月：乌鲁木齐 -库尔勒-楼兰-尼雅遗址 -和田-喀什 -阿克苏 -千佛寺-伊犁-天鹅湖 -乌鲁木齐，交通费用为820 元。问题三：据分析，首先根据问题一中求得的各景点间的最短路径，画出以乌鲁木齐为起点的树状图如下1乌鲁木齐3达坂城2天山天池21昌吉10石河子6阿勒泰8喀纳斯湖7额尔齐斯河9克拉玛依20博乐19伊犁18天鹅湖17千佛洞16阿克苏15喀什13和田4吐鲁番5哈密12楼兰11库尔勒各景点到乌鲁木齐的最短路径图4375354272432272972312546626867011080143410394350由题意考察团分三组进行， 且考察对象为所有景点， 即所有景点都必需包括名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 13 页 - - - - - - - - - 在内，则要把所有景点分成3 组。分组过程中需尽量遵守以下三个原则：原则一：尽量使同一干支上的点分在同一组。原则二：应将相邻的干枝上的点分在同一组。原则三：尽量将长的干枝与短的干枝分在同一组。原则四：尽量使各组的停留时间相等。第一种分法：按以上三个原则，可将所有景点按如下所示分为6 个区1乌鲁木齐3达坂城2天山天池21昌吉10石河子6阿勒泰8喀纳斯湖7额尔齐斯河9克拉玛依20博乐19伊犁18天鹅湖17千佛洞16阿克苏15喀什13和田4吐鲁番5哈密12楼兰11库尔勒各景点到乌鲁木齐的最短路径图43753542724322729723125466268670110801434103943501区2区3区4区5区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-1 该种分法的均衡度为：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 13 页 - - - - - - - - - 31max |( )( )|58.9%max( )w iw jw i该分法的均衡度较差， 因此我们对分组进行调整， 将将中的 4 景点调整到第三组中，将中的21 调整到第三组，分组如下：第一组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 该种分法的均衡度为：32max |( )( )|7.8%max( )w iw jw i显然这种分法的均衡性要好一些，因此选用该种方法。即该考察团的考察路线为：第一组：乌鲁木齐 -博乐-伊犁-昌吉-天山天池 -吐鲁番 -达坂城 -乌鲁木齐，考察时间为 47 天。第二组：乌鲁木齐 -石河子 -克拉玛依 -天鹅湖 -千佛洞 -阿克苏 -尼亚遗址 -和田-喀什-乌鲁木齐，考察时间为51 天。第三组：乌鲁木齐 -喀纳斯湖 -阿勒泰 -额尔齐斯河 -库尔勒 -楼兰-哈密-乌鲁木齐 ，考察时间为 48 天。问题四：此问题实质是对景点的分组问题。由第一问我们求出了行遍所有景点的最短路为 9317 公里，花在路上的时间为9317/（10*75）=12.42天，要行遍所有景点的总逗留时间为32 天，计算出总共花费的时间44.42 天，44.42/12 3.68，则至少要分出 4 组路线。当分成 4 组路线时，各组停留时间大约为32/4=8 天，各组花在路途上的时间为12-8=4 天。由第三问我们求得12207km，分 4 组的总路程不 会 比 分三 组的 路 程 大 多 少， 不 妨 以 12207km 来 估 算 。 路 途 中时 间 为12207/75=162.75h 16.275 天，若平均分给4 个组，则每组 16.275/4=4.0684, 所以分 4 组不可行。因此分5 组. 依照前文所述前三个原则进行分组如下：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 13 页 - - - - - - - - - 1乌鲁木齐3达坂城2天山天池21昌吉10石河子6阿勒泰8喀纳斯湖7额尔齐斯河9克拉玛依20博乐19伊犁18天鹅湖17千佛洞16阿克苏15喀什13和田4吐鲁番5哈密12楼兰11库尔勒各景点到乌鲁木齐的最短路径图43753542724322729723125466268670110801434103943501区2区3区4区5区6区第一组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 用同样的方法求解得：线路编号总时间交通费用游玩费用最佳路径1 7 天245元85 元1-17-16-18-1 2 11天665元130 元1-14-13-15-1 3 12天276元30 元1-10-9-20-19-21-1 4 12天477元230 元1-8-6-7-2-3-1 5 11天390元246 元1-12-11-5-4-1 六、模型的分析该模型简单容易理解问题一中没有考虑王先生夫妇对各景点的喜好度，对此，我们可以在上述模型中加入一个喜好度矩阵，优先选择他们喜欢去的地方，这样更符合实际需求。很多数据都是从网上查找的， 可能会与实际有差别。 而且有些景点并不是全年都开放的， 如乾隆格登碑暂不开放， 但考虑到一般情况， 我们认为景点均正常开放。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 13 页 - - - - - - - - - 模型中，我们认为行驶途中路况相同，匀速行驶，而且路费与距离成正比，而在实际生活中，对于各种不同的出行方式，如火车、大巴、自驾等，它们的速度均不一样， 所需要花费的路费也不一样， 所以对此也要对模型进一步修改才能更符合实际。参考文献赵静，但琦数学建模与数学实验（第3 版） 北京：高等教育出版社 20076 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 13 页 - - - - - - - - -