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

胡冉 西藏大學(xué) 工學(xué)院

1.引言

拉薩市的旅游業(yè)發(fā)展雖一直穩(wěn)中求進(jìn)，但由于拉薩市地理位置的特殊，導(dǎo)致了拉薩市產(chǎn)業(yè)結(jié)構(gòu)單一的現(xiàn)象，目前旅游業(yè)所帶來(lái)的經(jīng)濟(jì)收入難以滿足城市經(jīng)濟(jì)的發(fā)展要求。受到地形地質(zhì)等自然條件的影響，現(xiàn)階段想通過(guò)改變交通運(yùn)輸方式來(lái)提高拉薩市的整體旅游效率和收入仍存在著較大的技術(shù)空缺，因此縮短旅游路線，為旅客提供高效旅游服務(wù)是解決當(dāng)務(wù)之急的有效方法。

粒子群算法是近年來(lái)較為科學(xué)有效的全局尋優(yōu)算法，它模擬鳥群飛行覓食的行為，通過(guò)鳥之間的集體協(xié)作使群體達(dá)到最優(yōu)。盡管每個(gè)個(gè)體的行為準(zhǔn)則是很簡(jiǎn)單的，但組合成整個(gè)群體的行為將會(huì)是非常復(fù)雜的。此算法是在解空間中利用種群迭代的方法對(duì)最優(yōu)粒子進(jìn)行搜索。它具有模型簡(jiǎn)單且易實(shí)現(xiàn)的優(yōu)點(diǎn)，目前在科學(xué)研究以及工程應(yīng)用都發(fā)揮了一定的作用。

2.模型簡(jiǎn)介

2.1 旅行商問題

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

2.2 粒子群優(yōu)化算法

其中：K是迭代次數(shù)，r1和r2為之間的隨機(jī)數(shù)，用來(lái)保持群體的多樣性。c1和c2為學(xué)習(xí)因子，也稱為加速因子，其使粒子具有自我總結(jié)和向群體中最優(yōu)秀個(gè)體學(xué)習(xí)的能力，從而向自己的歷史最優(yōu)點(diǎn)以及群體內(nèi)歷史最優(yōu)點(diǎn)靠近。

2.3 模型求解

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

本文通過(guò)對(duì)拉薩市四個(gè)著名景點(diǎn)做出了景點(diǎn)之間的分布圖1。

圖1 景點(diǎn)分布圖

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

2.4.1 仿真參數(shù)設(shè)置

種群數(shù)量N=1000，迭代次數(shù)k=50。表1為各景點(diǎn)的具體坐標(biāo)。

表1 景點(diǎn)坐標(biāo)圖

2.4.2 仿真結(jié)果與分析

在MATLAB2018b版本中的運(yùn)行結(jié)果如下圖2所示。通過(guò)交叉變異的混合粒子群算法，可較為精確的確定各個(gè)景點(diǎn)之間路徑最短的旅行方式，以①號(hào)羅布林卡為起點(diǎn)，可先選擇②號(hào)布達(dá)拉宮游玩，再經(jīng)過(guò)③號(hào)小昭寺，最后選擇大昭寺回到起點(diǎn)布達(dá)拉宮。由于旅行路線為無(wú)向圖，因此還可以選擇反方向的旅游路線。

圖2 最短旅行路線

3.結(jié)論

本文利用基于交叉變異的混合粒子群算法本文粗略地介紹了基于交叉變異的混合粒子群算法在PSO問題上的簡(jiǎn)單應(yīng)用，并能有效解決拉薩市旅游規(guī)劃上帶來(lái)效率低下等問題。但由于本文景點(diǎn)個(gè)數(shù)較少，因此難以體現(xiàn)此算法在收斂速度上的優(yōu)勢(shì)。但此算法在生活和工業(yè)應(yīng)用中具有極大的探究潛能，可延申至有向圖等非對(duì)稱問題上的研究。將本算法應(yīng)用至西藏自治區(qū)中將有更大的實(shí)踐價(jià)值和意義，西藏自治區(qū)地域廣袤、旅游景點(diǎn)眾多，距離因素是影響當(dāng)?shù)芈糜螛I(yè)發(fā)展的主要因素，可利用此算法有效地將旅游資源整合，更好地推動(dòng)西藏自治區(qū)旅游業(yè)的發(fā)展。