基于粒子群算法的拉薩市最短旅游路線規劃

胡冉 西藏大學 工學院

1.引言

拉薩市的旅游業發展雖一直穩中求進，但由于拉薩市地理位置的特殊，導致了拉薩市產業結構單一的現象，目前旅游業所帶來的經濟收入難以滿足城市經濟的發展要求。受到地形地質等自然條件的影響，現階段想通過改變交通運輸方式來提高拉薩市的整體旅游效率和收入仍存在著較大的技術空缺，因此縮短旅游路線，為旅客提供高效旅游服務是解決當務之急的有效方法。

粒子群算法是近年來較為科學有效的全局尋優算法，它模擬鳥群飛行覓食的行為，通過鳥之間的集體協作使群體達到最優。盡管每個個體的行為準則是很簡單的，但組合成整個群體的行為將會是非常復雜的。此算法是在解空間中利用種群迭代的方法對最優粒子進行搜索。它具有模型簡單且易實現的優點，目前在科學研究以及工程應用都發揮了一定的作用。

2.模型簡介

2.1 旅行商問題

旅行商問題，即TSP問題是數學領域中著名問題之一。即要求商人在每個城市只能拜訪一次的前提下走完所有選定的城市并返回出發點通過旅行商問題的啟發，本文利用基于交叉變異的混合粒子群算法，尋找出各旅游景點的之間的最短路徑。

2.2 粒子群優化算法

其中：K是迭代次數，r1和r2為之間的隨機數，用來保持群體的多樣性。c1和c2為學習因子，也稱為加速因子，其使粒子具有自我總結和向群體中最優秀個體學習的能力，從而向自己的歷史最優點以及群體內歷史最優點靠近。

2.3 模型求解

PSO算法是依靠群體之間的相互合作和競爭在問題空間中搜索最優值，本文為了彌補粒子自身缺乏選擇、交叉和變異的特性，在基本粒子群算法中引入了交叉和變異的機制，既加快了算法的收斂速度，又保證了粒子群的尋優精度。

本文通過對拉薩市四個著名景點做出了景點之間的分布圖1。

圖1 景點分布圖

為了更直觀的展現各景點之間的距離，本文將路徑均以直線代替且取整。其中①代表羅布林卡；②代表布達拉宮；③代表小昭寺；④代表大昭寺。

2.4.1 仿真參數設置

種群數量N=1000，迭代次數k=50。表1為各景點的具體坐標。

表1 景點坐標圖

2.4.2 仿真結果與分析

在MATLAB2018b版本中的運行結果如下圖2所示。通過交叉變異的混合粒子群算法，可較為精確的確定各個景點之間路徑最短的旅行方式，以①號羅布林卡為起點，可先選擇②號布達拉宮游玩，再經過③號小昭寺，最后選擇大昭寺回到起點布達拉宮。由于旅行路線為無向圖，因此還可以選擇反方向的旅游路線。

圖2 最短旅行路線

3.結論

本文利用基于交叉變異的混合粒子群算法本文粗略地介紹了基于交叉變異的混合粒子群算法在PSO問題上的簡單應用，并能有效解決拉薩市旅游規劃上帶來效率低下等問題。但由于本文景點個數較少，因此難以體現此算法在收斂速度上的優勢。但此算法在生活和工業應用中具有極大的探究潛能，可延申至有向圖等非對稱問題上的研究。將本算法應用至西藏自治區中將有更大的實踐價值和意義，西藏自治區地域廣袤、旅游景點眾多，距離因素是影響當地旅游業發展的主要因素，可利用此算法有效地將旅游資源整合，更好地推動西藏自治區旅游業的發展。