《最佳旅游路线设计》由会员分享，可在线阅读，更多相关《最佳旅游路线设计（12页珍藏版）》请在金锄头文库上搜索。
1、姓名：李忻玮 学号：07111044 题目：D1最佳旅游路线设计摘要本论文主要考虑通过合理的假设将问题简化为图论问题，使用 floyed 算法得到任意两点间的最短路径后，带入各景点间的距离、时间、门票等信息后，视为 0-1 线性规划模型用 lingo 进行求解。问题一给出了一个月的时间要求，同时需要考虑到最少的花费和前往最多的景点两个规划目标，是一个 0-1 多目标的线性规划问题。我们通过将其中一个规划目标：“最多的景点”划入约束条件，将多目标问题变成“在前往N（N=12)个景点的条件下，最少花费”的 0-1 线性单目标规划问题。使用lingo 后求出结果如下：乌鲁木齐哈密库尔勒楼兰阿克苏千佛
2、洞天鹅湖伊犁石河子博乐克拉玛依阿勒泰天池乌鲁木齐。问题二要求用两年暑假游遍新疆的所有假期，即使用两个除乌鲁木齐外不想交的圈遍历全图，并使两条线路的总费用最小。显然可得，将所有的顶点以乌鲁木齐为界划分出南北两块，每个区块使用一个圈进行遍历将能节省费用。我们以行驶路程为规划目标，用相应的约束条件建立 0-1 线性规划模型，使用lingo 求解两个区块的的最佳旅行路线。再分析均衡度后调整区块的分布，以求得最佳均衡度的分组。求解得最佳路线规划如下： 问题三与问题二的解答方法相同，根据各景点之间的最短路径画出以乌鲁木齐为根的树形图，然后将地理上在一个区域的景点分为三块。将模型二中的目标函数替换为考察时间
3、最小后，可使用 lingo 计算出每组的最佳路线，在参考均衡度对分组进行调整后可得到近似的最佳分组和每组的最佳路线。结果如下：问题四中，通过合理假设，我们认为每个景点只应该出现在一条线路上。据此，我们根据假期时间限制以及游遍所有景点所需时间最少，求得至少要提供 4 条旅游路线才能满足题意。根据分析，我们发现无法找到这样 4 条路线均满足要求，因此，我们将所有景点分为 5 组，通过多次求解调整，最终我们为旅行社提供了 5 种路线。具体结果在正文中给出。最后，本文对模型进行了分析与评价。关键词最短距离 均衡度 0-1 线性规划 最佳路线一、问题的重述王先生夫妇是华东某高校的年轻教师，打算暑假中到新
4、疆旅游。受文学作品的影响，天池、达坂城、吐鲁番、楼兰古城、伊犁都是他们十分向往的地方，新疆的其他地方对他们也有很大的吸引力。1请你们为他们设计合适的旅游路线，使他们在今年暑假一个月的时间里花最少的钱游尽可能多的地方，并估算除吃饭之外的费用。姓名：李忻玮 学号：07111044 题目：D22如果他们打算今、明两年暑假完成对新疆的旅游，请你们为他们设计合适的旅游路线，使在新疆境内的交通费用尽量地节省。3如果华东某高校的少数民族研究所组织对新疆文化考察，考察分三组进行，用于交通的时间和前两种情况相同，但考察时间是旅游观光时间的四倍，请你们为他们设计合适的考察路线，以便尽早完成考察任务。4新疆自治区旅
5、游部门为迎接“五一旅游黄金周” （考虑到远途旅游，自治区内游程延长为十二天）准备为自治区外的游客组织多条旅游路线以分散游客，提高接待的质量。在假设参加你们设计的各条路线的游客人数与整条路线的接待能力成比例的条件下，请你们为新疆自治区旅游部门设计合适的、准备向游客推介的全部旅游路线。下图是新疆主要景点分布图，各旅游点之间的路程、每个景点的最佳逗留时间等信息可以登陆新疆旅游网对题。你也可以目做进一步的完善。二、问题的分析由简单的分析可以得出，问题的实质都是要求得出一条满足某一约束条件的旅游路线。我们将景区进行编号，并通过网络查找到各个景点之间的距离，我们就可以将实际地图简化为赋权无向图，所以问题就
6、变成了图论问题。另外我们还需补充路费、最佳逗留时间以及门票费用等其他信息。问题一的目标是找到一条能在一个月内实现的最佳旅游路线，要求花费最少，姓名：李忻玮 学号：07111044 题目：D3景点最多，这是一个多目标线性规划问题。我们可以使用 floyd 算法求得各个顶点（景区）之间的最短路径，然后我们以花费最少为规划目标，将“景点最多”这一目标放入限制条件中，要求走过的景点数为 N（N=12) 。然后再建立时间、景点路线为要求的约束条件，将多目标规划问题转变成单目标 0-1 规划问题。使用 lingo 求解可得最佳旅游路线。问题二需要两条旅游线路，这两条旅游线路可以覆盖新疆的全部景点。同时这两
7、条线路都从乌鲁木齐出发再回到乌鲁木齐，彼此之间无重复的景点，这两组线路所需时间都在一月之内。我们很容易想到，将全部的景点以乌鲁木齐为界分为南北两组比较容易求出满足要求的路线。我们将景点进行分组，并计算均衡度后利用 0-1 规划求解得到的最佳路线及所需时间，再根据均衡度进行调整，选取均衡度最佳的一组。问题三是多旅行商问题。解法同问题二，我们将所有景点分为 3 组，使各组的考察时间尽量相等。由问题一中已经画出的各景点间的最短路径，求出以乌鲁木齐为起点的树，然后按照分类的原则，将景点分为三类，再进行调整即可。确定景点的分组后，同样使用问题二中建立的 0-1 线性规划模型求解，只需将目标函数换成考察天
8、数最小即可。问题四与问题三相似，我们首先利用问题一中 N=21 及游遍所有景点所需的最小花费和时间，再根据五一黄金周时间限制，确定游玩路线至少应分为几条，才可以最大程度上分散景区压力。然后按时间均衡度和花费均衡度都尽可能好的原则将景点进行分类，再按照问题二中的模型求解，即可得所需旅游路线。三、模型的假设1.所有景点都正常开放，开放时间没有区别。2.交通路线全部正常，交通工具匀速。3.景点的花销仅限于门票支出。4.住宿费用和交通费用在所有景区都是一样的。5.景区的先后到达不会有区别（考察和旅游时） 。6.王夫妇对于的景点喜爱程度是一样的。四、符号的说明总交通费用加门票费用mM 除吃饭外的所有消费
9、（包括住宿费）总的交通费用1总的门票费用2第 i 个景点的门票费用ic每条路线总的行驶路程w若 =1，则表示从 i 景点去 j 景点，否则 =0ijij ijc表示 i 景点与 j 景点之间的距离ijr姓名：李忻玮 学号：07111044 题目：D4表示从 i 景点到 j 景点多需的时间ijt表示游客在 i 景点的最佳逗留时间i五、模型的建立与求解问题一基于分析，我们首先在网上收集各旅游景点之间的路程、门票、最佳逗留时间、汽车的行驶速度以及住宿费用，具体数据见表 1，并据此对地图进行了简化，如下图所示:8 哈 纳 斯 湖6 阿 勒 泰5 哈 密4 吐 鲁 番3 达 坂 城1 乌 鲁 木 齐1
10、0 石 河 子2 0 博 乐1 9 伊 犁1 8 天 鹅 湖1 1 库 尔 勒1 2 楼 兰1 7 千 佛 洞1 6 阿 克 苏1 5 喀 什 1 4 尼 雅 遗 址1 3 和 田7 额 尔 齐 斯 河2 天 山 天 池9 克 拉 玛 依1843 8 81101007531152345363323593505161 0 0 04 7 44 1 83 7 02 7 43 1 04 6 61 0 93 82 7 43 7 12 3 53 8 74 6 6著 名 景 点 之 间 的 连 线 图421630火 焰 山回 王 陵博 斯 腾 湖357405180昭 苏 边 境 的 乾 隆 格 登 碑博 尔
11、 塔 拉怪 石 沟库 车 大 寺苏 丹 . 沙 图 克 麻 扎香 妃 墓艾 提 尕 尔 清 真 寺阿 图 什我们加上了王先生夫妇特别向往的景点天池和达坂城。对于很靠近旅游景区的景点，我们把它划分到一个景区，只考虑各景点的最佳逗留时间的和。表 1：各景点最佳逗留时间及门票费用景点编号 景点名称 逗留时间 门票（元）姓名：李忻玮 学号：07111044 题目：D51 乌鲁木齐（昌吉、达坂城） 96h 02 天池 48h 1003 吐鲁番（火焰山） 72h 604 哈密（回王陵） 48h 405 库尔勒（博斯腾湖） 48h 306 石河子 24h 07 克拉玛依 24h 08 阿勒泰 24h 09
12、喀纳斯湖 24h 23010 额尔齐斯河 24h 011 伊犁（昭苏边境的乾隆格登碑） 72h 3012 博乐（博尔塔拉，怪石沟） 72h 6013 天鹅湖 24h 9814 千佛洞（库车大寺） 48h 12515 阿克苏 24h 016 喀什（阿图什、苏丹.沙图克麻扎、香妃墓、艾提尕清真寺）72h 5017 和田 24h 018 尼亚遗址 24h 5019 楼兰（罗布泊） 72h 0大巴平均行驶速度：85km/h，车费为 0.4/km住宿费用：100 元/晚我们需要根据以上数据规划出一条路线让王先生夫妇能够在一个月内用最少的花费走过最多的景点，这是一个典型的优化问题。从上面的加权图中我明年可
13、以使用 FLOYD 算法求出任意两个景点之间的最短路径，然后将其做成一个完备图。由于该 0-1 规划中存在两个目标，即花费最少和最多的景点，我们可以将景点数设置为一定的情况下单独考虑花费最少这一目标函数，将多目标规划变为单目标规划。然后不断改变设定的景点数，就不同景点数情况下的花费经过综合对比求出最佳路线。旅途中总的消费除吃饭外主要考虑交通费用 m1 和门票费用 m221ijimrc21ijiji则得到目标函数： 2121iji ijijij imrcrc约束条件如下：姓名：李忻玮 学号：07111044 题目：D6约束 1：时间约束，游玩所有景点最佳路线的时间不能超过一个月，即 300个小时
14、。此时间包括路上交通所消耗的时间和景点逗留时间，路上消耗的时间为 ，景点逗留的总时间为 ，由此可得21ijict21ijijict212130ij ijiji ictt约束 2：我们假设王先生夫妇游玩的景点数为 n，一共有 21 个景点，为保证数量，我们规定 n=12， 13。 。 。19，由假设可知，所选路线为 1 个环形，因此21,12,3.9ijic约束 3：所有经过的景点相连成为一个圈。则，对于每个景点，最多只有一条边进入，同样只允许最多一条边出来。并且只要有一条边进去就有一条边出来，因此 1,2.19ijjkcij约束 4：所有的线路出发点终点均为乌鲁木齐，即 ， 。1ic1jjc约
15、束 5：除了乌鲁木齐外，其余的景点游客至多只会经过一次，即当时，不会出现 ，因此我们可得约束：,23,.1ij1jiijc0,2,3.19ijij综上所述，我们可以建立如下 0-1 线性规划：21212121111min30,3.9. 2,1,0,3.ij ijiji iij ijiji iijiijijijijijirccttcnstc9分别令 n=10,11.19，求解，得到如下结果景点数 日均消费（元） 总时间 总费用（元） 具体路线10 96.2 22 天 2115.4 1-6-7-12-11-13-15-14-5-19-1姓名：李忻玮 学号：07111044 题目：D711 97.5
16、 23 天 2241.8 1-5-19-15-14-13-11-12-6-7-8-112 93.7 25 天 2341.8 1-5-19-15-14-13-11-12-6-7-8-2-113 81.3 27 天 2916.2 1-4-5-19-15-14-13-11-6-12-7-8-2-114 101.5 30 天 3044.6 1-2-3-4-5-14-15-13-11-12-6-7-9-8-1 分析上表，一个月内可参观的景点数最多为 14 个，但其平均消费额也最大为 101.5，比景点数为 13 时的平均消费额高 20.2，综合考虑，我们向王先生夫妇推荐景点数为 13 的旅游路线：1-4-5-19-15-14-13-11-6-12-7-8-2-1 总费用为2916.2 元问题二：据分析，我们需将所有景点分为
