基于回溯蟻群-粒子群混合算法的多點(diǎn)路徑規(guī)劃

劉麗玨，羅舒寧，高琰，陳美妃

（中南大學(xué)信息科學(xué)與工程學(xué)院，湖南 長沙 410083）

1 引言

隨著智慧旅游的興起，為了向游客提供更精準(zhǔn)的導(dǎo)游服務(wù)，不少景區(qū)推出了官方App。單一基于道路網(wǎng)的導(dǎo)航方式已經(jīng)難以滿足游客對(duì)精準(zhǔn)化、個(gè)性化導(dǎo)航尋徑的需求。針對(duì)旅游景區(qū)個(gè)性化導(dǎo)航需求，不少論文提出了路徑規(guī)劃算法。文獻(xiàn)[1]通過改進(jìn)A*算法，融合多維動(dòng)態(tài)環(huán)境信息，提出了景點(diǎn)間動(dòng)態(tài)路徑規(guī)劃的解決方案。文獻(xiàn)[2]以鼓浪嶼景區(qū)為例，改進(jìn)Dijkstra算法，實(shí)現(xiàn)了對(duì)該景區(qū)旅游線路的規(guī)劃。文獻(xiàn)[3]考慮了景區(qū)路徑的復(fù)雜性，將景區(qū)路徑分為全景區(qū)圖和子景區(qū)圖，改進(jìn)蟻群算法實(shí)現(xiàn)了景區(qū)路徑規(guī)劃。文獻(xiàn)[4]運(yùn)用混合密度聚類方法識(shí)別景點(diǎn)熱度，改進(jìn)傳統(tǒng)蟻群算法，提出了一種新型的熱門游覽景點(diǎn)路徑規(guī)劃方法。這些算法和模型僅僅解決了從起點(diǎn)到終點(diǎn)之間的最優(yōu)路徑規(guī)劃問題。但在實(shí)際的旅游需求中，游客或旅游大巴進(jìn)行路徑規(guī)劃時(shí)，更希望能得到一條從起點(diǎn)出發(fā)，經(jīng)過某些必去的景點(diǎn)（必經(jīng)點(diǎn)）的最短規(guī)劃路線，以便游客無遺漏且更省時(shí)間地進(jìn)行游覽。

鑒于此問題，本文參考TSP（traveling salesman problem）問題解決方法，提出了一種回溯蟻群-粒子群混合算法（BAPM，backtracking ant colonyparticle swarm method），可用于解決景區(qū)中從某個(gè)旅游景點(diǎn)開始經(jīng)過一些特定旅游點(diǎn)的多點(diǎn)路徑規(guī)劃問題，該問題的解決對(duì)旅游景區(qū)多點(diǎn)路徑規(guī)劃具有一定的參考價(jià)值。

本文將景區(qū)景點(diǎn)抽象為點(diǎn)，將景區(qū)路徑抽象為有向線段，將景區(qū)圖抽象為非完全有向圖，從而對(duì)該圖模型進(jìn)行描述，并且利用該圖模型，實(shí)現(xiàn)本文提出的BAPM算法。

2 基本知識(shí)

2.1 最大最小蟻群系統(tǒng)

最大最小蟻群系統(tǒng)（MMAS，max-min ant system）[5]是目前眾多蟻群算法中效率較高的算法之一，它模擬了螞蟻在覓食過程中尋找路徑的場景，對(duì)當(dāng)前路徑不斷地進(jìn)行優(yōu)化，從而找到最短覓食路線。該算法中，節(jié)點(diǎn)i到節(jié)點(diǎn)j路徑上的啟發(fā)因子記作ηij；在第t次迭代中，節(jié)點(diǎn)i到節(jié)點(diǎn)j路徑上的信息素記作τij（t）；ηij與τij（t）的占比將會(huì)成為第t次迭代中螞蟻k站在節(jié)點(diǎn)i選擇下一個(gè)節(jié)點(diǎn)j所走路徑的重要因素，記作（t），該因素值越大，選擇該值對(duì)應(yīng)的節(jié)點(diǎn)的概率就越高。反復(fù)迭代該算法，最終可以得到一條近似最短路徑。在迭代過程中，信息素τij（t）根據(jù)螞蟻尋找到的最優(yōu)權(quán)值變化進(jìn)行更新。信息素τij（t）將會(huì)被限制在最大最小信息素范圍之間，使該方法不會(huì)在短時(shí)間內(nèi)快速收斂陷入局部最優(yōu)。

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

粒子群優(yōu)化（PSO，particle swarm optimization）算法[6]模擬鳥群或魚群的覓食方法，不斷地更新當(dāng)前位置及下一時(shí)刻的方向及速度，使其不斷逼近目標(biāo)。在PSO算法中，每個(gè)粒子通過不斷的自我學(xué)習(xí)與向迭代最優(yōu)粒子學(xué)習(xí)來改進(jìn)自身的速度及位置，從而達(dá)到一個(gè)最優(yōu)結(jié)果。

MMAS算法相對(duì)于傳統(tǒng)的蟻群算法來說，極大程度地避免了局部最優(yōu)情況的發(fā)生，并且增加了該模型找到最優(yōu)值的概率，但是在節(jié)點(diǎn)數(shù)量非常多的情況下，MMAS仍然容易陷入局部最優(yōu)，它的最大最小值的限制在避免算法快速陷入局部最優(yōu)的同時(shí)，也降低了其尋找到最優(yōu)路徑的可能性，即忽略了信息素中的優(yōu)越因子。為了增強(qiáng)算法尋找最優(yōu)路徑的能力，本文結(jié)合PSO算法和MMAS算法，對(duì)信息素τij（t）進(jìn)行局部及全局更新，突出了對(duì)優(yōu)越路段的標(biāo)記，實(shí)現(xiàn)了對(duì)多點(diǎn)路徑規(guī)劃問題的有效處理。

3 回溯蟻群-粒子群混合算法

本文提出運(yùn)用回溯蟻群-粒子群混合算法（BAPM）解決旅游景區(qū)中的多點(diǎn)路徑規(guī)劃問題。該算法結(jié)合了MMAS算法和PSO算法，增強(qiáng)了路徑尋優(yōu)能力，避免了算法過早陷入局部最優(yōu)，并改善了算法尋優(yōu)能力弱的問題，在對(duì)比實(shí)驗(yàn)部分，也達(dá)到了較為理想的測試結(jié)果。該算法如算法1所示。

算法1回溯蟻群-粒子群混合算法

1）使用Floyd-Warshall算法將圖G轉(zhuǎn)換成，更新權(quán)值，用city表示中節(jié)點(diǎn)個(gè)數(shù)

2）建立的權(quán)值矩陣，如果兩點(diǎn)之間沒有路徑，則=-1

3）設(shè)置迭代次數(shù)num和螞蟻數(shù)量m

4）初始化信息素τ、啟發(fā)因子η、信息素和啟發(fā)因子的相關(guān)重要性參數(shù)α與β、學(xué)習(xí)因子中的可調(diào)參數(shù)ω、衰減因子ρ、最小信息素可調(diào)參數(shù)pbest、迭代代數(shù)i=1、全局最優(yōu)路徑 pathgb、局部最優(yōu)路徑pathlb及螞蟻所處當(dāng)前節(jié)點(diǎn)startpoint

5）whilei≤num

6）初始化path記錄每只螞蟻?zhàn)哌^的路徑

7）forj=1:m

8）startpoint=s

9）設(shè)置 city×city的矩陣 tabu_arc，如果=-1，那么tabu_arc（i,j）=-1，設(shè)置鄰接表tabu_node用于存放螞蟻當(dāng)前到達(dá)點(diǎn)的可行路段，設(shè)置不定長數(shù)組node記錄pathj中經(jīng)過的所有不重復(fù)節(jié)點(diǎn)

11）if count（tabu_node（startpoint））＞0

12）計(jì)算 tabu_node（startpoint）中的所有路段的被選擇概率

14）更新變量,startpoint=b、ifb?node,node={n ode,b}

15）else

16）回溯到tabu_arc的上個(gè)狀態(tài), 刪除pathj中的最后一條路段,更新startpoint、node,并在tabu_node中對(duì)當(dāng)前不可行路段進(jìn)行標(biāo)記

17）end if

18）end while

20）用改進(jìn)PSO算法局部更新信息素τ

21）end for

22）對(duì)全局最優(yōu)路徑 pathgb進(jìn)行更新

23）對(duì)信息素τ進(jìn)行全局更新

24）i=i+1

25）end while

本文所提 BAPM 算法中關(guān)鍵的幾個(gè)部分為：原始圖G轉(zhuǎn)換成完全圖；尋找可行路徑，包括路徑的編碼、計(jì)算路徑的被選擇概率；信息素的局部更新和全局更新。下面分別對(duì)這幾個(gè)部分進(jìn)行詳細(xì)說明。

3.1 圖模型轉(zhuǎn)換

從景區(qū)地圖中抽象獲得的圖G是一個(gè)非完全有向圖，它存在以下2種特殊情況：1）2個(gè)節(jié)點(diǎn)之間沒有一條直接連接的路徑，2）直接連接路徑的權(quán)值比間接路徑的權(quán)值大。因此在處理圖G之前，本文重新構(gòu)建圖模型，以便更好地計(jì)算出多點(diǎn)最短路徑。

假設(shè)N為非完全連通圖G=（V,A）中所有節(jié)點(diǎn)的個(gè)數(shù)，其中有n（n≤N-1）個(gè)節(jié)點(diǎn)為必經(jīng)節(jié)點(diǎn)，從節(jié)點(diǎn)s出發(fā)，尋找一條經(jīng)過這n個(gè)必經(jīng)節(jié)點(diǎn)一次且僅一次，再返回起始節(jié)點(diǎn)s的最短路徑。將起始點(diǎn)s看作固定點(diǎn)，s∈V，必經(jīng)點(diǎn)集為M?V-{s} 。本文通過以下步驟實(shí)現(xiàn)問題的轉(zhuǎn)換。

步驟 1生成新的頂點(diǎn)集合顯然是V的子集。

步驟 2生成新的邊集合且i,j在G中存在路徑} ，顯然，由于G是一個(gè)連通圖，G中任意兩點(diǎn)間都有路徑，則）是一個(gè)完全圖。

步驟 3計(jì)算圖中每條邊的長度，令中的任意兩點(diǎn)i、j之間的距離為圖G中i、j之間最短路徑的長度，由于G是連通圖，圖中任意兩點(diǎn)間都有路徑，即該長度不會(huì)等于無窮大。在圖G中求i、j兩點(diǎn)之間的最短距離使用了Floyd-Warshall[7]算法。

很明顯，通過以上3個(gè)步驟建立了一個(gè)完全圖，其點(diǎn)集合只包含G中的起始點(diǎn)s和必經(jīng)點(diǎn)集合M，邊的長度則對(duì)應(yīng)邊的2個(gè)端點(diǎn)在G中的最短路徑長度，則原問題轉(zhuǎn)換為在完全圖中找尋一個(gè)最短Hamilton圈的TSP問題。

圖1 多點(diǎn)路徑規(guī)劃原問題

圖2 多點(diǎn)路徑規(guī)劃轉(zhuǎn)換后

圖1所示為非完全連通圖。需要從點(diǎn)1出發(fā)，前往點(diǎn)2、點(diǎn)3、點(diǎn)4、點(diǎn)5、點(diǎn)6進(jìn)行游覽，之后回歸點(diǎn)1，起始點(diǎn)s=1，M={ 2 ,3,4,5,6}。將圖1中必經(jīng)點(diǎn)提取出來構(gòu)成圖2，運(yùn)用Floyd算法計(jì)算集合M中每兩點(diǎn)之間最短路徑長度，將其作為圖2中的邊長。

斯坦納旅行商問題[8]（STSP，Steiner traveling salesman problem）與本文所述問題相似，都是解決經(jīng)過必經(jīng)點(diǎn)的路徑規(guī)劃問題，并且必經(jīng)點(diǎn)可以重復(fù)使用。不同之處點(diǎn)在于STSP有固定的起始點(diǎn)和終點(diǎn)，而本文所述問題僅需要固定起始點(diǎn)。由于必經(jīng)點(diǎn)可以重復(fù)使用，為了讓該問題在定義上更加準(zhǔn)確，引入引理1[8]。

引理1在 STSP最佳解決方案中，任何一條有向邊僅能遍歷一次。

也就是說，在圖的最優(yōu)路徑中，點(diǎn)集中的節(jié)點(diǎn)可以重復(fù)使用，但邊集中的有向邊不能重復(fù)使用。本文基于此規(guī)則實(shí)現(xiàn)了BAPM算法對(duì)最小權(quán)值路徑的搜索。

3.2 尋找可行路徑

3.2.1 路徑編碼

將景區(qū)地圖按照3.1節(jié)步驟1～步驟3進(jìn)行轉(zhuǎn)換后，問題轉(zhuǎn)變?yōu)閺霓D(zhuǎn)換后的圖中給定的起始點(diǎn)s出發(fā)，需要找到一條經(jīng)過所有必經(jīng)點(diǎn)的可行路徑。

由3.1節(jié)可知，為轉(zhuǎn)換圖的有向邊集合。從節(jié)點(diǎn)i出發(fā)到達(dá)節(jié)點(diǎn)j的有向邊記作（i,j）。本文用圖中的邊構(gòu)成的位串對(duì)路徑進(jìn)行編碼，將螞蟻a尋找到的路徑patha表示為

將路徑patha中包含的所有不重復(fù)節(jié)點(diǎn)的集合記作node；使用禁忌表tabu_arc對(duì)有向邊集合進(jìn)行管理，保證在patha中的有向邊不會(huì)重復(fù)出現(xiàn)；使用鄰接表tabu_node來記錄路徑patha當(dāng)前到達(dá)節(jié)點(diǎn)的可選路段；startpoint記錄路徑當(dāng)前到達(dá)的節(jié)點(diǎn)，當(dāng)路徑patha經(jīng)過（i,j）時(shí)，可以說當(dāng)前路徑patha到達(dá)了節(jié)點(diǎn)j，此時(shí)startpoint=j。

3.2.2 可行路徑的尋找與路段的選擇

根據(jù)圖 2，初始化的權(quán)值矩陣和禁忌表tabu _ arc為

其中，存放路段的權(quán)值，tabu_arc表示路徑段的使用狀態(tài)，“0”表示該路徑可行，“-1”表示該路徑不可行。

尋找一條可行路徑的方法如下。螞蟻a從起始點(diǎn)startpoint=s開始尋找路徑，根據(jù)tabu_node（startpoint）得到下一時(shí)刻的所有可選路段，選擇其中一條路段（s,j），在tabu_arc中將已走過的路段標(biāo)記為“-1”，同時(shí)，將路段（s,j）存入patha中，并且startpoint=j。為了減少算法的時(shí)間復(fù)雜度，tabu_node使用散列表進(jìn)行存儲(chǔ)。當(dāng)執(zhí)行到某個(gè)沒有可行邊的節(jié)點(diǎn)，即可行路段tabu_node（startpoint）為空或者均已被標(biāo)記時(shí)，證明該路徑不可行，則使用回溯方法，最終找到一條可行路徑。

上述尋找可行路徑的過程可簡化表示為圖3。

圖3 尋找可行路徑的迭代過程

在非完全有向圖中，運(yùn)用回溯方法查詢路徑可以避免產(chǎn)生非可行性路徑，提高選擇路徑的效率。

Tabu_node表中，確定可選路段是該算法中的一個(gè)重要環(huán)節(jié)。在第k次迭代中，螞蟻a在尋找路徑時(shí)，會(huì)根據(jù)startpoint對(duì)應(yīng)的tabu_node（startpoint）中每條路段的可行概率（k）,i∈,j∈，i≠j，選擇概率大的路段，并根據(jù)已選擇的路段到達(dá)下個(gè)節(jié)點(diǎn)d，startpoint=d。若tabu_node不存在可行路段，即 count（tabu_node（startpoint））=0，則刪除patha中startpoint所對(duì)應(yīng)路段，將螞蟻到達(dá)的當(dāng)前節(jié)點(diǎn)賦值給startpoint，釋放tabu_arc中該路段的標(biāo)記，繼續(xù)尋找下一個(gè)可行路段，以此類推，直到所有必經(jīng)點(diǎn)都包含在該螞蟻的所行路徑當(dāng)中，即node=，此路徑patha則為一條可行路徑。這種尋路方式適應(yīng)本文模型要求，使尋找路徑更加靈活并且保證了每條路徑的可行性，避免了非可行解的產(chǎn)生。

選擇路段的概率計(jì)算式如式（1）所示。

3.3 更新信息素

3.3.1 信息素的全局更新

根據(jù)上述尋路方法，可以得到所有螞蟻的可行路徑path，找出其中權(quán)值最小的路徑，記作 pathgb，并且記錄每只螞蟻的可行路徑，記作 pathlb。在迭代過程中，找出權(quán)值最小的路徑并且將其權(quán)值與pathgb的權(quán)值進(jìn)行比較，將 pathgb替換成權(quán)值最小的路徑，本文將 pathgb稱作全局最優(yōu)路徑，同理，將pathlb替換成每只螞蟻尋找到的權(quán)值最小的路徑，稱作局部最優(yōu)路徑。

當(dāng)所有螞蟻均尋找到一條可行路徑后，需要更新圖中每個(gè)路段對(duì)應(yīng)的信息素。信息素τij（t）描述了螞蟻經(jīng)過各個(gè)路段所留下的痕跡，本文將τij（t）值較大的路段稱為優(yōu)越路段，信息素更新如式（2）所示。

其中，參數(shù)ρ（0≤ρ≤1）為衰減因子，用于沖淡信息素的濃度；為全局最優(yōu)路徑 pathgb的信息素增量，計(jì)算式如式（3）所示。

為了避免信息素過快地陷入局部最優(yōu)，設(shè)置最大信息素τmax和最小信息素τmin，如式（4）和式（5）所示，則信息素更新范圍為τmin≤τij（t）≤τmax。

其中，city表示點(diǎn)集的大小；pbest表示一個(gè)可調(diào)參數(shù)，本文取值為0.005。

3.3.2 信息素的局部更新

設(shè)置最大最小信息素后，隨著迭代次數(shù)的增多，優(yōu)越路段得不到有效的突出，使算法容易陷入局部最優(yōu)，造成最終得到的最短路徑與期望路徑存在較大差距。本文結(jié)合改進(jìn)后的PSO算法，突出路徑中較優(yōu)路段的信息素，以保證算法能產(chǎn)生更為接近最短路徑的結(jié)果。

基本的 PSO算法通常用于連續(xù)函數(shù)尋找最優(yōu)解的問題，粒子從隨機(jī)的初始位置出發(fā)，不斷改變自身的速度和位置，每次迭代均飛向自身最優(yōu)和全局最優(yōu)位置的加權(quán)中心，以達(dá)到自我認(rèn)知和信息共享的目的。本文建立了所討論問題和PSO算法之間的映射關(guān)系，將問題空間映射到粒子空間，將問題離散化。

將每只螞蟻a的可行路徑patha看作一個(gè)粒子，將當(dāng)前的信息素τ看作粒子的當(dāng)前位置，將信息素的增量看作PSO算法中的速度變化量。

本文定義了 2個(gè)變量——全局最優(yōu)路徑片段pgb和局部最優(yōu)路徑片段plb，用于計(jì)算粒子的運(yùn)動(dòng)速度。全局最優(yōu)路徑片段為螞蟻當(dāng)前找到的路徑與全局最優(yōu)路徑中相同的路徑片段集合，局部最優(yōu)路徑片段為螞蟻當(dāng)前找到的路徑與其自身曾找到的最優(yōu)路徑中相同的路徑片段集合。若螞蟻a找到當(dāng)前路徑為patha，其計(jì)算式為

全局最優(yōu)路徑為

局部最優(yōu)路徑為

則全局最優(yōu)路徑片段為

局部最優(yōu)路徑片段為

在螞蟻a尋找到可行路徑patha后，得到pgb和plb，增加pgb、plb對(duì)應(yīng)路段的信息素，信息素增長式如式（6）～式（9）所示。

在迭代過程中，不斷地更新 pathlb和 pathgb，從而更新plb和pgb對(duì)應(yīng)的信息素，使信息素不斷地向有益于獲取最優(yōu)路徑的方向增長，從而使算法能夠更加快速有效地得到圖中的最短路徑。

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

本文的實(shí)驗(yàn)主要分為4個(gè)部分。第一部分將本文所提BAPM算法與MMAS算法、遺傳算法（GA，genetic algorithm）進(jìn)行比較，展示BAPM算法在精確度上的優(yōu)越性，本文選擇了TSPLIB數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。第二部分為仿真實(shí)驗(yàn)，運(yùn)用BAPM算法尋找包含多點(diǎn)的最短路徑，然后運(yùn)用分支定界法[9-10]找出這個(gè)圖中的精確最短路徑，驗(yàn)證 BAPM算法尋找最短路徑的正確性。第三部分為景區(qū)地圖實(shí)際規(guī)劃結(jié)果，展示了BAPM算法在一個(gè)實(shí)際的景區(qū)地圖數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果。第四部分對(duì)上述實(shí)驗(yàn)進(jìn)行總結(jié)。

4.1 TSPLIS數(shù)據(jù)庫實(shí)驗(yàn)

為了驗(yàn)證 BAPM 算法有效地改進(jìn)了局部最優(yōu)問題并且能找到更為接近的最短路徑，本文使用MMAS算法和GA算法作為對(duì)比算法，3種算法均在 MATLAB（R2014a）上進(jìn)行實(shí)現(xiàn)，且迭代次數(shù)相同。BAPM算法的參數(shù)設(shè)置如表1所示。

表1 BAPM算法參數(shù)

分別運(yùn)用BAPM算法、MMAS算法和GA算法對(duì)TSPLIS數(shù)據(jù)庫中提供的14組數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，每種算法各運(yùn)行10次，獲取每組數(shù)據(jù)在不同算法中運(yùn)行得到的最大路徑長度、最小路徑長度以及10組數(shù)據(jù)值與精確解之間的平均偏差百分比，如表2所示。

表2 TSPLIB數(shù)據(jù)庫對(duì)比實(shí)驗(yàn)

4.2 仿真實(shí)驗(yàn)

為驗(yàn)證BAPM算法的正確性，本文建立了一個(gè)仿真系統(tǒng)。該系統(tǒng)可隨機(jī)構(gòu)建不同的圖。這些圖都可以看作景區(qū)地圖的抽象圖結(jié)構(gòu)，圖中的頂點(diǎn)對(duì)應(yīng)景區(qū)的景點(diǎn)，邊則表示景點(diǎn)之間的路徑。假設(shè)必經(jīng)節(jié)點(diǎn)數(shù)量為 9，尋找圖中從某一起始點(diǎn)出發(fā)經(jīng)過這些點(diǎn)的最短路徑，就對(duì)應(yīng)為從景區(qū)的當(dāng)前位置出發(fā)，規(guī)劃一條包含9個(gè)游覽景點(diǎn)的最短路徑問題。第一種情況，隨機(jī)構(gòu)建一個(gè)包括100個(gè)隨機(jī)生成的節(jié)點(diǎn)的圖，任意兩節(jié)點(diǎn)之間均有路徑。在產(chǎn)生的路徑中隨機(jī)刪除4 000條路徑，將其轉(zhuǎn)換為一個(gè)稀疏圖，從而模擬景區(qū)路線網(wǎng)絡(luò)的布局，然后在圖中選擇10個(gè)必經(jīng)點(diǎn)（包含起點(diǎn)），如圖4所示。第二種情況，隨機(jī)產(chǎn)生 10個(gè)點(diǎn)及其之間的路徑，構(gòu)成一個(gè)有向非完全圖，隨機(jī)選擇一個(gè)起始點(diǎn)，尋找經(jīng)過這10個(gè)點(diǎn)的最短路徑，如圖5所示。

圖4 第一種情況

圖 4（a）展示了通過 Floyd-Warshall算法變換后的路線圖，由選定的這 10個(gè)點(diǎn)構(gòu)成的圖，圖4（b）是運(yùn)用BAPM算法經(jīng)過這10個(gè)點(diǎn)尋找的最短路徑。

圖 5（a）為由 Floyd-Warshall算法進(jìn)行重組的有向圖，圖5（b）表示由BAPM算法產(chǎn)生的最短路徑。

圖5 第二種情況

以上2種情況下本文方法得到的結(jié)果與分支定界法找到的路徑相同。

4.3 橘洲景區(qū)游覽路線規(guī)劃

橘洲景區(qū)是長沙的著名旅游景區(qū)，本文算法被應(yīng)用于橘洲景區(qū)智能導(dǎo)覽系統(tǒng)中。該系統(tǒng)中的橘洲地圖是借助GPS設(shè)備、GOOGLE衛(wèi)星地圖等，通過實(shí)地打點(diǎn)，遍歷景區(qū)道路并測量記錄后自行建立的電子地圖，橘洲景區(qū)景點(diǎn)的位置信息如表3所示。

以表3中標(biāo)注*的6個(gè)景點(diǎn)為實(shí)驗(yàn)1必經(jīng)景點(diǎn)，采用BAPM算法規(guī)劃出的最佳路徑為：枕江觀光車售票處—沁園春詩詞碑—毛澤東青年藝術(shù)雕像—望江亭—指點(diǎn)江山石碑—問天臺(tái)，全程645 m，為最短游覽路徑。

以表3中標(biāo)注#的10個(gè)景點(diǎn)為實(shí)驗(yàn)2必經(jīng)景點(diǎn)，采用BAPM算法規(guī)劃出的最佳路徑為：地鐵站西站口—原長沙海關(guān)舊址—婚慶園—橘子洲古董鋼琴博物館—沁園春·長沙橘洲 1925 —橘子洲人行入口—美孚洋行舊址—財(cái)神古殿—游客服務(wù)中心西站點(diǎn)—橘子洲西大門，全程1 218 m，為最短游覽路徑。

表3 橘子洲景區(qū)景點(diǎn)信息

實(shí)驗(yàn)1與實(shí)驗(yàn)2均找到了包含必經(jīng)景點(diǎn)的最短游覽路徑。

4.4 實(shí)驗(yàn)總結(jié)

本文使用了3組實(shí)驗(yàn)，驗(yàn)證了提出的BAPM算法的有效性及優(yōu)越性。在第一組實(shí)驗(yàn)中，選用了TSPLIB數(shù)據(jù)庫中的TSP數(shù)據(jù)，將本文提出的BAPM算法與MMAS算法及GA算法進(jìn)行了比較，結(jié)果顯示BAPM算法可以在數(shù)據(jù)量較大的條件下，找出更接近最小路徑的結(jié)果。在第二組實(shí)驗(yàn)中，隨機(jī)生成點(diǎn)和路徑，模擬景區(qū)地圖和景點(diǎn)，該組實(shí)驗(yàn)的必經(jīng)點(diǎn)數(shù)設(shè)置較?。?0個(gè)必經(jīng)點(diǎn)），驗(yàn)證了在點(diǎn)數(shù)較少的情況下，BAPM算法可以有效地找到準(zhǔn)確的最短路徑。第三組實(shí)驗(yàn)對(duì)實(shí)際的景區(qū)景點(diǎn)進(jìn)行規(guī)劃，所有景點(diǎn)位置和景點(diǎn)間路徑長度均為實(shí)測數(shù)據(jù)，驗(yàn)證了算法在景點(diǎn)路徑規(guī)劃中的有效性。

通過實(shí)驗(yàn)驗(yàn)證了BAPM算法的有效性。實(shí)驗(yàn)結(jié)果表明，BAPM算法可以處理非完全圖問題和完全圖問題，并且在必經(jīng)點(diǎn)個(gè)數(shù)較小的情況下，可以準(zhǔn)確并且快速地尋找到最短路徑。

5 結(jié)束語

本文針對(duì)旅游景區(qū)場景下，旅游者對(duì)多景點(diǎn)游覽路徑的規(guī)劃需求，提出了一種基于回溯蟻群-粒子群混合算法的旅游景點(diǎn)路徑規(guī)劃模型，用于解決從起始點(diǎn)出發(fā)，經(jīng)過若干必經(jīng)點(diǎn)的景區(qū)景點(diǎn)路線規(guī)劃的問題。通過實(shí)驗(yàn)，證明了BAPM算法可解決上述多點(diǎn)景點(diǎn)路徑規(guī)劃問題。由于BAPM算法實(shí)際上是一種多點(diǎn)路徑規(guī)劃算法，在復(fù)雜網(wǎng)絡(luò)分析與設(shè)計(jì)、機(jī)器人路徑規(guī)劃[11]、路由復(fù)雜網(wǎng)絡(luò)[12]等方面同樣具有一定的實(shí)用價(jià)值。