旅游路线规划问题-2015年研究生数学建模竞赛

参赛密码 （由组委会填写）

第十二届“中关村青联杯”全国研究生

数学建模竞赛

学校 参赛队号

队员姓名

参赛密码

（由组委会填写）

西南大学

31

第十二届“中关村青联杯”全国研究生

数学建模竞赛

题 目旅游路线规划问题

摘要：

近年来随着科技的进步和社会的不断发展，旅游活动正在成为全球经济发展的动力之一，它加速国际资金流转和信息、技术管理的传播，创造高效率消费行为模式、需求和价值等。随着人们生活水平提升，越来越多的人积极参与有益于身心健康的旅游活动。国家旅游局公布了201个5A级景区名单，但是当前人们对旅游路线规划的问题还比较盲目，如何选择最优路线游遍201个5A级景区的旅游还不够清楚。针对这些问题本文着重进行了以下几个方面的工作：

问题一，旅游爱好者常住西安市，采用高速优先的策略自驾到景区，规划设计最短路线游遍201个5A级景区。根据附件1我们利用图论和运筹学的相关知识对景区构建赋权图。由附件2的信息统计得出从西安到各省会的公路长度，结合附件一和百度地图上的高速路距离，对于分块的景区利用改良圈法建立TSP问题的旅游路优化设计模型，运用Lingo软件编程求出最短路径。对于旅游者每年有不超出30天的外出旅游时间，每次不超过15天，每年不超过4次的旅行条件，采用目标规划算法编写Java语言求出游完201个5A级景区的最佳途径。通过该程序给出了每次旅游的具体行程表。

问题二，除了高速优先之外，人们还可以考虑乘坐高铁或飞机到达与景区相邻的省会城市，再采用租车的方式自驾到景区游览，考虑旅游费用规划一个十年游遍所有201个5A级景区费用最低、旅游体验最好的旅游路线。根据附件3和附件4统计出高铁和飞机的费用，运用层次分析法在Excel中求解出从出发点到省会的最佳交通方式。利用模型一中改良圈法建立TSP问题的旅游路优化设计的路线，根据题上约束条件采用多目标规划运用Java语言编程求出游完201个5A级景区的最佳路径。由以上结果在Excel算出每次旅行的花费，规划出每次旅行的具体行程。

问题三，将模型二推广至常住北京的自驾游爱好者的十年旅游计划，根据上述三问结果分别给旅游爱好者和旅游部门提建议。考虑住宿，耗油加过路费，同样采用层次分析法确定每次旅游时旅游者的最合理的旅途方式，根据确定好的方式利用模型一中改良圈法建立的旅游优化模型，采用目标规划用Java语言给出了北京自驾游的十年旅行计划。最后结和已建立的模型考虑费用、时间等因素给出合理建议。

问题四，根据附件6和附件7给出的信息，采用改进的蚁群算法，使对景区选择能实现动态规划、从而实现旅游景区的负载均衡，用概率对景区的选择做目标规划，从而确定旅游最佳路径，求解出更为合理地规划该旅游爱好者的十年旅游计划。

关键词：图论；改良圈法；TSP问题；Java语言；目标规划；层次分析法；最优化问题改进蚁群算法；动态规划；Lingo软件

32

目录

一、问题背景与重述 ................................................................................................................ 34

1.1 问题背景 ................................................................................................................... 34 1.2 需要解决的问题 ...................................................................................................... 35 二、模型假设与符号说明 ........................................................................................................ 35

2.1 模型假设 ................................................................................................................... 35 2.2符号说明 ................................................................................................................... 36 三、问题分析 ........................................................................................................................... 37

3.1针对问题一 ................................................................................................................ 37 3.2针对问题二 ............................................................................................................ 38 3.3针对问题三 ............................................................................................................ 38

33

3.4针对问题四 ............................................................................................................ 38 四、模型的建立 ................................................................................................................. 39

4.1 问题一模型的建立和求解 ...................................................................................... 39

4.1.1 问题一模型的建立 ........................................................................................ 39 4.1.2问题一模型的求解 ................................................................................. 40 4.2 问题二模型的建立和求解 .................................................................................... 45

4.2.1 问题二模型的建立 ........................................................................................ 45 4.2.2 问题二模型的求解 ........................................................................................ 45 4.3 问题三模型的建立和求解 ................................................................................... 47

4.3.1问题三模型的建立 ....................................................................................... 47 4.3.2 问题三主要模型的求解 ................................................................................ 47 4.3.3问题三给旅游者和旅游部门的建议 ............................................................... 48 4.4 问题三模型的建立和求解 ................................................................................... 49

4.4.1问题三模型的建立 ....................................................................................... 49

五、模型的优缺点 .................................................................................................................. 51

5.1 模型的优点 ............................................................................................................ 51 5.2 模型的缺点 ............................................................................................................ 51 参考文献 .................................................................................................................................. 52 附录 .......................................................................................................................................... 52

一、 问题背景与重述 1.1 问题背景

近年来随着科技的进步和社会的不断发展，旅游已然成为人们的一种生活方式，各种旅游服务业的不断发展成熟，让人民外出旅游变得十分便捷，一方面是旅行社提供的团队游产品日益丰富；另一方面是旅游个性化的自助游,随着旅游业的日益成熟，旅游环境让旅行者渴望尝试。不管是团队游还是自助游，旅游路线都是连接旅游客源地与旅游目的地的重要环节。设计合理的旅游线路既有利于旅游者有目的的选择、安排自己的旅游活动，又有利于发挥各个旅游点的功能以及旅游者合理利用时间，还有利于旅游者有计划地支配自己的旅游费用等等。设计合理的旅游线路技术性和经验性非常强，大多数旅游者出游过程中都希望在感觉舒适和体力充沛的情况下，采用较短路程、花费较少时间和费用来游览更多的旅游景区。因此依据旅行者自身的间、旅游计划经费、准备采用的出行方式和期望的旅游地点，设计科学合理及体检最佳的旅游线路不管是对旅游组织者还是旅游者，都具有重要的意义。

34

1.2 需要解决的问题

为了给旅游爱好者规划出费用最优、旅游体验最好的的旅游路线，本文将利用数学方法解决以下数学问题：

1.采用高速优先，设计出游遍201个5A景区的具体行程安排表。

（1）旅游者采用自驾高速优先的方式，依据题目要求关于该旅游者旅游次数、旅游时间，自驾时间、自驾速度、游玩时间等规定，及附件1,2,3中相关参考信息，将201个5A级景区划分为小的分块，确定旅行完每一个小的分块的最佳旅行途径，求出该旅行者游遍201个5A级景区至少需要年数。

（2）建立数学模型对该旅行者每一次旅游中每一天的出发地、行车时间、行车里程及游览的景区做出详细的行程安排表。

2.采用多元化出行方式，设计出游遍5A景区，费用最优、体验最好的具体行程安排表。

(1)考虑全程自驾或者乘坐高铁或飞机到达与景区相邻的省会城市然后再租车到达景区游览等，建立数学模型分别计算在10年里游遍5A级景点所产生的旅游成本。

(2)综合考虑旅游成本及旅游体验，设计规划出最优的线路，并给出每一次旅行的具体行程，包括每次具体的出游方式、每一天的出发地、旅游成本、路途时间。游览景区及旅行者在每个景区的游览时间。

3．推广所建数学模型，规划出常住地在北京的自驾旅游者十年的旅行计划。 （1）将第二问中所建立的数学模型加以推广，为常住地在北京的自驾爱好者规划出十年的旅游计划，并给出每一次旅行的具体行程，包括每次具体的出游方式、每一天的出发地、旅游成本、路途时间，游览景区及旅行者在每个景区的游览时间

（2)结合前三问所建立的数学模型得出的旅游规划，分别给旅游爱好者和旅游有关部门提出合理的建议

4．针对附件6、附件7建立数学模型，采用多元化的出行方式，为该旅游者规划出十年游览5A及4A景区的行程表。

（1）优化上述数学模型，考虑在旅游成本最优及旅游体验最佳的情况下，采用多元化的出行方式，规划出旅游者十年内尽量多游览5A及4A景区的旅游线路设计。

（2）在此模型下给出每一次旅行的具体行程，包括每次具体的出游方式、每一天的出发地、旅游成本、路途时间，游览景区及旅行者在每个景区的游览时间。

二、模型假设与符号说明 2.1 模型假设 1. 附件中的数据都是准确无误的实测数据，没有经过改动。 2. 本文自行检索收集的网络资料、数据和信息都是准确无误的。

3. 该旅行者在每个省会至少停留24小时，在这24小时之内不安排景区游览。 4. 景区开放时间统一为8:00至18:00。

5. 该旅游者在每个景区的游览时间严格按附件一中的最少游览时间计算，不出现特殊情况。

6. 天气等一切突发情况不纳入考虑范围，对于道路的拥挤程度不予考虑，认为是通畅的。

7. 对于高铁及航班的晚点情况不予考虑，认为是准点的，忽略一切等车时间。 8.不考虑旅途中可能突发的汽车故障及旅行者身体不适等因素。

9. 假设旅游时间只包括交通乘车时间和在景点的旅游时间，不包括住宿时间。

35

10. 假设全国所有5A级旅游景区门票费用都一样，所有4A级旅游景区门票费用都一样。

11. 该旅行者的住宿费简化为：省会城市和景区每人每天200元，地级市每人每天150元，县城每人每天100元。

2.2 符号说明

符号

im

符号说明

第m个省内的第i个旅游景区

i?1第m个省内的所有景区游览时间 i?2第m个省内景区间线路花费时间

tim

m dij第m个省内的从第i个旅游景区到第j个旅游景区距离

第m个省内的从第i个旅游景区到第j个旅游景区驾车所花费的第m个省内的从第i个旅游景区到第j个旅游景区所花费的交通

tim

mcijrij

Mmrij?1游客从第i个景点到第j个景点 第个省的旅游总费用m?rij0i 旅游总成本

第m个省内的第i个旅游景区住宿费 第m个省内景区间路程上花费的时间 游览总时间

第m个省旅游景区的数目 各5A级旅游景区的门票费用 各4A级旅游景区的门票费用 第m个省的最短路径长度

从西安市到第m个省会城市高速路所需要的时间 第m个省内游览景区花费的时间

第m个省内所产生的景区门票、交通费、住宿费的总和 第m个省内的高速公路里程数

jM

MZim

TmT nm b1 b2 dm T1m ?mT Pm

D1m

36

m D2mP1

第m个省内的普通公路里程数 从西安到第m个省会的高铁费用 从西安到第m个省会的航班费用 从西安到各个省会的交通时间 第i个景区中的最大人流量 第i个景区在t时刻旅游景区的人数

P2m

tm

i ?max?i(t)

P1 Li

t时刻旅游景区人数与最大人流量比值 第i个旅游景区到当地省会的距离 所有景点到当地省会的总距离

旅游景区到当地省会的距离与总距离的比值 第j次旅行花费的总费用 第j次旅游t时刻剩余的费用 费用花费率 是否去第i个景点

L P2

?j

?j(t)

P3

?i

三、问题分析

3.1 针对问题一 采用高速优先，设计出游遍5A景区的具体行程安排表，分析问题得知求游遍201个5A级景区最少需要的年数，先不考虑旅行成本，由附件1假设该旅行者在各个景区游览时间按最少游览时间计算，该问题实际就是在一定的约束条件下求出最短的行程问题。从整体上来说，题目实际上研究的就是运筹学及图论中的组合优化问题。

将各个景区看成图中的一个顶点，边表示连通各个景区之间的路，边上的权表示距离（或时间或费用），由此形成了旅行问题的加权网络图，那问题就转化成了求这个简单的网络加权图的最佳推销员回路问题，也就是TSP问题。又根据附件一中该旅游者计划在每个省会城市至少停留24小时，且各个省会城市的交通高速网相对完善发达，故考虑将各个省会城市作为从西安市到各个省份旅游景区的中转站，将各个省会划分为独立的小板块。

针对多局部最优的最优化问题，目前解法主要有遗传算法、最小生成法、模拟退火法、蚁群法、局部搜索及神经网络等，因为简化模型后各个小板块内顶点不多，考虑对该TSP问题用一般方法求Hamilton圈，建立数学规划

37

模型用lingo程序求出精确的最短圈长度及最短路径，从而求出走完这一小版块的最短时间。然后将各个省看成节点，由于自驾游爱好者每年有不超过30天的外出旅游时间，每年外出旅游的次数不超过4次，每次旅游的时间不超过15天，我们根据这些约束条件建立约束函数然后采用Java程序求出每年的具体旅游行程。

3.2 针对问题二

问题二中题设中丰富了旅行者的出行方式，总共可分为三种。第一种是问题一中高速优先的全程自驾，第二种是先乘高铁到省会城市，然后租车的方式；最后一种先坐飞机到省会城市，然后租车到景区。考虑三种方式下旅游者在旅途过程中分别产生的旅游总费用，其中包括交通费用(包含可能产生的高铁费、机票费、租车费、高速公路的油耗加过路费及普通公路上的油耗费)住宿费用及景区门票。

问题二中要求规划出费用最优、旅游体验最好的旅行路线，结合实际我们将旅行体验具体量化为旅行中在交通工具上所花费的时间最短，众所周知旅途中交通工具所占时间比重越少，比如在不考虑旅行费用的前提下，乘坐飞机固然比乘坐高铁或汽车带给旅行者的旅行体验更佳。

又针对旅行费用和旅行交通工具所占时间这两个权衡指标因人而异，用层次分析法予以权衡这两个指标，来求解合适的交通方式，然后运用Java程序从而建立设计出十年内游遍所有5A级景区、费用最优、旅游体验最好的旅游路线。然后再依据问题二中具体旅游行程中的相关约定（旅游者在任一景区最长逗留时间不超过附件1给出的最少时间的两倍，高铁出行当天乘坐高铁时间不超过6小时，乘坐高铁或飞机当天至多安排半天的景区游览等）便能具体规划出并给出每一次旅行的具体行程，包括每次具体的出游方式、每一天的出发地、旅游成本、路途时间。游览景区及旅行者在每个景区的游览时间。

3.3 针对问题三

在问题二已有的交通方式即高速优先的全程自驾、先乘高铁到省会城市，然后租车的方式、最后一种先坐飞机到省会城市，然后租车到景区。此次旅游为常住在北京市的自驾游爱好者的十年旅游计划，考虑模型二旅游者在旅途过程中分别产生的旅游总费用，其中包括交通费用住宿费用及景区门票结合，实际在旅行中若在交通工具上所花费的时间短，旅途中交通工具所占时间比重少，我们旅行的时间就少。

又针对旅行费用和旅行交通工具所占时间这两个权衡指标因人而异，用层次分析法予以权衡这两个指标，来求解合适的交通方式，再依据问题二中具体旅游行程中的相关约定（旅游者在任一景区最长逗留时间不超过附件1给出的最少时间的两倍，高铁出行当天乘坐高铁时间不超过6小时，乘坐高铁或飞机当天至多安排半天的景区游览等），然后运用Java程序从而建立设计出十年内游遍所有5A级景区、费用最优、旅游体验最好的旅游路线。便能具体规划出并给出每一次旅行的具体行程，包括每次具体的出游方式、每一天的出发地、旅游成本、路途时间。游览景区及旅行者在每个景区的游览时间。

3.4 针对问题四

38

实际上任何一个旅游景区接待游客的能力都是有限的，无限制的接待游客将导致景区的生态环境遭到严重的破坏。从旅游者来说一个景区接待的人数越多，景区的交通及公共服务能力必然会大幅下降，欣赏风景时人头攒动会耗费旅行者的时间和精力，会在很大程度上影响游客的旅行质量，游客满意度及体验感会下降，因此一个景区容纳游客的数量就该依据具体每个景区的相关配套设施及公共服务能力严加控制。正如近年来出现的黄金周旅游热，使得旅游爱好者在制定旅游规划时针对第四问要求给出更为合理的旅游规划路线，因此考虑将利用图论最大流方法和层次分析法讨论景区的流量控制时，定义t时刻景区m的人流量，产生动态的景区人流量比例函数，这个函数将一定程度上制约旅行者是否选取该景点作为下一站。对于多景点间的顺序规划的实现借助于改进后的蚁群算法。

四、模型的建立

4.1 问题一模型的建立和求解 4.1.1 问题一模型的建立 首先由题目中约束条件该旅游者计划在每个省会城市至少停留24小时，且由附件2知各个省会城市的交通高速网相对完善发达，故考虑将各个省会城市作为从西安市到各个省份旅游景区的中转站，将各个省划分为独立的板块，便于表述将其按附件1中的顺序编号为b1,b2,?,b31。然后将省内的各个旅游景点之间的关系转化为图论问题，建立赋权图G?V,E?，其中V??V1,V2,?,Vn?称为G的节点集，V的每一个元素Vi?i?1,2,?,n?在该问题中表示景点之间。即将每一个省内的旅游景区看着图中的一个节点，各景区景点之间的线路看成图中对应节点间的边，边上的长度表示旅游景区之间的距离，所给各旅游景区间的公路网就转化成为网络图G，要游遍该省内的各5A级景区的最佳旅游路线问题就转化为在给定的网络图中寻找从给定出发点出发，行遍所有顶点至少一次再回到定点，使得距离最小，此即改良圈算法建立的最佳旅行商问题（TSP问题）。TSP问题的本质就是从出发点出发最后回到出发点的距离最小Hamilton圈，采用改良圈算法解该问题。

Hamilton圈的最邻近算法的基本思想：

第一步：任意选一个点v0作起点，找一条与v0关联且权最小的边e1，e1的另一个端点记作v1，得到一条路v0v1；

第二步：设已选出路v0v1?vi，在V?G???v0,v1,?,vi的相邻顶点vi?1得到路v0v1?vivi?1；

第三步：若i?1?n?1，用i代替i?1返回步骤二，否则记v0v1?vpv0，停止

?中取一个与vi最邻近

39

得到一条近似最优的Hamilton回路。用最邻近算法求得的Hamilton回路一般不是最优解，但是通过改良可以获得更短的Hamilton回路。设C?v0v1?vnv1是网络图G的一个Hamilton圈。对圈C中所有满足1?i?1?j?v的i,j，按照以下方法最终得到一条新的Hamilton圈C1:

第一步：在C上检查是否有i?j，使得vivj?E?G?,vi?1vj?1?E?G?且

w?vivj??w?vi?1vj?1??w?vivi?1??w?vjvj?1?，

则构成新圈

C1?v1v2?vivjvj?1?vi?1vj?1?vnv1。

第二步：用C1代替C转到第一步，直到终止。 将改良圈算法写成数学规划模型有：

mmin?dijrij，

i?js.t.?rj?1niji?1nij?1,i?1,2,?,n，

?ri,j?s?1,j?1,2,?,n，

?rij?s?1,2?s?n?1,s??1,2,?,n?，

即s为?1,2,?,n?的真子集（除起点和终点外，各边不构成圈），

rij??0,1?,i,j?1,2,?,n,i?j。

4.1.2 问题一模型的求解

由附件1及附件2相关信息统计可得各个省(小板块)内所有旅游景区及省会城市之间的线路距离表（单位：公里）注：所有省均设其省会城市为1，其余旅游景区按附件1中给出顺序依次编号2,3,?,n；依据附件1、附件9相关信息及中国行政区域划分图，为了便于计算将河北省内的景点按邻近原则划分到北京和天津区域内，将江苏省内的景点划分部分到上海景区。

表1：山西省内所有旅游景区及省会城市之间的线路距离表 1 2

1 0 276 2 276 0 3 80 257 4 344 620

40

5 135 411 67 86 361 7 107 382

3 4 5 6 7

80 344 135 86 107 257 620 411 361 382 0 531 322 272 293 531 0 299 351 324 322 299 0 61 34 272 351 61 0 32 293 324 34 32 0

通过编写Lingo，求解得到结果如下（代码见附录1) 求得的山西省内各旅游景区及省会城市的最短路径为

1?4?5?7?6?2?3?1，最短路径长度1407公里。即山西省内各旅游景区及省会城市的最短路径为：太原市? 晋城阳城县皇城相府生态文化旅游区 ?晋中市介休市绵山风景名胜区 ?晋中市平遥县平遥古城景区 ? 晋中市乔家大院文化园区?大同云冈石窟? 忻州五台山风景名胜区 ?太原市。

如下以山西省为例验证该算法：

图1：山西省内景点分布图

从图1可以看出山西省内5A级景点分布零散，采用上述算法对该7个景点求最短路径后绘图如图2。

图2：山西省内景点的最短路径图

同样方法运行Lingo（附录1）求出其余省份的最短路径及最短路径长度见下表2：

41

表2：各省份最短路径及最短路径长度表

省份 北京 天津 山西 内蒙古 辽宁 吉林 黑龙江 上海 江苏 浙江

最短路径

1?3?4?7?5?6?9?10?8?2?1 1?7?6?4?3?2?5?1 1?4?5?7?6?2?3?1 1?3?2?1

1?3?4?5?2?1 1?3?4?5?2?1 1?3?6?5?4?2?1

1?13?7?8?11?5?10?12?9?6?2?3?4?1

1?3?2?10?8?5?11?7?6?4?9?1

1?2?10?13?6?9?4?7?3?8?12?5?11?1

1?8?6?4?5?9?7?2?3?1 1?7?2?5?4?3?6?8?9?1 1?2?7?6?4?5?8?3?1

1?10?3?7?6?5?8?4?2?9?1

1?7?5?4?2?8?10?3?6?9?11?1

1?9?2?11?5?7?6?12?10?4?3?8?1 1?6?7?4?3?8?5?2?1

1?11?9?7?8?5?10?3?6?4?2?1 1?4?2?3?5?1 1?5?2?3?6?4?1 1?6?7?4?5?3?2?1

1?7?10?9?11?4?6?8?2?5?3?1 1?3?2?4?5?1

1?4?3?7?5?6?2?1 1?3?2?1

1?5?2?6?3?4?7?1 1?4?3?2?5?1 1?4?2?3?5?1 1?3?2?1

1?2?8?10?7?6?4?5?9?3?1

最短路径长度 835 928 1407 543 981 792 3371 318 933 1452

安徽 1310 福建 1377 江西 1610 山东 1585 河南 1327 湖北 1750 湖南 1496 广东 1576 广西 914 海南 617 重庆 1531 四川 1789 贵州 1117 云南 2150 西藏 0 陕西 713 甘肃 3046 宁夏 599 青海 404 新疆 2907

问题一中行车路线要求采用高速优先的策略，即先通过高速公路到达与景区邻近的城市，再自驾到景区。由附件2、附件8和附件9，运用数学方法近似求得在各个省内高速公路和普通公路权重分别为0.8与0.2，又有假设自驾在高速公路上的行车平均速度为90公里/小时，在普通公路上的行车平均速度为40公里/小时，有计算式：

bmbmT??

90*0.8?40*0.280m由表2中各省内的最短路径长度及上述计算式，求出各省内（板块内）所需要游览

42

本文来源：https://www.bwwdw.com/article/mebd.html