没有合适的资源?快使用搜索试试~ 我知道了~
首页关于潘安湖风景区的游览路线设计
关于潘安湖风景区的游览路线设计
5星 · 超过95%的资源 需积分: 42 102 下载量 27 浏览量
更新于2023-03-16
31
收藏 344KB PDF 举报
为完成游客在景区的游览路线设计问题,本文基于整数线性规划,0— 1模型,双层嵌套规划,分支定界法,遗传算法等方法进行解决。 针对问题一,需要解决经过经过①一⑥所有景点至少1次的距离最短的路线, 计算该路线的长度。这是一个Tsp旅行商问题,需建立整数线性规划模型,同时确go—1变构成0—1模型,加上约束条件,利用lingo编程可直接得出距离最短的经过六个景点的顺序
资源详情
资源推荐
1
关于潘安湖风景区的游览路线设计
摘要
为完成在一定约束以及不同要求的前提下游客的游览路线设计,我们在基于优化
模型,TSP 模型的前提下,运用 lingo 编程,在一定的人工设计的基础上求得每个
问题的路线。
针对问题一,需要解决从景石出发最终到达湿地商业街中间所有景点至少一次的
最短路线,并计算该路线的长度。我们运用 TSP 模型,优化模型,设定相应的变量,
利用 0-1 规划,加上约束条件,利用 lingo 编程,可求得距离最短的经过六个景点
的路线。
针对问题二,需要设计一条经过所有景点且游览时间最长的路线。由于我们需要
保证森林小剧场是半点或者整点进入,所以在游览时间最长的前提下,从景石出发
不能直接到达森林小剧场,而且还要保证在 16:00 之前到达游客服务中心。同样运
用 0-1 规划,优化模型,在问题一的理解下,加上时间约束路线约束,利用 lingo
编程,可最终求得能游览完所有景点且游览总时间最长的路线。
针对问题三,需要给三个旅游团分别设计一条路线,使得每个旅游团都能游览完
且总游览时间最长。问题三是在问题二的基础上将游览数量由一变到三,而由于每
个景点只能容纳一个地方所以将会限制每个旅游团的路线,所以该问题还要考虑等
待时间。我们在问题三中,在问题二的前提下运用 0-1 规划,TSP 模型,优化模型,
而且在一定的人为规划下,利用 lingo 编程,可求得三条路线。
针对问题四,在速度可在满足条件的一定范围内改变的前提下,需要给三个旅游
团分别设计一条路线,使得每个旅游团都能游览完且总游览时间最长。依据问题三
的约束和分析,在人为设定条件下,安排和规划路线,可求得最后结果。
针对问题五,需要在考虑现实条件和不确定因素的情况下,设计和规划多个旅游
团的路线。
本论文结合多种方法,主要运用 lingo 进行编程,思路清理,模型合理,合理的
解决 0-1 规划问题,针对不同的问题给出了合理的数学模型,建立了合理的目标函
数和约束条件。
关键词:游览路线设计 TSP 问题 0-1 规划 优化模型
1
目录
一、 问题重述................................................................................................................................................ 1
二、 问题分析................................................................................................................................................ 1
2.1 问题一的分析:............................................................................................................................... 1
2.2 问题二的分析:............................................................................................................................... 1
2.3 问题三的分析:............................................................................................................................... 1
2.4 问题四的分析:............................................................................................................................... 2
2.5 问题五的分析:............................................................................................................................... 2
三、 模型假设................................................................................................................................................ 2
四、 符号说明................................................................................................................................................ 2
五、 模型的建立与求解................................................................................................................................ 3
5.1 问题一:........................................................................................................................................... 3
5.2 问题二:........................................................................................................................................... 6
5.3 问题三:........................................................................................................................................... 9
5.4 问题四:......................................................................................................................................... 11
5.5 问题五:......................................................................................................................................... 12
六、 模型的评价、改进及推广.................................................................................................................. 13
6.1 模型的评价..................................................................................................................................... 13
6.2 模型的改进及推广......................................................................................................................... 13
七、 参考文献.............................................................................................................................................. 13
八、 附录...................................................................................................................................................... 14
附录 1 为题目所给景区关系图以及景区间的不行最短距离;................................................................ 14
附录 2 为各景区游览及开放时间;............................................................................................................ 14
附录 4 为各个问题的具体程序以及问题二的详细结果;........................................................................ 14
附录 1:......................................................................................................................................................... 14
图 1.1 景区关系图................................................................................................................................14
图 1.2 景点之间的最短步行距离(单位:米)....................................................................................14
附录 2:......................................................................................................................................................... 14
图 2 各景点游览及开放时间............................................................................................................... 15
附录 3:......................................................................................................................................................... 15
问题一程序:................................................................................................................................................ 15
问题二程序:................................................................................................................................................ 16
1
一、问题重述
徐州市是一个有着长达 130 年历史煤炭开采的老工业基地和资源型城市,但长
时间的煤炭开采造成了严重的塌陷。2010 年,江苏省单位体投资最大的土地整理项
目在潘安湖启动,利用坍塌形成的开阔水面建立了一个 6500 亩湖面的国家级水利风
景区。本题主要是根据有关假设设计潘安湖风景区的部分景点游览路线。
分析题目并建立合适的数学模型解决以下问题:
1. 根据附件 1 中所给的关系图及景点之间的最短距离,分析并设计一条从景
石出发经过所有景点不停留至少一次的情况下最终到达湿地商业街的最短路
线,并求出路线总长度。
2. 在附件 2 中各个景点的开放时间内且每个景点没有等待时间的情况下保证
总游览时间最长的游览完所有景点,设计游览路线并求出每个景点的到达时
间、游览时间和离开时间。
3. 保证三个旅游团同时 12:00 从景石出发 17:00 到达湿地商业街 17:30 离开
并且每个景点只能容纳一个旅游团,后到达的需要等待先到达的游览结束才能
开始游览,根据要求为每个旅游团设计一条能游览完所有景点且游览总时间最
长的路线。
4. 在速度可以在 1km/h 到 3km/h 调节但总平均速度不超过 2km/h 条件下,三
个旅游团同时 12:00 从景石出发 17:00 到达湿地商业街 17:30 离开并且每个
景点只能容纳一个旅游团,后到达的需要等待先到达的游览结束才能开始游
览,根据要求为每个旅游团设计一条能游览完所有景点且等待时间短的路线。
5. 考虑不同旅游团出发时间不同每个景区等待时间不同的因素下在问题四的
条件下为每个旅游团设计一条能游览完所有景点且等待时间短的路线。
二、问题分析
2.1 问题一的分析:
问题一中,可以根据附件 1 中所给的图表,在了解该问题是类似于 TSP 问题的前提
下利用 0-1 规划的方法,用解决最优问题的思路,根据题目在每个景点不用停留且
不考虑其他问题的情况下,从景石出发除湿地商业街外,所有景点可以重复经过的
情况下求出最短路径。
2.2 问题二的分析:
问题二中,步行速度在假设中已经给出,根据附件 2 可以看出需要约束森林小剧场
和游客服务中心的到达时间,可以在保证总游览时间最长的情况下,由于到达森林
小剧场为半点或整点,所以需要给到达森林小剧场之前所到景区合理分配时间,使
得每个地区的游览时间加上之前的所有路上的时间使之尽量于半点或者整点到达,
否则就需要一定的等待时间。所以根据以上推测可以得出从景石出发到达的第一个
景区不可能是森林小剧场。由于游客服务中心需要在 16:00 之前到达,所以需要根
据在其之前的每个景区游览时间来合理分配,以及路上所消耗的所有时间来限制到
达的时间。由于要保证游览时间最长且所有景点都必须游览,所以根据条件可以推
测每个景点只游览一次。
2.3 问题三的分析:
在问题三中,每个景点的时间限制条件及步行速度和第二问一样,是三个旅游团同
时出发而且都要在规定的时间内游览完所有景点并在 17:00 之前到达湿地商业街,
2
而且题目中限制除湿地商业街外每个景点只能容纳一个旅游团,后到达的旅游团要
等先到达的结束后才能开始。要是游览时间最少,就要设计三条路线,尽量使得每
个景点只容纳一个旅游团,尽量使等待的总时间最小,路上时间在上述约束下取最
小。最终达到每个旅游团都能在 16:00 之前离开游客服务中心,都能在半点或者整
点进入森林小剧场,在 17:00 之前到达湿地商业街,在此前提下保证三个旅游团都
能游览完所有景点,并且游览时间最长。在此分析下,分别求得每个旅游团的约束
路线。
2.4 问题四的分析:
问题四中,每个景点的时间限制条件以及容纳量和第三问一样,但是三个旅游团的
速度都是可在 1km/h 到 3km/h 内调节,但是总平均速度不超过 2km/h,既然速度可
调,就可以选择在不同的路线上速度不同。除速度约束和问题三不同外,其他约束
都一样,在此约束和分析下,而且要求总游览时间最长总等待时间尽最短,建立数
学模型,为三个旅游团分别设计一条旅游路线。
2.5 问题五的分析:
问题五将现实元素考虑进去,设计多个旅游团的游览路线,多个旅游团从景石出发
的时间不一定相同,而且到达湿地商业街的时间只要在其开放时间内即可,每个景
点的等待时间也有可能有变,其他时间约束以及景点约束与问题四相同。在此分析
下,建立合适的数学模型,为多个旅游团分别设计一条能游览完所有景点且总游览
时间最长总等待时间最短的路线。
三、模型假设
假设:
1.任意两个景区之间的最短步行距离及景区关系图见附件 1。
2.问题二问题三中步行速度为 2km/h。
3.游客在景区停留时间包括景点间的步行时间、景点游览时间、景区外的等待时间。
游览时间必须符合附件 2 所给数据。
4.在游览过程中不出现其他问题。
5.每个景点对应数字为:
数字
1
2
3
4
5
6
7
8
景点
景石
旅游服
务中心
阳光草
坪
森林小
剧场
儿童科
普体验
区
儿童戏
水场
湿地博
物馆
湿地商
业街
四、符号说明
ji,
:第 i 个或者第 j 个景点,
ji,
=1,2......,8;
分别表示景石,游客服务中心,阳光草坪,森林小剧场,儿童科普体验区,儿
童戏水场,湿地博物馆,湿地商业街
c
ij
:从第 i 个
景点
到第 j 个景点之间的距离;
x
ij
:
0
x
ij
表示不经过从 i 到 j 的路线,
1
x
ij
表示经过从 i 到 j 的路线;
x
im
:从第 i 个景点到第 m 个景点的路线(m≠i≠j,2≤m≤8) ;
剩余18页未读,继续阅读
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功