基于遺傳算法的旅游線路規劃研究

郭豐林

摘 要：本文針對當前重點關注的旅游路徑規劃問題，綜合利用圖論和智能算法的相關理論，通過建立TSP數學模型和使用遺傳算法對問題進行求解，得到了遍歷30個景點的時間最短、總距離最短的旅游路徑。結果表明該方法具有較好的有效性和實用性。

關鍵詞：旅游路徑規劃，TSP，遺傳算法

當前旅游業正朝著定制化、個性化方向發展，對旅游路徑的規劃也逐漸成為研究熱點。多數學者針對單一景區內的游人行走線路或針對長距離、大跨度的跨省、出境游路徑規劃展開研究，而忽略了受眾更廣，更貼近日常出行真實狀況的中遠途（不跨省）、短時間內（不超過1周）的自駕出行情況，本文正是針對該范圍內的中小型區域旅游展開研究，將上海及周邊多個景區構成的旅游目的地網絡作為研究對象，將路線規劃問題抽象成TSP問題并建立哈密頓回路的數學模型，通過傳統遺傳算法實現對該區域旅游路徑的規劃，幫助游客提升出行體驗。

一、提出問題

假設一游客計劃從上海出發，自駕游覽上海市及周邊共30個景區并最終回到出發地，根據出行需求，游客要遍歷每個景區且各個景區只能到訪一次，如何規劃路線可以使游客在最短時間內完成游覽目標。

根據問題，提出以下假設：

（1）每兩個景區之間都有直接接通的公路，不存在兩個景點間必須通過其他景點才能到達的情況，且連接各景區的公路均為直線。

（2）游客在景區間的移動過程全程自駕，且平均車速為40km/h。

（3）不考慮游客中途停車、用餐、夜間休息或其他突發因素造成的時間增加，且游客到達景區馬上開始游覽，沒有時間間隔。

（4）游客在各個景區內的游覽時間是固定的，不因到達的時刻不同而變化。

二、建立模型

TSP問題即旅行商問題，可描述為：已知n各城市坐標，一個商人從起點城市出發，經過且只經過每個城市一次，最后回到起點城市的最短路程。TSP問題屬于NP完全問題的一種，目前沒有精確算法可以找到最優解，只能找到有效地近似解。

TSP問題的數學描述為：在正權圖G（V，E）中，頂點集合V={1，2，…，n}，邊集合為E，d為城市i到城市j的距離矩陣，要找到最短路徑的回路，成為最佳哈密頓回路或最佳哈密頓圈。

三、算法實現

遺傳算法是模擬生物界“物競天擇，適者生存”的自然演化規律的一種隨機搜索方法，它將自然界繁殖、雜交、變異、競爭等概念引入算法當中，通過一組可行解進行交叉、變異、逆轉化等操作得到最優解，是一種全局最優算法。其基本思路為，首先對問題參數進行編碼，形成一定數量的染色體，即初始種群，然后計算種群的適應度，再利用迭代對初始種群進行交叉、變異等操作得到更加優秀（適應度更高）的種群，最終保留符合目標的最優群體。

在本例中，利用遺傳算法求解上述模型的主要步驟及部分代碼如下：

（1）編碼

在遺傳算法中，大部分時候采用二進制編碼方式，但在求解旅行商問題時最簡單最直接的編碼方式是基于結點順序進行編碼，如針對一個9個景點的旅游路徑3-2-6-4-8-9-5-1-7可直接用（3 2 6 4 8 9 5 1 7）進行編碼，直觀明了的情況下還可以滿足模型中的約束條件。

（2）初始化種群

隨機生成一個初始解，初始解的個數決定了初始化種群的數量，本文中設定初始解中個體的數量為NIND=30，同時設定最大迭代次數為GENMAX=500次。

（3）適應度函數

適應度函數是用來評判個體優劣性的唯一標準，是遺傳算法進行個體選擇的依據，通常適應度函數由目標函數轉化而來，當求解目標函數最小值時，一般使適應度值最大，因此采用目標函數的倒數值作為適應度值，本文模型中目標函數為總距離最短，因此適應度函數設置如下

?（4）選擇操作

選擇操作是使用輪盤賭的方式，從上一代種群中選擇較優秀的個體作為父代繁衍子代，父代個體被選擇的概率與其適應度值相關，適應度值越高，被選擇的概率越大，個體i被選擇的概率pi為

?（5）交叉操作

將上一步選擇的兩個個體作為父代進行交叉操作以產生新的子代，其方法是在[1，9]（以9個城市為例）之間隨機取兩個整數r1和r2，將r1和r2之間的部分交換，本文中設置交叉概率pc=0.8。

（6）變異操作

變異操作是指在新產生的子代個體上進行的變異操作，主要為了維持子代個體的多樣性，其方法是在[1，9]之間隨機取兩個整數r1和r2，將個體這兩個位置上的編碼數字互換。

（7）終止條件判定

本文的終止條件為迭代次數=GENMAX（最大迭代次數），否則返回步驟3進行循環。

四、結果分析

根據以上遺傳算法模型，利用MATLAB編程進行模擬求解，得到結果在第462代的到最優結果，最優路徑為1-2-19-20-10-21-18-3-9-11-7-8-14-15-24-25-26-29-28-27-23-22-16-17-30-12-13-4-5-6-1，總距離為459.86km，計算后可得游客在旅途路上（不包括游覽時間）所用的最短時間為11.5h。對結果分析可知，該模型和算法大大縮短了總路程，根據問題描述和假設，得到了最短距離、最短時間游覽全部景點的路徑，該問題得到解決，可見遺傳算法對于解決TSP旅游路徑規劃問題效果顯著。

總結與展望

本文首先將旅游規劃問題轉換成TSP問題，然后建立混合整數規劃模型，最后利用遺傳算法設計程序并求解該問題，高效便捷的解決了旅游線路規劃問題。但本研究結果仍存在不足，如當景點數量n過大時，遺傳算法求解效率會大幅降低，此時可以考慮將其他近似算法與遺傳算法相結合提高求解效率，這些內容有待進一步研究。

參考文獻：

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

[2] 喻? 菡.遺傳算法求解TSP的研究[D].西南交通大學，2006.

[3] 鄭天翔.基于動態實時調度的主題公園游客時空分流導航管理研究[J].旅游科學，2012，26（4）：8-16.

[4] 鄭天翔，吳? 蓉，羅海媛.國內景區旅游流調控研究綜述[J].地理與地理信息科學，2015，31（5）：90-96.