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

（1. 桂林理工大學(xué)旅游與風(fēng)景園林學(xué)院，桂林 541000；2. 南昌航空大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，南昌 330063；3. 南昌航空大學(xué)軟件學(xué)院，南昌 330063）

0 引言

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

1 算法介紹

粒子群優(yōu)化算法（particle swarm optimization，PSO）又稱粒子群算法［17］，是通過(guò)模擬鳥群覓食行為而發(fā)展起來(lái)的一種基于群體協(xié)作的隨機(jī)搜索算法［18-20］，主要應(yīng)用在連續(xù)優(yōu)化的問(wèn)題中，對(duì)于離散問(wèn)題，PSO應(yīng)用在TSP旅行商問(wèn)題是一個(gè)新的研究方向。

一群鳥在尋找食物，在這個(gè)區(qū)域中只有一只蟲子，所有的鳥都不知道食物在哪。但是它們知道自己的當(dāng)前位置距離食物有多遠(yuǎn)，同時(shí)它們知道離食物最近的鳥的位置［21-24］。如圖1 所示，表示的是鳥群在覓食過(guò)程中的幾種狀態(tài)。小黑點(diǎn)表示一只鳥，箭頭指示的方向表示鳥群飛行的方向。圖1（a）表示鳥群的初始覓食狀態(tài)，鳥群都是分散開來(lái)的，朝著區(qū)域內(nèi)最可能找到食物的方向運(yùn)動(dòng)；圖（b）表示鳥群中間覓食的狀態(tài)，可以看到鳥群已經(jīng)呈現(xiàn)出聚集狀態(tài)，分布在食物周圍，找到局部最優(yōu)解；圖（c）表示鳥群的最終覓食狀態(tài)，鳥群分布在食物的周圍，此時(shí)找到了最優(yōu)解［25］。

圖1 鳥群覓食狀態(tài)

圖2 描述了粒子群優(yōu)化算法的運(yùn)算流程，如下［26］：

圖2 粒子群優(yōu)化算法的運(yùn)算流程［27］

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

步驟2：計(jì)算每個(gè)粒子的適應(yīng)度值fit(i)。

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

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

（5）迭代更新粒子的速度vi和位置xi。根據(jù)公式（1）和（2）得到兩個(gè)最優(yōu)值pbest和gbest，可根據(jù)公式（3）和（4）來(lái)更新粒子的速度和位置。

其中：c1和c2稱為學(xué)習(xí)因子，分別調(diào)節(jié)pbest和gbest方向飛行的最大步長(zhǎng)；r1和r2為［0，1］范圍內(nèi)的均勻隨機(jī)數(shù)。

（6）進(jìn)行邊界條件處理。

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

2 實(shí)例驗(yàn)證

2.1 實(shí)例介紹

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

表1 江西省13個(gè)5A景區(qū)坐標(biāo)

2.2 實(shí)驗(yàn)結(jié)果分析

本文中景點(diǎn)坐標(biāo)是經(jīng)緯度坐標(biāo)，而地球是一個(gè)三維的球體，不能夠直接通過(guò)經(jīng)緯度計(jì)算距離，所以需要將景點(diǎn)的經(jīng)緯度坐標(biāo)轉(zhuǎn)換為距離進(jìn)行計(jì)算。

把表1中景點(diǎn)坐標(biāo)數(shù)據(jù)輸入Matlab中，通過(guò)粒子群優(yōu)化算法對(duì)江西13個(gè)5A景區(qū)進(jìn)行路徑規(guī)劃。根據(jù)若干次Matlab 仿真實(shí)驗(yàn)結(jié)果對(duì)蟻群算法的其他參數(shù)進(jìn)行設(shè)定：城市數(shù)量為13，種群大小為50，學(xué)習(xí)因子c1為2，學(xué)習(xí)因子c2為2，pbest-xi的保留概率r1為0.7，gbest-xi的保留概率r2為0.8，算法最大迭代次數(shù)為1000。利用同樣的參數(shù)和程序?qū)魇÷糜尉包c(diǎn)進(jìn)行多次Matlab 仿真計(jì)算，最優(yōu)結(jié)果如圖3所示。

圖3 粒子群優(yōu)化算法最優(yōu)路徑

根據(jù)仿真實(shí)驗(yàn)結(jié)果，得到最短路徑順序?yàn)椋?1→10→12→4→8→5→6→13→2→3→1→9→7→11。

表2 除了統(tǒng)計(jì)了景點(diǎn)間的直線距離(根據(jù)經(jīng)緯度計(jì)算)，還展示了景點(diǎn)間的真實(shí)距離（通過(guò)高德導(dǎo)航，選擇駕駛模式）。從表2 可以看出導(dǎo)航的真實(shí)距離和通過(guò)經(jīng)緯度計(jì)算得到的直線距離有較大差別，而導(dǎo)航的真實(shí)距離才是日常生活中使用的，所以本文把導(dǎo)航的真實(shí)距離作為實(shí)驗(yàn)結(jié)果。

表2 最優(yōu)路徑各區(qū)間距離

由表2 中的導(dǎo)航真實(shí)距離得到最短距離為2582 km，相鄰景點(diǎn)間的距離依次為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 結(jié)語(yǔ)

TSP 旅行商問(wèn)題是一個(gè)生活中很常見的問(wèn)題，本文通過(guò)粒子群優(yōu)化算法模擬對(duì)江西省13個(gè)5A 景區(qū)進(jìn)行路徑規(guī)劃，通過(guò)對(duì)參數(shù)的多次調(diào)整，最終找到一條最短的旅游路徑，為乘客節(jié)省旅途時(shí)間的成本，完成了本文需要實(shí)現(xiàn)的目標(biāo)。本文得到的最短距離是根據(jù)導(dǎo)航的真實(shí)距離，更加貼近真實(shí)的生活，但是沒有考慮到旅途中路線等真實(shí)費(fèi)用問(wèn)題，在日后的研究中應(yīng)當(dāng)把這些實(shí)際因素考慮進(jìn)來(lái)，這樣才能更好地解決生活中的實(shí)際問(wèn)題，讓科學(xué)研究走進(jìn)生活。