王军涛 梅书涛

摘要：本文通过参考国家旅游局网站，收集到河南省5A景点的相关信息，根据收集得到的大量数据进行统计，利用任意两点间的最短路径法与固定起点的最短路径法，运用Floyd算法得到旅游5A景点中由某一景点出发途经若干个景点的最短行程路线，弥补了导航系统的不足，为自驾旅游的游客提供借鉴与帮助。

关键词：河南5A景点；最短路径法；Floyd算法

一、引言

随着科学技术的发展、人们生活水平的提高，旅游逐渐成为人们改善生活质量的一种方式，越来越多的人开始利用节假日自驾游。同时河南省作为中华民族与华夏文明的发源地，也是建都朝代最多、建都历史最长、古都数量最多的省份，自古就有“天下名人，中州过半”之说，因此大量的旅游爱好者慕名前来。为了更好的服务游客，如何设计出一条关于游客自任一5A级景点出发，游览本人感兴趣部分5A级景点或者全部的5A级景点的旅行路线，使得行程最短，进而可以避免因多绕路而耽误时间。因此这是一个值得关注和研究的问题。

本文考虑自驾游是以任一景点为出发点展开旅游且游遍自己感兴趣所有景点之后不需要返回出发点，参考国家旅游局网站[1]给出的准确信息可确定河南省的5A级景区为13个，通过百度地图网站[2]搜索各个景点之间的最短距离利用Excel建立任意两景点间距离的相关表格，随后可根据数据结果画出网络图，建立邻接矩阵。

为了叙述的方便和游览河南5A景点的全面性，我们假定将嵩山少林寺景点设置为起点，其余12个景区设为单位点，可以找到该固定点到其余点间的最短距离；再在MATLAB里输入Floyd算法[3]的函数程序即可得到不重复经过所有点的距离矩阵和路径矩阵，分析处理所得到的距离矩阵与路径矩阵，得到最短距离与最短路径。从而我们找到了一条游览河南省13个5A级景区距离最短最佳路线。

二、文中符号说明

文中的符号含义：1、用vi（i=1，2，…，13）表示景点名称依次排序；2、边（vi，vj）（i，j=1，2，…，13）表示从一个景点到另一个景点的距离，单位为：千米（km）。

三、数学模型的建立与求解

3.1模型的建立

通过搜索百度地图网站，可以得到各个景点之间的最短距离，其中，从嵩山少林寺到龙门石窟的距离为56.4千米，从嵩山少林寺到白云山的距离为201.7千米等等依次排列，整理数据利用Excel建立任意两景点间距离。如果我们设嵩山少林寺为v1，龙门石窟为v2等等，vi到vj之间的连线代表从一个景点到另一个景点的路径，因此我们就可以做出不同景点间的网络。利用不同景点间的距离数据我们可建立各个景点距离的邻接矩阵w（i，j）：

下面我们使用Floyd算法来求任意两点间的最短路。最后，将路径矩阵中的数字1，2，…，13转化成为上文中的vi（1，2，…，13），找到与之对应的景点名称，得到旅游最优路线设计为：嵩山少林寺龙门石窟鸡冠洞龙潭大峡谷中原大佛景区白云山老界岭嵖岈山景区清明上河园云台山红旗渠风景区殷墟芒砀山。最短路线长为1915.8千米。

四、模型的優缺点

1）该模型首先改进导航的不足，导航的性能仅仅提供任意两点间的优化路线，而不能提供途经多个地点的最短线路。

2）本论文研究的是旅游景点的优化路线，但论文的研究方法可以用于类似于最短线路的不同问题。譬如安全巡视员巡视安全隐患点、景区讲解员给游客讲解景点内容、邮递员投放不同单位的信件等均可运用最短路来解决。

3）本模型在积累大量游客信息数据的官方网站上精确统计数据结果，为模型提供了事实论据，使模型具有严谨性与普适性。

4）论文提供了游览13个5A景点的最短路线，如果游客仅对13个5A景点中部分景点感兴趣，参照上述算法可以更快速的找到自己感兴趣景点的最优路线。

5）该模型仅考虑从一点出发，途经所有需要经过的点，到最后一个点结束，而没有考虑如何再回到出发点，即没有考虑返还的情况。另外该模型也没有提供如何使路线最短且消费最低的最佳线路，因消费最低涉及到景点不同时期门票价格的变化及住宿价格的波动等因素的影响，不容易确定，这也是我们接下来要研究与探讨的问题。

参考文献：

[1]国家旅游局网站：https：//baike.baidu.com/item/国家AAAAA级旅游景区/3575094？fr=aladdin&fromid= 4413098&fromtitle=5A级旅游景区#7

[2]百度地图网站：http：//map.baidu.com/

[3]赵礼峰，黄奕雯.基于矩阵自定义运算的Floyd改进算法[J].计算机技术与发展，2016，26（10）：41-44.

[4]叶其孝，姜启源等.数学建模（第5版）[M]，北京，机械工业出版社，2014.

[5]杨柳，李苗苗，程越等.基于Floyd算法的旅游线路优化[J].电子科技，2017，30（1）：76-79.

[6]袁光辉，谢科，邓林胜等.旅游路线动态规划问题研究——以西安市出发为例[J].数学的实践与认识，2016，46（15）： 125-133.

[7]徐婷婷，王柱，徐海洋等.旅游路线规划数学模型的建立与应用探讨[J].廊坊师范学院学报（自然科学版），2016，16（1）：23-26.

[8]刘忠花，李宪印，于婷等.基于三阶段TSP算法的旅游路线规划[J].曲阜师范大学学报（自然科学版）， 2016，42（4）：11-16.

[9]陈雅良，温朝晖，周浩然等.基于Floyd算法对交通流最优路径选择的研究[J].佳木斯大学学报（自然科学版），2016，34（6）：917-919.

[10]张宗浩.“畅游中国”--旅游路线规划问题[J].卷宗，2016，（7）：1006-1007.

作者简介：王军涛（1980-），男，河南南阳人，硕士，副教授，主要最优化算法及其应用研究。

基金项目：河南科技学院2018年大学生创新训练计划项目（2018CX70）。