基于粒子群算法的電子地圖路徑規(guī)劃軟件設計

王磊， 楊思燕

(陜西廣播電視大學 信息與智能技術學院，西安 710119)

0 引言

電子地圖不僅能夠提供路線規(guī)劃的多種功能，還能夠提供道路的詳細信息，規(guī)劃出最佳的路線供用戶選擇。設計了西安市電子地圖路徑規(guī)劃軟件，該軟件具有地圖放大、縮小、定位、搜索等基本功能，可以根據(jù)Dijsktra算法實現(xiàn)路徑導航功能，完成任意起始點和終點之間的最短路徑計算，基于粒子群算法能夠在選定的節(jié)點范圍內(nèi)尋找一條優(yōu)化路徑，達到路徑規(guī)劃目的，如公交線路規(guī)劃、機器人路線規(guī)劃、物流配送[1]等。

1 路徑規(guī)劃軟件設計模塊與功能

路徑規(guī)劃軟件主要模型主要分為地圖操作和路徑規(guī)劃，其中地圖操作主要有放大、縮小、定位搜索等，路徑規(guī)劃主要是路徑導航與路徑尋優(yōu)。

點擊“地圖操作”，會彈出“放大”、“縮小”、“定位”、“搜索”子菜單，各個功能如下：

(1)放大：點擊地圖上任意位置，地圖將以該地點為中心放大一倍比例尺顯示。

(2)縮?。狐c擊地圖上任意位置，地圖將以該地點為中心縮小一倍比例尺顯示。

(3)定位：可以通過定位系統(tǒng)實時定位。

(4)搜索：在地圖上尋找目標位置。

點擊“路徑尋優(yōu)”，會彈出“路徑導航”及“路徑規(guī)劃”子菜單，各個功能如下：

(1)路徑導航：輸入起始點和終點，可以計算出一條最短路徑。

(2)路徑規(guī)劃：選擇若干個結點，可以計算出經(jīng)過這些結點的一條較優(yōu)路徑。

路徑規(guī)劃軟件模塊與功能，如圖1所示。

圖1 路徑規(guī)劃軟件模塊與功能

2 路徑規(guī)劃軟件實現(xiàn)技術

2.1 MapInfo軟件簡介

MapInfo由美國MapInfo公司開發(fā)，是一款地理信息系統(tǒng)二次開發(fā)軟件，能夠提供數(shù)據(jù)可視化、信息地圖化的桌面解決方案。它集成多種數(shù)據(jù)庫數(shù)據(jù)、結合計算機地圖方法、采用數(shù)據(jù)庫技術、融入地理信息系統(tǒng)分析功能，可以為各行各業(yè)所用的軟件系統(tǒng)提供服務[2]。MapInfo全稱為Mapping+Information即地圖對象+屬性數(shù)據(jù)。MapInfo采用“空間實體+空間索引”的拓撲關系模型，其空間實體是地理實體的抽象，類型包括點、線、面，每個空間實體對象都具有自身所有屬性，一個圖層由多個空間實體構成?？臻g索引能夠定位到給定的空間坐標，快速搜索到坐標范圍中的空間對象。MapInfo利用雙數(shù)據(jù)庫存儲模式(空間、屬性數(shù)據(jù))，空間數(shù)據(jù)以MapInfo的自定義格式保存在文件中，屬性數(shù)據(jù)存儲在關系數(shù)據(jù)庫的屬性表中，他們之間通過一定的索引機制互相通信[3]。

2.2 Mapx控件簡介

MapInfo公司在1996年推出了基于ActiveX技術的MapX控件，MapX控件隨著MapInfo的功能升級而不斷完善。MapX控件提供了二次開發(fā)的功能強大的地圖化組件?？梢郧度氲皆诳梢暬绦蜷_發(fā)環(huán)境中如Visual Basic、Visual C++等，只需將MapX控件放入到窗體中，進行設置屬性、調(diào)用方法和事件，就可實現(xiàn)地理空間數(shù)據(jù)的常用操作及可視化，并可以實現(xiàn)空間查詢、地理編碼等復雜的地圖信息系統(tǒng)功能[4]。

MapX與MapInfo使用一致的地圖數(shù)據(jù)格式，主要功能有顯示MapInfo格式的地圖數(shù)據(jù)，支持地圖的放大、縮小、平移、選擇等操作，圖層的自由控制，支持動態(tài)圖層和自定義圖層，專題地圖制作，簡單的地理查詢等。本軟件基于MapX組件進行二次開發(fā)。

2.3 路徑規(guī)劃軟件實現(xiàn)

本軟件把西安市路網(wǎng)電子地圖數(shù)據(jù)顯示在單文檔上，安裝MapX、MapInfo及Visual Studio 2008開發(fā)平臺，導入MapX.h 和 MapX.cpp到工程。其中MapX內(nèi)置了常用的標準地圖工具，例如放大、縮小、平移、選擇等，在菜單的單擊事件中編寫相關的代碼即可實現(xiàn)相應的功能。在地圖操作中的放大、縮小、搜索及定位等操作用以下函數(shù)實現(xiàn)[5-6]：

m_ctrlMapX.SetFocus();

m_ctrlMapX.SetCurrentTool(miZoomInTool);

m_ctrlMapX.SetCurrentTool(miPanTool);

m_ctrlMapX.SetCurrentTool(miZoomOutTool);

m_ctrlMapX.ZoomTo(2, centerX, centerY);

其中路徑導航dijkstra算法主要代碼如下：

void CMapShowView::OnDijkstra(){

DijDialog m_dijParameter;

m_dijParameter.DoModal();

}

其中路徑規(guī)劃粒子群算法代碼如下：

void CMapShowView::OnPSO() {

PsoParaDialog psoPDlg;

PsoPDlg.DoModal();

PsoParaDialog* pDlg = new PsoParaDialog();

pDlg->Create(IDD_DIALOG2);

}

3 路徑規(guī)劃軟件功能算法實現(xiàn)

3.1 基于Dijkstra算法路徑導航功能實現(xiàn)

3.1.1 Dijkstra算法簡介

軟件路徑導航功能利用Dijkstra算法實現(xiàn)，Dijkstra算法思想[7]：迅速地擴展頂點集S中的每一個頂點v, S中s頂點和v頂點之間的最短路徑已經(jīng)計算出來。頂點集S初始化為{s}，在搜索s和v之間最短路徑的過程中，S不斷擴展，Dijkstra最短路徑算法本身便可以尋找距離源點s最短路徑的頂點v(v∈V-S)，以此類推，順著頂點v的邊，尋找是否存在一條最短路徑到達另外一個頂點v2。當處理完v2后，算法通過這條路徑計算得到s到v2的最短距離。當s擴展到等于v時，算法終止。

3.1.2 基于Dijkstra算法路徑導航功能實現(xiàn)步驟

(a)初始時，S只包含源點，即S={v}，v的距離為0。U包含除v外的其他頂點，若v與u有邊，U中頂點u距離為邊上的權，若u不是v的出邊鄰接點，u距離無窮大。

(b)從U中選取一個距離v最小的頂點k，把k加入S中(該選定的距離就是v到k的最短路徑長度)。

(c)以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u的距離(經(jīng)過頂點k)比原來距離(不經(jīng)過頂點k)短，則修改頂點u的距離值，修改后的距離值的頂點k的距離加上邊上的權。

(d)重復步驟第(b)步和第(c)步直到所有頂點都包含在S中。

軟件導航功能操作：在對話框中輸入起點和終點，如圖2所示。

圖2 Dijkstra參數(shù)設置

路徑結果紅色軌跡，如圖3所示。

圖3 Dijkstra路徑軌跡

3.2 基于粒子群算法路徑規(guī)劃功能實現(xiàn)

3.2.1 粒子群算法簡介[8-9]

設有n個粒子組成的一個粒子群算法，其搜索區(qū)域空間為D維，Xid=(X1,X2,…XD)指粒子i在D維空間中的位置，Vid=(V1,V2,…VD)指粒子i在D維空間中的飛行速度。Pid為粒子的個體極值，即粒子i在自己的尋優(yōu)歷史中找到的最優(yōu)解，Pgd是目前為止整個群體中所有粒子發(fā)現(xiàn)的最好位置。基本粒子群算法是用于實值連續(xù)空間，然而路徑規(guī)劃屬于組合優(yōu)化問題，引入交換子和交換序來解決路徑規(guī)劃問題，每個粒子速度位置按照式(1)、式(2)更新。

Vid=Vid(c1(Pid-Xid) (c2(Pgd-Xid)

(1)

Xid=Xid+Vid

(2)

其中，c1、c2是兩個隨機數(shù)。路徑規(guī)劃問題n個節(jié)點依次用序號1,2,3,…,n表示，設d為節(jié)點i與節(jié)點j之間的距離，1≤i,j≤n，引入決策變量x見式(3)。

(3)

路徑規(guī)劃問題的適應度函數(shù)M為式(4)。

(4)

3.2.2 粒子群算法進行電子地圖路徑尋優(yōu)步驟[8-9]

(a)在西安市地圖4 525個節(jié)點中選取n個必經(jīng)節(jié)點，初始化粒子個數(shù)m(m

(b)初始化粒子群，每個粒子的位置表示一條路徑，粒子的速度表示一個隨機交換序。

(c)據(jù)粒子當前位置計算其下一個位置Xid。計算A=Pid-Xid，A是一個基本交換序，表示A作用于Xid得到Pid，計算B=Pgd-Xid，B是基本交換序，根據(jù)式(1)計算速度Vid，并將交換序Vid轉換為一個基本交換序，根據(jù)式(2)計算搜索到的新解。

(d)根據(jù)路徑規(guī)劃問題的適應度函數(shù)M，如式(4)，計算每個粒子的適應度值，例如，有10個節(jié)點，某個粒子個體適應度值為這10個必經(jīng)節(jié)點的最短距離，將每個粒子的個體適應度值與歷史記錄中其個體最優(yōu)值比較，若優(yōu)于個體最優(yōu)值，則用此個體適應度值替代個體最優(yōu)適應度值，同樣，把每個粒子的個體最優(yōu)值與粒子群算法的全局最優(yōu)值進行比較，若優(yōu)于全局最優(yōu)值，則利用個體最優(yōu)值進行更新。

(e) 判斷當前迭代是否達到最大迭代次數(shù)，滿足則終止，輸出最優(yōu)解，否則轉至步驟(c)。

粒子群算法參數(shù)設置，如圖4所示。

圖4 參數(shù)設置

找出的最優(yōu)路徑，如圖5所示。

3.2.3 與基于蟻群算法的路徑尋優(yōu)比較

路徑尋優(yōu)問題是在給定節(jié)點的條件下，找到一條遍歷所有節(jié)點且每個節(jié)點只能訪問一次的距離最短的路線。蟻群算法在路徑尋優(yōu)問題應用中取得了良好的效果，但是也存在一些問題：如參數(shù)α，β值設置不當，求解速度會很慢且所得解的結果不理想；蟻群算法計算量大，求解時間較長，最優(yōu)線路是所有的螞蟻選擇同一路線，但實際在給定一定循環(huán)數(shù)的條件下很難達收斂，如本軟件用蟻群算法進行路徑規(guī)劃時在給定1 000次迭代下，每次執(zhí)行出現(xiàn)的結果會不同；蟻群算法收斂速度慢、易陷入局部最優(yōu)，規(guī)劃路徑不一定是最優(yōu)路線。

圖5 粒子群算法路徑軌跡

為緩解以上問題，采用粒子群算法進行路徑規(guī)劃。粒子群優(yōu)化算法的基本思想是通過粒子之間的協(xié)作和信息共享來尋找最優(yōu)解，優(yōu)點在于不用調(diào)節(jié)過多參數(shù)。粒子群算法利用當前位置、全局極值和個體極值，指導粒子下一步位置，每個粒子利用自身經(jīng)驗和群體經(jīng)驗調(diào)整自身的狀態(tài)。粒子群算法可以優(yōu)化參數(shù)，具有相當快的求解速度。實驗表明，粒子群算法在給定迭代條件下，得到的規(guī)劃路徑比較穩(wěn)定，運行時間也較蟻群算法快。

4 總結

設計了電子地圖路徑規(guī)劃算法軟件，對路徑規(guī)劃軟件功能及模型進行了介紹，軟件實現(xiàn)了電子地圖放大、縮小、定位、搜索等功能，基于Dijstrka算法實現(xiàn)了任意兩點求解最短距離，基于粒子群算法實現(xiàn)了多節(jié)點路徑規(guī)劃。后面對軟件功能將進一步完善，為提升軟件運行速度，將設計基于云平臺的路徑規(guī)劃算法軟件。