基于粒子群算法的江西景點自駕游路線規劃

宋艷艷，李廣宏，朱 玲，夏傳林，鄭 巍

（1. 桂林理工大學旅游與風景園林學院，桂林 541000；2. 南昌航空大學數學與信息科學學院，南昌 330063；3. 南昌航空大學軟件學院，南昌 330063）

0 引言

隨著科技的發展，通過攜程、美團、飛豬等APP 可以在網上查詢各地的旅游景點，十分方便人們的出行，在一定程度上也促進了旅游業的發展。隨著汽車的普及，自駕游也越來越受到年輕人的喜愛，人們會根據出行的時間合理地規劃旅游行程，選擇合適的景點個數，但是實際出行中，還會伴隨其他問題的產生，例如旅游路徑的規劃［1-2］、旅游費用等，這個時候需要合理的方法解決這個問題。許多學者對這個問題進行研究，最早源于TSP 旅行商問題［3］，隨后對該問題的算法進行深入研究，解決這類問題常用的方法有蟻群［4-7］、粒子群［8-11］、遺傳算法［12-15］等。本文結合粒子群算法，對江西13 個5A 旅游景點進行路徑規劃，粒子群算法可以為我們提供最佳的旅游順序［16］。

1 算法介紹

粒子群優化算法（particle swarm optimization，PSO）又稱粒子群算法［17］，是通過模擬鳥群覓食行為而發展起來的一種基于群體協作的隨機搜索算法［18-20］，主要應用在連續優化的問題中，對于離散問題，PSO應用在TSP旅行商問題是一個新的研究方向。

一群鳥在尋找食物，在這個區域中只有一只蟲子，所有的鳥都不知道食物在哪。但是它們知道自己的當前位置距離食物有多遠，同時它們知道離食物最近的鳥的位置［21-24］。如圖1 所示，表示的是鳥群在覓食過程中的幾種狀態。小黑點表示一只鳥，箭頭指示的方向表示鳥群飛行的方向。圖1（a）表示鳥群的初始覓食狀態，鳥群都是分散開來的，朝著區域內最可能找到食物的方向運動；圖（b）表示鳥群中間覓食的狀態，可以看到鳥群已經呈現出聚集狀態，分布在食物周圍，找到局部最優解；圖（c）表示鳥群的最終覓食狀態，鳥群分布在食物的周圍，此時找到了最優解［25］。

圖1 鳥群覓食狀態

圖2 描述了粒子群優化算法的運算流程，如下［26］：

圖2 粒子群優化算法的運算流程［27］

步驟1：初始化粒子群，包括群體規模N，每個粒子的位置xi和速度vi。

步驟2：計算每個粒子的適應度值fit(i)。

步驟3：對每個粒子，用它的適應度值fit(i)和個體極值pbest(i)比較。如果fit(i)＜pbest(i)，則用fit(i)替換掉pbest(i)。第i個粒子迄今為止搜索到的最優位置稱為個體極值，記為

（4）對每個粒子，用它的適應度值fit(i)和全局極值gbest比較。如果fit(i)＜gbest(i)，則用fit(i)替換掉gbest。整個粒子群迄今為止搜索到的最優位置為全局極值，記為

（5）迭代更新粒子的速度vi和位置xi。根據公式（1）和（2）得到兩個最優值pbest和gbest，可根據公式（3）和（4）來更新粒子的速度和位置。

其中：c1和c2稱為學習因子，分別調節pbest和gbest方向飛行的最大步長；r1和r2為［0，1］范圍內的均勻隨機數。

（6）進行邊界條件處理。

（7）判斷算法終止條件是否滿足：若是，則結束算法并輸出優化結果；否則返回步驟（2）。

2 實例驗證

2.1 實例介紹

江西省是一個具有濃厚歷史韻味和人文特色的著名旅游城市，本文選取江西省13個5A景區作為分析對象，其中包含自然景觀、歷史遺址、現代建筑等相對具有代表性的旅游景點。其中包含滕王閣、廬山、廬山西海、龍虎山、三清山、龜峰、井岡山、江灣、明月山、共和國搖籃、武功山、大覺山、古窯民俗博覽區13個景點。這些景點有的在南昌市內，有的在九江市，分布在江西省的各個地區。如果想去多個景點旅游，要是沒有做好路線規劃，會造成去過相同的路線，非常浪費時間。因此，本文重點對13 個景區進行一個順序排序，對景點進行路徑規劃，使得總路線最短。各個景點的位置坐標如表1所示，景點坐標是通過百度的拾取坐標系統獲得的經緯度坐標，在后續實驗計算中，需要將經緯度坐標轉換為距離坐標。

表1 江西省13個5A景區坐標

2.2 實驗結果分析

本文中景點坐標是經緯度坐標，而地球是一個三維的球體，不能夠直接通過經緯度計算距離，所以需要將景點的經緯度坐標轉換為距離進行計算。

把表1中景點坐標數據輸入Matlab中，通過粒子群優化算法對江西13個5A景區進行路徑規劃。根據若干次Matlab 仿真實驗結果對蟻群算法的其他參數進行設定：城市數量為13，種群大小為50，學習因子c1為2，學習因子c2為2，pbest-xi的保留概率r1為0.7，gbest-xi的保留概率r2為0.8，算法最大迭代次數為1000。利用同樣的參數和程序對江西省旅游景點進行多次Matlab 仿真計算，最優結果如圖3所示。

圖3 粒子群優化算法最優路徑

根據仿真實驗結果，得到最短路徑順序為：11→10→12→4→8→5→6→13→2→3→1→9→7→11。

表2 除了統計了景點間的直線距離(根據經緯度計算)，還展示了景點間的真實距離（通過高德導航，選擇駕駛模式）。從表2 可以看出導航的真實距離和通過經緯度計算得到的直線距離有較大差別，而導航的真實距離才是日常生活中使用的，所以本文把導航的真實距離作為實驗結果。

表2 最優路徑各區間距離

由表2 中的導航真實距離得到最短距離為2582 km，相鄰景點間的距離依次為429 km、288 km、108 km、276 km、102 km、147 km、173 km、159 km、104 km、97 km、249 km、248 km和202 km。

3 結語

TSP 旅行商問題是一個生活中很常見的問題，本文通過粒子群優化算法模擬對江西省13個5A 景區進行路徑規劃，通過對參數的多次調整，最終找到一條最短的旅游路徑，為乘客節省旅途時間的成本，完成了本文需要實現的目標。本文得到的最短距離是根據導航的真實距離，更加貼近真實的生活，但是沒有考慮到旅途中路線等真實費用問題，在日后的研究中應當把這些實際因素考慮進來，這樣才能更好地解決生活中的實際問題，讓科學研究走進生活。