王軍濤 梅書濤

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

關(guān)鍵詞：河南5A景點；最短路徑法；Floyd算法

一、引言

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

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

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

二、文中符號說明

文中的符號含義：1、用vi（i=1，2，…，13）表示景點名稱依次排序；2、邊（vi，vj）（i，j=1，2，…，13）表示從一個景點到另一個景點的距離，單位為：千米（km）。

三、數(shù)學(xué)模型的建立與求解

3.1模型的建立

通過搜索百度地圖網(wǎng)站，可以得到各個景點之間的最短距離，其中，從嵩山少林寺到龍門石窟的距離為56.4千米，從嵩山少林寺到白云山的距離為201.7千米等等依次排列，整理數(shù)據(jù)利用Excel建立任意兩景點間距離。如果我們設(shè)嵩山少林寺為v1，龍門石窟為v2等等，vi到vj之間的連線代表從一個景點到另一個景點的路徑，因此我們就可以做出不同景點間的網(wǎng)絡(luò)。利用不同景點間的距離數(shù)據(jù)我們可建立各個景點距離的鄰接矩陣w（i，j）：

下面我們使用Floyd算法來求任意兩點間的最短路。最后，將路徑矩陣中的數(shù)字1，2，…，13轉(zhuǎn)化成為上文中的vi（1，2，…，13），找到與之對應(yīng)的景點名稱，得到旅游最優(yōu)路線設(shè)計為：嵩山少林寺龍門石窟雞冠洞龍?zhí)洞髰{谷中原大佛景區(qū)白云山老界嶺嵖岈山景區(qū)清明上河園云臺山紅旗渠風(fēng)景區(qū)殷墟芒碭山。最短路線長為1915.8千米。

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

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

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

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

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

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

參考文獻(xiàn)：

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

[2]百度地圖網(wǎng)站：http：//map.baidu.com/

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

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

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

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

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

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

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

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

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

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