自駕游河南省5A景區(qū)的最短路線優(yōu)化設計模型

王軍濤 梅書濤

摘要：本文通過參考國家旅游局網站，收集到河南省5A景點的相關信息，根據收集得到的大量數據進行統(tǒng)計，利用任意兩點間的最短路徑法與固定起點的最短路徑法，運用Floyd算法得到旅游5A景點中由某一景點出發(fā)途經若干個景點的最短行程路線，彌補了導航系統(tǒng)的不足，為自駕旅游的游客提供借鑒與幫助。

關鍵詞：河南5A景點；最短路徑法；Floyd算法

一、引言

隨著科學技術的發(fā)展、人們生活水平的提高，旅游逐漸成為人們改善生活質量的一種方式，越來越多的人開始利用節(jié)假日自駕游。同時河南省作為中華民族與華夏文明的發(fā)源地，也是建都朝代最多、建都歷史最長、古都數量最多的省份，自古就有“天下名人，中州過半”之說，因此大量的旅游愛好者慕名前來。為了更好的服務游客，如何設計出一條關于游客自任一5A級景點出發(fā)，游覽本人感興趣部分5A級景點或者全部的5A級景點的旅行路線，使得行程最短，進而可以避免因多繞路而耽誤時間。因此這是一個值得關注和研究的問題。

本文考慮自駕游是以任一景點為出發(fā)點展開旅游且游遍自己感興趣所有景點之后不需要返回出發(fā)點，參考國家旅游局網站[1]給出的準確信息可確定河南省的5A級景區(qū)為13個，通過百度地圖網站[2]搜索各個景點之間的最短距離利用Excel建立任意兩景點間距離的相關表格，隨后可根據數據結果畫出網絡圖，建立鄰接矩陣。

為了敘述的方便和游覽河南5A景點的全面性，我們假定將嵩山少林寺景點設置為起點，其余12個景區(qū)設為單位點，可以找到該固定點到其余點間的最短距離；再在MATLAB里輸入Floyd算法[3]的函數程序即可得到不重復經過所有點的距離矩陣和路徑矩陣，分析處理所得到的距離矩陣與路徑矩陣，得到最短距離與最短路徑。從而我們找到了一條游覽河南省13個5A級景區(qū)距離最短最佳路線。

二、文中符號說明

文中的符號含義：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），找到與之對應的景點名稱，得到旅游最優(yōu)路線設計為：嵩山少林寺龍門石窟雞冠洞龍?zhí)洞髰{谷中原大佛景區(qū)白云山老界嶺嵖岈山景區(qū)清明上河園云臺山紅旗渠風景區(qū)殷墟芒碭山。最短路線長為1915.8千米。

四、模型的優(yōu)缺點

1）該模型首先改進導航的不足，導航的性能僅僅提供任意兩點間的優(yōu)化路線，而不能提供途經多個地點的最短線路。

2）本論文研究的是旅游景點的優(yōu)化路線，但論文的研究方法可以用于類似于最短線路的不同問題。譬如安全巡視員巡視安全隱患點、景區(qū)講解員給游客講解景點內容、郵遞員投放不同單位的信件等均可運用最短路來解決。

3）本模型在積累大量游客信息數據的官方網站上精確統(tǒng)計數據結果，為模型提供了事實論據，使模型具有嚴謹性與普適性。

4）論文提供了游覽13個5A景點的最短路線，如果游客僅對13個5A景點中部分景點感興趣，參照上述算法可以更快速的找到自己感興趣景點的最優(yōu)路線。

5）該模型僅考慮從一點出發(fā)，途經所有需要經過的點，到最后一個點結束，而沒有考慮如何再回到出發(fā)點，即沒有考慮返還的情況。另外該模型也沒有提供如何使路線最短且消費最低的最佳線路，因消費最低涉及到景點不同時期門票價格的變化及住宿價格的波動等因素的影響，不容易確定，這也是我們接下來要研究與探討的問題。

參考文獻：

[1]國家旅游局網站：https：//baike.baidu.com/item/國家AAAAA級旅游景區(qū)/3575094？fr=aladdin&fromid= 4413098&fromtitle=5A級旅游景區(qū)#7

[2]百度地圖網站：http：//map.baidu.com/

[3]趙禮峰，黃奕雯.基于矩陣自定義運算的Floyd改進算法[J].計算機技術與發(fā)展，2016，26（10）：41-44.

[4]葉其孝，姜啟源等.數學建模（第5版）[M]，北京，機械工業(yè)出版社，2014.

[5]楊柳，李苗苗，程越等.基于Floyd算法的旅游線路優(yōu)化[J].電子科技，2017，30（1）：76-79.

[6]袁光輝，謝科，鄧林勝等.旅游路線動態(tài)規(guī)劃問題研究——以西安市出發(fā)為例[J].數學的實踐與認識，2016，46（15）： 125-133.

[7]徐婷婷，王柱，徐海洋等.旅游路線規(guī)劃數學模型的建立與應用探討[J].廊坊師范學院學報（自然科學版），2016，16（1）：23-26.

[8]劉忠花，李憲印，于婷等.基于三階段TSP算法的旅游路線規(guī)劃[J].曲阜師范大學學報（自然科學版）， 2016，42（4）：11-16.

[9]陳雅良，溫朝暉，周浩然等.基于Floyd算法對交通流最優(yōu)路徑選擇的研究[J].佳木斯大學學報（自然科學版），2016，34（6）：917-919.

[10]張宗浩.“暢游中國”--旅游路線規(guī)劃問題[J].卷宗，2016，（7）：1006-1007.

作者簡介：王軍濤（1980-），男，河南南陽人，碩士，副教授，主要最優(yōu)化算法及其應用研究。

基金項目：河南科技學院2018年大學生創(chuàng)新訓練計劃項目（2018CX70）。