利用Floyd 算法優化設計旅游路線
——以蘇州市為例

趙 強，沈正平，史春云，葉 青

（1. 江蘇師范大學地理測繪與城鄉規劃學院，江蘇 徐州 221000；2. 閩江學院海洋學院，福建 福州 350000）

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

1 Floyd算法及其推演過程

1.1 算法簡介

路徑規劃的經典算法為Dijkstra 算法、Ford 算法、Floyd 算法和蟻群算法。Dijkstra 算法又稱貪心算法，其不足在于無法解決負權邊問題、規劃過程不具有動態性和推演過程中路徑結果不可回溯；蟻群算法則面臨計算量大、推算時間長、演算過程不可回溯等問題；Ford算法可以解決負權邊問題；Floyd算法不僅可解決負權邊問題，而且推演過程具有動態性，可在推演過程中不斷更新優化路徑結果，且推算過程簡便[5-6]。

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

1.2 Floyd算法推演

1.2.1 插點更新路徑推演

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

1.2.2 路徑循環更新推演

在插點更新路徑推演中，插入C點后，在該路徑中A 點到C 點也構成了一條路徑，因此同樣可對A 點到C 點的路徑進行更新優化，具體步驟為：①記錄A點到C 點的路徑距離a；②在A、C 點之間插入D 點，確定從A 點出發經D 點再到C 點的路徑，并計算路徑距離，記為w；③若w＜a，則以新路徑取代原本路徑，并輸出取代后的路徑，實現迭代更新，若a＜w，則保留原本路徑并輸出，路徑優化結束（圖1）。同理，C點到B點的路徑也可利用該方法實現循環更新迭代。

圖1 Floyd算法路徑迭代優化圖解

2 蘇州市旅游路線優選方案

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

式中，Dij、Lij分別為i點到j點的路徑邊權值和實際路程距離，Dij越小表明路徑花費的成本越小，路徑越優；T為路程中花費的時間；C為路程中的費用。

2.1 景點間路徑的確定

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

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

圖2 蘇州市5A景區分布圖

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

2.2 景點間路徑距離更新迭代

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

圖3 路徑邊權值矩陣結果

2.3 最優方案選擇

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

Python 是一門應用場景廣泛的編程語言，具有開源、靈活等特點，擁有龐大的第三方庫，常被用于數據運算處理，在矩陣數據運算方面具有很大優勢。利用Python 程序的第三方庫可實現上述數據處理原則，將利用Floyd 算法處理好的矩陣數據導入程序的第三方庫中，便可在程序內部自行實施運算并輸出最終結果（具體路線和路徑邊權值）見表1。

表1 路徑輸出結果

根據結果選出邊權值最小的路徑，得到路線規劃最優方案，即拙政園→留園→虎丘山風景名勝區→金雞湖景區→同里古鎮→周莊古鎮→太湖景區→尚湖風景區→拙政園，全程路徑邊權值為382（圖4）。

圖4 最優路線哈密頓圈

3 結 語

Floyd 算法是經典的路徑規劃算法，部分學者將其應用于路徑規劃研究中，并提供了精確的編程代碼，但缺少關于路徑邊權值矩陣數據的處理方法。

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

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

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