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

王磊， 楊思燕

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

0 引言

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

1 路徑規劃軟件設計模塊與功能

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

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

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

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

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

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

點擊“路徑尋優”，會彈出“路徑導航”及“路徑規劃”子菜單，各個功能如下：

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

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

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

圖1 路徑規劃軟件模塊與功能

2 路徑規劃軟件實現技術

2.1 MapInfo軟件簡介

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

2.2 Mapx控件簡介

MapInfo公司在1996年推出了基于ActiveX技術的MapX控件，MapX控件隨著MapInfo的功能升級而不斷完善。MapX控件提供了二次開發的功能強大的地圖化組件。可以嵌入到在可視化程序開發環境中如Visual Basic、Visual C++等，只需將MapX控件放入到窗體中，進行設置屬性、調用方法和事件，就可實現地理空間數據的常用操作及可視化，并可以實現空間查詢、地理編碼等復雜的地圖信息系統功能[4]。

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

2.3 路徑規劃軟件實現

本軟件把西安市路網電子地圖數據顯示在單文檔上，安裝MapX、MapInfo及Visual Studio 2008開發平臺，導入MapX.h 和 MapX.cpp到工程。其中MapX內置了常用的標準地圖工具，例如放大、縮小、平移、選擇等，在菜單的單擊事件中編寫相關的代碼即可實現相應的功能。在地圖操作中的放大、縮小、搜索及定位等操作用以下函數實現[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();

}

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

void CMapShowView::OnPSO() {

PsoParaDialog psoPDlg;

PsoPDlg.DoModal();

PsoParaDialog* pDlg = new PsoParaDialog();

pDlg->Create(IDD_DIALOG2);

}

3 路徑規劃軟件功能算法實現

3.1 基于Dijkstra算法路徑導航功能實現

3.1.1 Dijkstra算法簡介

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

3.1.2 基于Dijkstra算法路徑導航功能實現步驟

(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的距離(經過頂點k)比原來距離(不經過頂點k)短，則修改頂點u的距離值，修改后的距離值的頂點k的距離加上邊上的權。

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

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

圖2 Dijkstra參數設置

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

圖3 Dijkstra路徑軌跡

3.2 基于粒子群算法路徑規劃功能實現

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

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

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

(1)

Xid=Xid+Vid

(2)

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

(3)

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

(4)

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

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

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

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

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

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

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

圖4 參數設置

找出的最優路徑，如圖5所示。

3.2.3 與基于蟻群算法的路徑尋優比較

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

圖5 粒子群算法路徑軌跡

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

4 總結

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