利用Floyd 算法優(yōu)化設(shè)計(jì)旅游路線
——以蘇州市為例

趙 強(qiáng)，沈正平，史春云，葉 青

（1. 江蘇師范大學(xué)地理測繪與城鄉(xiāng)規(guī)劃學(xué)院，江蘇 徐州 221000；2. 閩江學(xué)院海洋學(xué)院，福建 福州 350000）

隨著社會的發(fā)展，人們生活水平和經(jīng)濟(jì)能力不斷提高，促使旅游需求不斷增加。旅游活動屬于消費(fèi)活動，其目的是消遣、追求享受，因此應(yīng)對旅行體驗(yàn)加以關(guān)注。交通成本是旅行成本中最具優(yōu)化價值的成本因素之一，科學(xué)的路線規(guī)劃可大大減少通行成本，從而提高旅行過程中的游行比，即游覽過程成本與旅游全程成本之比[1]。近年來，關(guān)于旅游路線規(guī)劃的研究熱度持續(xù)攀升，分析知網(wǎng)中相關(guān)文獻(xiàn)發(fā)現(xiàn)，針對旅游路線規(guī)劃的研究自2006年開始逐漸興起，并呈螺旋式上升、波浪式前進(jìn)，2019年研究熱度出現(xiàn)了高峰；新冠疫情的影響導(dǎo)致旅游活動熱情減退，旅游路線的研究減少，但隨著疫情在我國甚至世界范圍內(nèi)得到相應(yīng)控制，對旅游活動的熱情將會恢復(fù)，旅游需求會更加旺盛，因此關(guān)于旅游路線的研究必不可少。然而，利用科學(xué)模型對旅游路線進(jìn)行規(guī)劃的研究較少，在知網(wǎng)的相關(guān)文獻(xiàn)中能將科學(xué)數(shù)理模型與研究主題相結(jié)合的文獻(xiàn)寥寥無幾，雖然部分旅游路線規(guī)劃研究采用了Dijkstra算法或蟻群算法，但在實(shí)際案例應(yīng)用中，其推演過程與結(jié)果有時并不理想[2-4]。因此，選擇一個適合的、科學(xué)的數(shù)理模型并將其應(yīng)用于實(shí)際案例中是旅游路線規(guī)劃研究領(lǐng)域需要關(guān)注的重點(diǎn)。

1 Floyd算法及其推演過程

1.1 算法簡介

路徑規(guī)劃的經(jīng)典算法為Dijkstra 算法、Ford 算法、Floyd 算法和蟻群算法。Dijkstra 算法又稱貪心算法，其不足在于無法解決負(fù)權(quán)邊問題、規(guī)劃過程不具有動態(tài)性和推演過程中路徑結(jié)果不可回溯；蟻群算法則面臨計(jì)算量大、推算時間長、演算過程不可回溯等問題；Ford算法可以解決負(fù)權(quán)邊問題；Floyd算法不僅可解決負(fù)權(quán)邊問題，而且推演過程具有動態(tài)性，可在推演過程中不斷更新優(yōu)化路徑結(jié)果，且推算過程簡便[5-6]。

Floyd 算法又稱插點(diǎn)法，產(chǎn)生于20 世紀(jì)60 年代，2000年開始得到發(fā)展，并呈逐年攀升的態(tài)勢，2017年是其研究發(fā)展的高峰。該算法常被應(yīng)用于移動機(jī)器人路徑規(guī)劃、緊急疏散線路設(shè)計(jì)、軌道交通路網(wǎng)設(shè)計(jì)、物資配送等領(lǐng)域[7-11]。將Floyd 算法應(yīng)用于旅游路線規(guī)劃方面的研究較少，如楊柳[12]等以出發(fā)地為中心，在全國范圍內(nèi)劃分分支線，再以省會為中心，在省內(nèi)構(gòu)建游覽路線的哈密頓圈，即閉合的回路；但其研究尺度較宏觀，不注重微觀線路的優(yōu)化設(shè)計(jì)，且線路邊權(quán)值僅考慮空間距離，未考慮時間距離與經(jīng)濟(jì)距離。本文旨在利用Floyd 算法研究蘇州市旅游路線規(guī)劃，并從地理學(xué)角度對Floyd 算法的數(shù)據(jù)選取提出改進(jìn)建議，即并非單純指空間距離數(shù)據(jù)，而是空間、時間、經(jīng)濟(jì)綜合計(jì)算的結(jié)果。

1.2 Floyd算法推演

1.2.1 插點(diǎn)更新路徑推演

該算法的主要思想為：在起點(diǎn)到終點(diǎn)的路徑中插入一個中轉(zhuǎn)點(diǎn)，并計(jì)算從起點(diǎn)經(jīng)中轉(zhuǎn)點(diǎn)再到終點(diǎn)的路徑距離；若該距離小于直接從起點(diǎn)到終點(diǎn)的距離，則以插入中轉(zhuǎn)點(diǎn)的路徑取代原本路徑，從而達(dá)到更新優(yōu)化路徑的目的。具體演算步驟為：①確定從A點(diǎn)出發(fā)直接到達(dá)B點(diǎn)的路徑，并計(jì)算路徑距離，記為x；②在A、B 點(diǎn)之間插入C 點(diǎn)，確定從A 點(diǎn)出發(fā)經(jīng)C 點(diǎn)再到B點(diǎn)的路徑，并計(jì)算路徑距離，記為y=a+b，a為A點(diǎn)到C 點(diǎn)的距離，b為C 點(diǎn)到B 點(diǎn)的距離；③若y＜x，則以新路徑取代原本路徑，并輸出取代后的路徑，若x＜y，則保留原本路徑，并將該路徑輸出。

1.2.2 路徑循環(huán)更新推演

在插點(diǎn)更新路徑推演中，插入C點(diǎn)后，在該路徑中A 點(diǎn)到C 點(diǎn)也構(gòu)成了一條路徑，因此同樣可對A 點(diǎn)到C 點(diǎn)的路徑進(jìn)行更新優(yōu)化，具體步驟為：①記錄A點(diǎn)到C 點(diǎn)的路徑距離a；②在A、C 點(diǎn)之間插入D 點(diǎn)，確定從A 點(diǎn)出發(fā)經(jīng)D 點(diǎn)再到C 點(diǎn)的路徑，并計(jì)算路徑距離，記為w；③若w＜a，則以新路徑取代原本路徑，并輸出取代后的路徑，實(shí)現(xiàn)迭代更新，若a＜w，則保留原本路徑并輸出，路徑優(yōu)化結(jié)束（圖1）。同理，C點(diǎn)到B點(diǎn)的路徑也可利用該方法實(shí)現(xiàn)循環(huán)更新迭代。

圖1 Floyd算法路徑迭代優(yōu)化圖解

2 蘇州市旅游路線優(yōu)選方案

由于Floyd 算法采用的數(shù)據(jù)基礎(chǔ)是單純的空間距離，而在旅游線路規(guī)劃過程中，所需考慮的因素不只是實(shí)際空間距離，若將空間距離數(shù)據(jù)直接套用Floyd算法，其規(guī)劃的路徑將不盡完善[13]。因此，需對算法中數(shù)據(jù)選取進(jìn)行改進(jìn)。數(shù)據(jù)計(jì)算公式為：

式中，Dij、Lij分別為i點(diǎn)到j(luò)點(diǎn)的路徑邊權(quán)值和實(shí)際路程距離，Dij越小表明路徑花費(fèi)的成本越小，路徑越優(yōu)；T為路程中花費(fèi)的時間；C為路程中的費(fèi)用。

2.1 景點(diǎn)間路徑的確定

蘇州是一座美麗的城市，自古便有“上有天堂、下有蘇杭”的美譽(yù)，聞名前來旅游的游客絡(luò)繹不絕。蘇州市位于江蘇省南部，與上海市接壤。豐厚的江南文化底蘊(yùn)和獨(dú)特的江南景觀特征決定了蘇州市適合旅游業(yè)發(fā)展。如今旅游業(yè)發(fā)展正是繁榮時期，利用科學(xué)的算法模型，在蘇州市范圍內(nèi)進(jìn)行旅游路線優(yōu)化設(shè)計(jì)是有必要的。

蘇州市旅游資源眾多，據(jù)統(tǒng)計(jì)大小景點(diǎn)約有54個，但人們不可能游玩每個景點(diǎn)，只能選擇較典型或具有代表性的景點(diǎn)進(jìn)行游歷，以了解這座城市并感受其中文化。因此，本文以蘇州市范圍內(nèi)5A 級及以上景區(qū)為研究對象，利用Floyd 算法對其進(jìn)行旅游路線規(guī)劃設(shè)計(jì)，并對算法機(jī)制提出優(yōu)化建議。本文對選取的5A級景區(qū)進(jìn)行編號，即拙政園、留園、虎丘山風(fēng)景名勝區(qū)、金雞湖景區(qū)、太湖景區(qū)、同里古鎮(zhèn)、周莊古鎮(zhèn)、尚湖風(fēng)景區(qū)依次為1～8，各景區(qū)區(qū)位分布見圖2。

圖2 蘇州市5A景區(qū)分布圖

駕車出行是目前旅游過程中較便捷的選擇，因此本文定義出行方式為駕車通行。根據(jù)式（1）計(jì)算各景點(diǎn)之間兩兩通達(dá)的路徑邊權(quán)值，數(shù)據(jù)均依據(jù)駕車標(biāo)準(zhǔn)獲取；并將所得數(shù)據(jù)記錄到矩陣中。矩陣的行和列分別代表起點(diǎn)和終點(diǎn)，矩陣的行數(shù)和列數(shù)分別代表景點(diǎn)編號數(shù)[14]，如第三行第四列的數(shù)據(jù)代表從3 號景點(diǎn)出發(fā)到4 號景點(diǎn)的路徑邊權(quán)值，即從虎丘山風(fēng)景名勝區(qū)出發(fā)到金雞湖景區(qū)的路徑邊權(quán)值。本文選取了8 個景點(diǎn)研究對象，因此需設(shè)置一個8 點(diǎn)的矩陣來裝載算法推演過程中所得出的路徑邊權(quán)值數(shù)據(jù)。

2.2 景點(diǎn)間路徑距離更新迭代

由于在兩個景點(diǎn)之間插入一個中轉(zhuǎn)點(diǎn)后，通行所花費(fèi)的實(shí)際距離、時間和費(fèi)用都有可能發(fā)生變化，因此此時的路徑邊權(quán)值也可能發(fā)生變化，需要對矩陣進(jìn)行更新迭代，即在插入中轉(zhuǎn)點(diǎn)后得到新路徑，根據(jù)公式推算新路徑的路徑邊權(quán)值，若新的路徑邊權(quán)值比原值小，則將新數(shù)據(jù)取代矩陣中相應(yīng)的舊數(shù)據(jù)；反之，則保留矩陣中的舊數(shù)據(jù)[15]。將各景點(diǎn)的路徑邊權(quán)值數(shù)據(jù)匯總整合到Floyd 矩陣，并不斷進(jìn)行更新優(yōu)化迭代，其路徑邊權(quán)值矩陣結(jié)果見圖3，其中∞表示兩地之間無法直接通達(dá)，必須中轉(zhuǎn)才可到達(dá)；0 表示兩地之間通達(dá)距離為0，即未發(fā)生位移。

圖3 路徑邊權(quán)值矩陣結(jié)果

2.3 最優(yōu)方案選擇

旅游路線規(guī)劃的最終目標(biāo)是形成哈密頓圈，即閉合回路。由于已得到更新迭代后的城市間路徑邊權(quán)值矩陣，只需科學(xué)選取和排列矩陣中的數(shù)據(jù)即可得出完整的路線規(guī)劃。數(shù)據(jù)處理時應(yīng)滿足的原則為：①不選取對角線上的數(shù)據(jù)，矩陣對角線代表起點(diǎn)和終點(diǎn)相同，數(shù)據(jù)無意義；②選取的數(shù)據(jù)行數(shù)、列數(shù)各不相同，線路規(guī)劃中每個地方只經(jīng)歷一次，不可能出現(xiàn)一個地方作為起點(diǎn)對應(yīng)多個終點(diǎn)或終點(diǎn)對應(yīng)多個起點(diǎn)的情況；③不可出現(xiàn)行數(shù)、列數(shù)互為相反的情況，該情況意味著在兩地間往返，無法到達(dá)其他景點(diǎn)，而陷入死循環(huán)路徑，這在旅行過程中是不現(xiàn)實(shí)的；④排列數(shù)據(jù)時，前一個數(shù)據(jù)的列數(shù)與后一個數(shù)據(jù)的行數(shù)應(yīng)相同，旅游路線中的每個地方均是前一個地方的終點(diǎn)和后一個地方的起點(diǎn)，并以此不斷循環(huán)往復(fù)進(jìn)行。

Python 是一門應(yīng)用場景廣泛的編程語言，具有開源、靈活等特點(diǎn)，擁有龐大的第三方庫，常被用于數(shù)據(jù)運(yùn)算處理，在矩陣數(shù)據(jù)運(yùn)算方面具有很大優(yōu)勢。利用Python 程序的第三方庫可實(shí)現(xiàn)上述數(shù)據(jù)處理原則，將利用Floyd 算法處理好的矩陣數(shù)據(jù)導(dǎo)入程序的第三方庫中，便可在程序內(nèi)部自行實(shí)施運(yùn)算并輸出最終結(jié)果（具體路線和路徑邊權(quán)值）見表1。

表1 路徑輸出結(jié)果

根據(jù)結(jié)果選出邊權(quán)值最小的路徑，得到路線規(guī)劃最優(yōu)方案，即拙政園→留園→虎丘山風(fēng)景名勝區(qū)→金雞湖景區(qū)→同里古鎮(zhèn)→周莊古鎮(zhèn)→太湖景區(qū)→尚湖風(fēng)景區(qū)→拙政園，全程路徑邊權(quán)值為382（圖4）。

圖4 最優(yōu)路線哈密頓圈

3 結(jié) 語

Floyd 算法是經(jīng)典的路徑規(guī)劃算法，部分學(xué)者將其應(yīng)用于路徑規(guī)劃研究中，并提供了精確的編程代碼，但缺少關(guān)于路徑邊權(quán)值矩陣數(shù)據(jù)的處理方法。

1）本文將Floyd 算法與旅游路線規(guī)劃研究相結(jié)合，路線規(guī)劃方案利用具體算法模型求得，因此結(jié)論具備一定的科學(xué)性和可行性。路線規(guī)劃過程中得出的旅游路線是一個哈密頓圈，即閉合回路，旅游者可從任何方位進(jìn)入該旅游區(qū)域開始其旅游行程，這為旅游活動帶來了許多便利。

2）本文提出了優(yōu)化路徑邊權(quán)值數(shù)據(jù)的思想。從地理學(xué)的角度來看，距離包括空間距離、時間距離和經(jīng)濟(jì)距離。隨著科學(xué)技術(shù)和交通水平的提高，空間距離在人們出行中的限制力度大大減弱，人們出行時更加傾向于關(guān)注便捷程度，因此出行時人們更多的是考慮時間距離和經(jīng)濟(jì)距離的影響。傳統(tǒng)Floyd 算法邊權(quán)值數(shù)據(jù)只考慮空間距離，這在本文中得到了改進(jìn)。該算法的優(yōu)化不僅限于地理學(xué)旅游路線規(guī)劃領(lǐng)域的研究，還可根據(jù)需要，對數(shù)據(jù)進(jìn)行科學(xué)地調(diào)整，將其推廣應(yīng)用于其他領(lǐng)域的研究。

3）本文提供了路徑邊權(quán)值矩陣數(shù)據(jù)的處理方法。本文在前人研究的基礎(chǔ)上提出了對邊權(quán)值矩陣中數(shù)據(jù)進(jìn)行選取和編排的規(guī)則方法，并應(yīng)用于計(jì)算機(jī)自動化運(yùn)算。目前自動化運(yùn)算研究還不完全成熟，仍存在不足，如在處理邊權(quán)值矩陣數(shù)據(jù)時，由于編程解釋器生成的隨機(jī)數(shù)是“偽隨機(jī)數(shù)”而非“真隨機(jī)數(shù)”，導(dǎo)致在利用該方法進(jìn)行自動化運(yùn)算時一次只能生成一條路徑，要得出最佳路徑只能人工計(jì)算其路徑邊權(quán)值，不能做到完全自動化。后續(xù)電子信息技術(shù)領(lǐng)域中編程解釋器“隨機(jī)數(shù)”機(jī)制的完善或編程運(yùn)算的優(yōu)化，可使解決該問題成為可能，這也是今后研究中努力突破的方向。