研究生数学建模竞赛

2023年12月15日发(作者：张店高三数学试卷)

研究生数学建模竞赛

参赛密码

（由组委会填写）

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

数学建模竞赛

学校西南大学

参赛队号

队员姓名

参赛密码

（由组委会填写）

31 / 25

研究生数学建模竞赛

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

数学建模竞赛

题目

旅游路线规划问题

摘要：

近年来随着科技的进步和社会的不断发展，旅游活动正在成为全球经济发展的动力之一，它加速国际资金流转和信息、技术管理的传播，创造高效率消费行为模式、需求和价值等。随着人们生活水平提升，越来越多的人积极参与有益于身心健康的旅游活动。国家旅游局公布了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 / 25 研究生数学建模竞赛

一、问题背景与重述 ................................................................................................................ 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 / 25 研究生数学建模竞赛

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 问题二模型的求解 ........................................................................................ 46

4.3 问题三模型的建立和求解 ................................................................................... 47

4.3.1 问题三模型的建立 ..................................................................................... 47

4.3.2 问题三主要模型的求解 .............................................................................. 48

4.3.3 问题三给旅游者和旅游部门的建议 ........................................................... 49

4.4 问题三模型的建立和求解 ................................................................................... 50

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

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

5.1 模型的优点 ............................................................................................................ 52

5.2 模型的缺点 ............................................................................................................ 52

参考文献 .................................................................................................................................. 52

附录 .......................................................................................................................................... 53

一、问题背景与重述

1.1 问题背景

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

34 / 25 研究生数学建模竞赛

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 / 25 研究生数学建模竞赛

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

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

2.2 符号说明

符号

符号说明

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

i1第m个省内的所有景区游览时间

i2第m个省内景区间线路花费时间

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

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

tim

dijtim

mcijrij

Mmrij1游客从第i个景点到第j个景点

第m个省的旅游总费用

旅游总成本

第m个省内的第i个旅游景区住宿费

第m个省内景区间路程上花费的时间

游览总时间

第m个省旅游景区的数目

各5A级旅游景区的门票费用

各4A级旅游景区的门票费用

第m个省的最短路径长度

从西安市到第m个省会城市高速路所需要的时间

第m个省内游览景区花费的时间

第m个省内所产生的景区门票、交通费、住宿费的总和

第m个省内的高速公路里程数

T1m

ˆmT

D1m

36 / 25 研究生数学建模竞赛

D2m

mP1

第m个省内的普通公路里程数

从西安到第m个省会的高铁费用

从西安到第m个省会的航班费用

从西安到各个省会的交通时间

第i个景区中的最大人流量

第i个景区在t时刻旅游景区的人数

P2m

maxi(t)

t时刻旅游景区人数与最大人流量比值

第i个旅游景区到当地省会的距离

所有景点到当地省会的总距离

旅游景区到当地省会的距离与总距离的比值

第j次旅行花费的总费用

第j次旅游t时刻剩余的费用

费用花费率

是否去第i个景点

j

j(t)

i

三、问题分析

3.1 针对问题一

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

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

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

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

3.2 针对问题二

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

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

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

3.3 针对问题三

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

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

3.4 针对问题四

38 / 25 研究生数学建模竞赛

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

四、模型的建立

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

4.1.1 问题一模型的建立

首先由题目中约束条件该旅游者计划在每个省会城市至少停留24小时，且由附件2知各个省会城市的交通高速网相对完善发达，故考虑将各个省会城市作为从西安市到各个省份旅游景区的中转站，将各个省划分为独立的板块，便于表述将其按附件1中的顺序编号为b1,b2,,b31。然后将省内的各个旅V1,V2,,Vn游景点之间的关系转化为图论问题，建立赋权图GV,E，其中V称为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 / 25 研究生数学建模竞赛

得到一条近似最优的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.

nrj1ijnij1,i1,2,,n，

ri11,j1,2,,n，

i,jsrijs1,2sn1,s1,2,,n，

1,2,,n的真子集（除起点和终点外，各边不构成圈），即s为rij0,1,i,j1,2,,n,ij。

4.1.2 问题一模型的求解

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

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

40 / 25 研究生数学建模竞赛

276

344

135

107

276

257

620

411

361

382

257

531

322

272

293

344

620

531

299

351

324

135

411

322

299

361

272

351

107

382

293

324

通过编写Lingo，求解得到结果如下（代码见附录1)

求得的山西省内各旅游景区及省会城市的最短路径为14576231，最短路径长度1407公里。即山西省内各旅游景区及省会城市的最短路径为：太原市 晋城阳城县皇城相府生态文化旅游区

晋中市介休市绵山风景名胜区

晋中市平遥县平遥古城景区

 晋中市乔家大院文化园区大同云冈石窟 忻州五台山风景名胜区

太原市。

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

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

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

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

41 / 25 研究生数学建模竞赛

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

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

省份最短路径最短路径长度

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

北京

835

17643251

天津

928

14576231

山西

1407

内蒙古

1321

543

134521

辽宁

981

134521

吉林

792

黑龙江

1365421

3371

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

上海

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

江苏

933

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

浙江

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

安徽

1310

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

福建

1377

127645831

江西

1610

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

山东

1585

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

河南

1327

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

湖北

1750

167438521

湖南

1496

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

广东

1576

142351

广西

914

1523641

海南

617

16745321

重庆

1531

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

四川

1789

132451

贵州

1117

14375621

云南

2150

1321

西藏

15263471

陕西

713

143251

甘肃

3046

142351

宁夏

599

1321

青海

404

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

新疆

2907

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

42 / 25 研究生数学建模竞赛

bmbmT

90*0.840*0.280m由表2中各省内的最短路径长度及上述计算式，求出各省内（板块内）所需要游览天数，然后由附件3能统计得出该旅行者从西安市到各个省会城市自驾行驶高速公路的里程数，又假设自驾在高速公路上的行车平均速度为90公里/小时，则从西安市出发到各个省会城市然后返回西安市所花费的旅游天数能计算得出。

目标函数的建立：

问题一中，在不考虑旅游费用的情况下，要求游览完201个5A级景区，使得该旅游者花费的时间最少。旅游者的时间花费由三部分组成，包括从西安市出发到各省会城市并折返回西安市的时间、花费在各个省内景区之间路程上的时间及游览景点的时间。（注：单位统一换算为天数）时间综合表

注：最后折算的总时间天数的小数部分，大于0.1按1天计算；其余情况按0计算）

ˆm由此总花费时间计算公式：T2*T1mTmT

T1mbmˆm

4640T

ˆm，当m从1取到30时，对应的省份所花费的总时间为12、11、9.5从而计算可得T、6、10、10.5、16、13、12、14.5、13、15、13、12、13.5、14.5、12、14、10、10.5、11.5、14、9、13.5、10、6、11、6.5、6、21。

由上数据发现从西安市前往新疆一次游览完所有的旅游景区需要花费21天，但题中限制该旅游爱好者每次旅游时间不超过15天。此处我们先粗略将新疆的景区按高速路G3012划分成南北两个部分，每部分近似估计游览时间为10天。

由以上所建立的数学模型，对旅游线路的规划可分以下几种情况加以讨论：

因每年所举行的旅行的次数不超过4次，可分为

(1) 若一年要4次旅行，根据题目的条件建立相应的约束函数

y1y2y3y430

5yi15

通过软件求出满足条件的分类有4中即得：

6+6+6+12 6+6+7+11 6+6+8+10 6+7+9+10

（2）若一年要3次旅行，根据题目的条件建立相应的约束函数

y1y2y330

5yi15,i1,2,3，yiN

通过软件求出满足条件的分类有

6+9+15 6+9+14 6+9+13 6+9+12 6+9+11 6+9+10 6+9+9

7+8+15 7+8+14 7+8+13 7+8+12 7+8+11 7+8+10 7+8+9

(3)若一年要2次旅行，根据题目的条件建立相应的约束函数：

y1y230

43 / 25 研究生数学建模竞赛

5yi15,i1,2,3，yiN

通过软件求出满足条件的分类有：

15+15 15+14 15+13 15+12 15+11 15+10

14+13 14+12 14+11 14+10 13+12 15+9

据以上建模和其他约束条件可以推出至少需要12年时间将所有地区走完，具体路径如下：

表4：模型一中十年旅行规划表

旅行年数旅行次数旅行地方

1 3 青海山西河南

2 3 陕西吉林上海

3 3 内蒙古辽宁安徽

4 3 宁夏海南江苏

5 3 贵州广西甘肃

6 3 西藏新疆新疆

7 2 北京天津

8 2 黑龙江浙江

9 2 福建江西

10 2 山东湖北

11 2 湖南广东

12 2 重庆四川

13 1 云南

由于地理位置的原因，游客可以自行调整旅游时间相同的地方自行旅游。由以上结果可以推出至少需要12年完成旅行，具体旅行路线与上述求得的每个省市内部旅游地点的安排有着密切的联系。下面以山西省为例给出具体的行程安排，其中包括每一天的出发地、行车时间、行车里程、游览景区及游览景区时间，其他省市类似布置每天的具体旅行行程。

表5：模型一旅程具体行程安排表

44 / 25 研究生数学建模竞赛

天数

1上午

2上午

3下午

4下午

5下午

6上午

6下午

7下午

9上午

出发地行车时行车路游览景区景（天间程数）

西安市 8 720 无 0

4 360 太原市 1

太原市 4 344 晋城阳城县皇城相府生态文化旅0.5

游区

晋阳市 4 299 晋中市介休市绵山风景名胜区 0.5

介休市 0.5 34 晋中市平遥县平遥古城景区 0.5

平遥县 0.5 32 晋中市乔家大院文化园区 0.5

乔家大4 361 大同云冈石窟 0.5

院

大同 4 257 忻州五台山风景区 1

忻州 1 80 太原 0

太原 7 80 西安 0

4.2 问题二模型的建立和求解

4.2.1 问题二模型的建立

问题二中该旅游者在出游的交通工具上有多种方式可选，考虑到附件4和附件5中提供的从旅游者所在的西安市到各省会城市的航班和高铁信息，为了简化模型，我们考虑有三种出游方式。第一种是问题一中的高速优先的全程自驾方式；第二种是先有西安市乘坐高铁到达与景区相邻的省会城市，而后采用租车的方式自驾到景区游览；第三种是是先有西安市乘坐直达航班（注：为了节约出游时间，只考虑从西安市直飞各个省会城市的情况）到达与景区相邻的省会城市，而后采用租车的方式自驾到景区游览。由问题中一中所建立的TSP问题模型中，采用改良圈算法给出了各省份内最短路径及其最短路径长度，确定了各个省份旅游景区的游览时间及具体行程安排，加上由此会产生的住宿费用及门票费用。因为三种出游方式在各个省份内部产生的交通费用，除了第一种全程自驾会多出每天300元的租车费用外，其余的交通费用都一致；交通费用产生差异最大的地方是在从西安市到各个省会城市之间的旅程中，依据不同的自驾、高铁、航班产生不同的交通费用。

又依据问题二中描述，要规划出能在10年游遍5A级景区的、费用最优、旅游体验最好的旅游路线。为了更好的建立模型，将旅游体验最好这个准则层量化成为旅行中在交通工具上所花费的时间最短。

对这两个准则层，在高校附近采用随机市场调查，填写问卷报告用联测法分析判断预测该地区人群对旅行中的这两个准则层的权重，加权予以权衡这两个指标，从而建立数学规划模型设计出十年内游遍所有5A级景区、费用最优、旅游体验最好的旅游路线，随后依据问题二中相关规定限制条件，规划出这十年间具体的旅游行程费用。

45 / 25 研究生数学建模竞赛

图3：费用、时间的层次分析图

4.2.2 问题二模型的求解

对费用最优与旅游体验最好（具体量化为旅行中在交通工具上所花费的时间最短）两个准则层，利用层次分析法，通过上述调查分别取其权重为：

w10.3,w20.7

权重和为：

Aw1*Mw2*T

考虑第一种出行方式（全程自驾）：

mˆm

ˆmTA1w1D1m1D20.6Pmw2t考虑第二种出行方式（西安高铁到省会城市，后自驾）：

mmmmˆm

ˆmTA2w1Pw2t13t1t2300P 考虑第三种出行方式（西安航班到省会城市，后自驾）：

m300Pmw2tˆmTˆm

A3w1P2m3t1mt2m依据附件2、3及查阅百度地图相关信息可统计出D1m,D2的数据，由模型一的求解过程得出：

表6：模型二的十年旅行规划表

46 / 25 研究生数学建模竞赛

旅行年数

表7：模型二的旅程具体行程安排表

天数

2天中午

3天上午

3天下午

4天

4天下午

5天上午

6天下午

8天上午

出发地

西安

北京

北京市延庆县

北京市昌平区

承德

北京

费用

1546.5

2700

250

292

229

路途时间（h）

5.5

1.5

0.5

游览景区

北京

天坛

颐和园

恭王府景区

八达岭-慕田峪

明十三陵

承德避暑山庄

秦皇岛

奥林匹克公园

故宫

游览时间

0.5

旅行次数

旅行地方

北京

内蒙古

上海

浙江

福建

山东

湖北

广东

重庆

西藏

天津

辽宁

江苏

安徽

江西

河南

湖南

四川

贵州

新疆

山西

吉林

广西

海南

青海

陕西

宁夏

甘肃

黑龙江

9天上午北京 0 0 1

注：其余省市的旅程具体行程安排表类似可知。

4.3 问题三模型的建立和求解

4.3.1 问题三模型的建立

由于旅游者在出游的交通工具上有多种方式（高速优先的全程自驾方式、先由北京市乘坐高铁到达与景区相邻的省会城市再采用租车的方式自驾到景区游览、是先有北京市乘坐直达航班（为了节约出游时间，只考虑从西安市直飞各个省会城市的情况）到达与景区相邻的省会城市再采用租车的方式自驾到景区游览）可选，在问题一所建立的TSP问题模型中，采用改良圈算法给出了各省份内最短路径及其最短路径长度，确定了各个省份旅游景区的游览时间及具体行程安排，加上由此会产生的住宿费用及门票费用。因为三种出游方式在各个省份内部产生的交通费用，除了第一种全程自驾会多出每天30047 / 25 研究生数学建模竞赛

元的租车费用外，其余的交通费用都一致；交通费用产生差异最大的地方是在从北京市到各个省会城市之间的旅程中，依据不同的自驾、高铁、航班产生不同的交通费用。又依据模型二中描述，要规划出能在10年游遍5A级景区的、费用最优、旅游体验最好的旅游路线。为了更好的建立模型，将旅游体验最好这个准则层量化成为旅行中在交通工具上所花费的时间最短。

对这两个准则层，在高校附近采用随机市场调查，填写问卷报告用联测法分析判断预测该地区人群对旅行中的这两个准则层的权重，加权予以权衡这两个指标，从而得出从北京到其他省会的最佳交通方式，然后运用Java程序设计出十年内从北京出发游遍所有5A级景区、费用最优、旅游体验最好的旅游路线，随后中相关规定限制条件，规划出这十年间具体的旅游行程费用。

4.3.2 问题三主要模型的求解

对费用最优与旅游体验最好，旅游体验最好即量化为旅行中在交通工具上所花费的时间最短两个准则层，利用层次分析法，通过上述调查分别取其权重为

w10.3,w20.7。

权重和

Aw1*Mw2*T

考虑第一种出行方式（全程自驾）：

mˆm

ˆmTA1w1D1m1D20.6Pmw2t考虑第二种出行方式（北京高铁到省会城市，后自驾）

mmmmˆm

ˆmTA2w1Pw2t13t1t2300P

考虑第三种出行方式（北京航班到省会城市，后自驾）

m300Pmw2tˆmTˆm

A3w1P2m3t1mt2m依据附件2、3及查阅百度地图相关信息可统计出D1m,D2的数据，利用模型二的算法求解得出常住地在北京市的自驾爱好者十年的旅游计划（见表8），此模型可推广至全国任意省会市或地区作为常住点，利用该算法求解出旅行者相应的十年旅行计划。

48 / 25 研究生数学建模竞赛

表8：模型三的十年旅行规划表

旅行年数旅行次数旅行地方

1 4 北京天津山西内蒙古

2 4 辽宁吉林黑龙江上海

3 3 江苏浙江广西

4 4 安徽福建海南西藏

5 3 江西山东湖南

6 3 河南湖北青海

7 3 广东重庆贵州

8 3 四川云南陕西

9 3 甘肃宁夏新疆

4.3.3 问题三给旅游者和旅游部门的建议

随着中国国民经济的不断增长，居民生活水平日益提高，旅游服务业及相关产业规模越来越完善。近年来不断兴起的“旅游热”、“自驾潮”“间隔年”，使得居民对旅游产业需求越来越大，国民的旅游消费行为也因此变得多元化，有更多倾向于个性化的过程。我国服员辽阔，国家评定的5A级旅游景区遍布全国31个省市州。再加上旅游者的不足、旅游时间不够灵活，旅游经费有限。要想在最短的时间内游遍201个5A级景点，提前做好旅游规划相当有必要，但目前我国居民对旅行缺乏具体规划观念。针对上述三个问题模型的求解分析，并针对我国旅游业发展状况给旅游爱好者和旅游相关部门提出以下建议。

4.3.3.1 针对旅游爱好者的建议：

1.在旅行开始前，针对自己预期旅游费用、旅行时间及期望目的地，从网络查找各类有用资源进行整合，如蚂蜂窝、百度旅游、途牛旅行网等，然后自己做一份详细的旅行规划表。这能从极大程度上节约旅行成本及旅行时间。同时也能增长对旅游地人文知识的了解。

2.自驾旅游者应该严格控制每天自驾时间，避免疲劳驾驶，同时关注天气变化、路况、车况及路线拥堵情况的实时信息，提前标记沿途加油站及时补及汽车燃油。注意旅途中行车安全，谨记交通法规。

3.鉴于旅游出行方式多样化，可根据旅游者自身旅游时间及旅游预期费用，综合比较后合理选择出行方式。比如从北京到拉萨若选择自驾，按每天8小时驾驶时间计算，来回至少需要十天自驾时间，这期间将产生大笔的旅游费用（燃油费、过路费、食宿费等）。这时就可选择乘坐飞机。

4.3.3.2 针对旅游相关部门的建议：

1.每个旅游者都有自己关于旅行天数、费用、出游方式、景区级别、目的地及景区性质的不同预期，然而市面上尚没有基于旅游爱好者个性化的旅游行程规划服务，旅游部门应该注重对旅游者个性化旅游行程规划服务产业的开发，让用户在提供以上旅行的约束条件后，能依据用户需求制定出详细的行程安排表，也即基于用户生成数49 / 25 研究生数学建模竞赛

据的旅游线路规划，让旅行规划个性化和实用化。

2.目前能提供的都是景区间的旅游规划，关于景点内部的线路选择和时间分配是个空白，需要旅游相关部门做工作加以完善，给旅游者提供更加全面的信息。

3.每个旅游景区都有一个最大游客容纳量，为了更好分散游客避免个别景区拥堵现象，旅游部门可利用手机GPS定位，为旅游者提供实时景点人数及景区附近地理位置图等及时反馈信息。

4.4 问题三模型的建立和求解

4.4.1 问题三模型的建立

用现有的蚁群算法对线路规划将使得景区的负载不均衡，若采用这种算法得到的最优路径旅游必然导致某些景点人数激增，而部分景点人数却很少。考虑改进蚁群算法，加入动态规划，将每个景区对游客的容纳量及t时刻景区的人流量加入其中，从而可以很好的实现旅游景区的负载均衡。问题四中在问题三的基础上加入了国家4A级景区，考虑旅游者的旅行时间及旅行费用均有限的情况下，要尽可能多的去游览附件1和附件7中的国家级5A和4A级风景区。即在给定时间和费用前提下，游览更多景点。因此模型的目标函数为：

Maxn

设为给定的旅行时间，为给定的旅行费用就有了约束条件。又通过对附件6、附件7的分析我们发现国家5A级景区和国家4A级景区太多，所以我们不能一次旅行完所有的景区，我们采用模型一的方法对全国各地的景区按省分块进行旅行，由于省内的景点也很多，并且旅行者受每次旅行时间的限制，不可能游完省内所有的4A和5A级景点。又因为当旅游者游览完第m个省的第i个景点后，在决策接下来是否该去第j个旅游景点时，将受到第j个旅游景点的该时刻的旅客流量，从景点i到景点j的景区路线长度及当前剩余旅游费用的限制。所以考虑这三个影响因素对旅游者决策的影响。

依据景点在t时刻游客流量及其承载量，定义以下游客量的函数关系式：

i(t)

P1imax如果P1越大，则说明景区在t时刻的游客能承载的游客流量越多，相反P1越小，则说明t时刻的游客流量越少。

对于从景点i到景点j的景区路线长度，定义以下线路函数关系式：

P2Li

L如果P2越大则说明景点i距离景点j的旅游路线越长，相反P2越小说明景点i距离景点j的旅游路线越短。

50 / 25 研究生数学建模竞赛

对于旅游费用方面，定义了以下函数关系式：

j(t)

P31j如果P3越大说明前几个地点花费的费用越多，当前所剩旅游费用越少；相反P3越小则说明旅游者在这之前旅行中花费越少。

由以上函数关系式知因变量和自变量成正比，由此旅行者在游览完第i个旅游景点后便能够依据以下01判别式来做决策是否接下来去第j个旅游景点游览：

1xi0P1P2P30.53

P1P2P30.53如果xi1表示接下来去第j个旅游景区xi表示接下来是否去第j个旅游景区游览，游览，若xi0则表示不去。

由此便可以动态的求解得出该省内哪些景区是要去的，哪些景区是不被旅行者考虑的。也即动态的产生出该省内的旅游路线的规划。然后将这31个省份看成节点，再运行模型一中编写的java语言求解出具体的旅行规划路线。

举例说明动态规划过程如下：

如某省内有A1,A2,A3,A4四个景区，从A1景区出发，按上述改进后的蚁群算法在A2,A3,A4景点中按顺序筛选出符合如何01判别式的景区A2，然后从重复筛选过程从A3,A4中筛选，直到把省内所有景区按序筛选完毕。

图4：动态规划过程图

51 / 25 研究生数学建模竞赛

五、模型的优缺点

5.1 模型的优点

1.本文正确、清楚地分析了题意的基础上，建立了合理、科学的数学模型。对旅游线路的设计进行了合理的假设，简化了一些不必要的因素，把问题转化成图论中TSP问题，利用Lingo软件，大大减少了计算过程。

2.在所建的模型中以旅行时间为基础，考虑了旅行中不能忽视的费用问题，考虑两者不能同时兼顾，采用层析分析法加权计算，符合实际情况。

3.在问题四中将建立的线路规划模型中，该算法考虑了各个景区的最大游客容纳量及t时刻景区的游客量，提出了路线的动态规划算法。考虑了与实际密切联系，并且结合实际解决问题，使得模型具有很好的广泛性和适用性。

5.2 模型的缺点

1.在模型中的景区游览时间只考虑了旅游者在各个景区的最少逗留时间，以及假设交通通畅、等待交通工具的时间忽律不计，在各个省份内的旅游均考虑为从省会城市出发，这些使得我们的模型有一定的局限性。如要作为旅游规划的参考，还需进一步深入研究。

2.模型中线路设计时所考虑的因素还可以加入交通状况、旅游者年龄、身体状况、旅行者的心理因素及满意度等。

3.由于时间有限，针对问题四中5A及4A级国家风景区的规划中对多种交通方式的并行使用情况下旅游线路规划问题的思考还不是很成熟。

参考文献

[1] 尹华罡，基于海量时空数据的路线挖掘与检索[D]，中国科学技术大学，2013.1

[2]司守奎，孙奎菁，数学建模算法与应用[M]，北京：国防工业出版社，2001.8：

37-82

[3]曹旭，旅游线路优化设计研究2012 [D].，西北民族大学，2013.5

[4]姜启源，谢金星，叶俊，数学模型(第四版) [M]，北京：高等教育出版社，2011.1

[5]王庚，王敏生，现代数学建模方法[M]，北京：科学出版社，2008：82-121

[6] 王徐民，方玉平,，张慧慧,，旅游线路优化设计[J]，中国矿业大学，2012.8

[7]佟欣，孙仲强，徐斌，黑龙江省旅游路线优化设计[J]，大庆师范学院，2000.9

[8]曹旭，马茜，马少仙，最短路问题在旅游线路优化中的应用[J]，科技广场，2012.2

[9] 栗雪娟，崔尚森，张柯，最佳旅游路线选择的神经网络方法[J]，长安大学

[10]徐锋，基于PDA的旅游导航系统的研究与实现[D]，北京邮电大学网络，2011

52 / 25 研究生数学建模竞赛

[11]百度地图，网站：

附录

山西省内最短路径Lingo运行结果如下：

论文中的模型所用程序如下：

程序1：

model:

sets:

city/1..7/:u;!u(i)=sequence city;

link(city,city):

dist,! the distance matrix;

x;! x(i,j)=1 if we use link i,j;

endsets

data:! distance matrix,it need not be symmetric;

dist=

276

344

135

107

;

enddata

276

257

620

411

361

382

257

531

322

272

293

344

620

531

299

351

324

135

411

322

299

361

272

351

107

382

293

324

! the model:hers&laporte,or letters,feb.91;

53 / 25 研究生数学建模竞赛

n=@ size(city);

min=@ sum(link:dist*x);

@ for(city(k):

!it must be entered;

@ sum(city(i)|i#ne#k:x(i,k))=1;

!it must be departed;

@ sum(city(j)|j#ne#k:x(k,j))=1;

!weak form of the subtour breking constraints;

!these are not very powerful for large problems;

@ for(city(j)|j#gt#1#and#j#ne#k:

u(j)>=u(k)+x(k,j)-(n-2)*(1-x(k,j))+(n-3)*x(j,k)));

!make the x\'s 0/1;

@ for(link:@ bin(x));

!for the first and last stop ;

@ for(city(k)|k#gt#1:

u(k)<=n-1-(n-2)*x(1,k);

u(k)>=1+(n-2)*x(k,1));

End

程序2：（java程序）

package Hmath;

//此程序用于实现将几个省分在一年旅行，分法必须保证每次旅行不超过15天，一年不过4次，一年总天数不超过30天

public class array {

public static void main(String[] args) {

int[] s={8 ,9 ,8 ,4 ,5 ,5,

0 ,10 ,10 ,12 ,11 ,11 ,10 ,10 ,13 ,13 ,10 ,10 ,6 ,5 ,10 ,13 ,6 ,10 ,3 ,7 ,9 ,5 ,4 ,14};//初始化数组

int[] x=new int[30];

for (int i = 0; i < ; i++) {

}

x[i]= 0;

int sum=0;

int y=0;

for (int i = 0; i < ; i++) {

n(\"%%%%%\"+sum);

if (sum<=30&&x[i]==0&&y<=3) {

sum=sum+s[i];

y++;

x[i]=1;

(\"#\"+i+\"# \"+s[i]+\" \");

}

54 / 25 研究生数学建模竞赛

}

for (int j = i+1; j < ; j++) {

}

if (sum<=30&&y<=3&&x[j]==0) {

}

if (j==-1) {

}

n(sum+\" ffff \");

sum=0;

sum=sum+s[j];

if (sum<=30) {

}

(\"#\"+j+\"# \"+s[j]+\" \");

x[j]=1;

y++;

sum=sum-s[j];

}else {

y=0;

55 / 25

更多推荐

旅游,景区,时间,旅行,问题

研究生数学建模竞赛

发布评论取消回复

最近发表

热门文章

标签列表

研究生数学建模竞赛

相关文章

发布评论取消回复

最近发表

热门文章

标签列表