電子地圖路徑規(guī)劃軟件設(shè)計(jì)范文

本站小編為你精心準(zhǔn)備了電子地圖路徑規(guī)劃軟件設(shè)計(jì)參考范文，愿這些范文能點(diǎn)燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

摘要：設(shè)計(jì)了基于粒子群算法的電子地圖路徑規(guī)劃軟件，可以實(shí)現(xiàn)對(duì)西安市電子地圖放大、縮小、定位、搜索、路徑導(dǎo)航等功能，根據(jù)Dijsktra算法實(shí)現(xiàn)路徑導(dǎo)航功能，根據(jù)粒子群算法解決真實(shí)路徑的路徑規(guī)劃問題，可以在指定的節(jié)點(diǎn)范圍內(nèi)尋找一條較優(yōu)路徑，達(dá)到路徑規(guī)劃目的。

關(guān)鍵詞：粒子群算法；Dijsktra算法；路徑規(guī)劃

0引言

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

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

規(guī)劃軟件主要模型主要分為地圖操作和路徑規(guī)劃，其中地圖操作主要有放大、縮小、定位搜索等，路徑規(guī)劃主要是路徑導(dǎo)航與路徑尋優(yōu)。點(diǎn)擊“地圖操作”，會(huì)彈出“放大”、“縮小”、“定位”、“搜索”子菜單，各個(gè)功能如下：（1）放大：點(diǎn)擊地圖上任意位置，地圖將以該地點(diǎn)為中心放大一倍比例尺顯示。（2）縮小：點(diǎn)擊地圖上任意位置，地圖將以該地點(diǎn)為中心縮小一倍比例尺顯示。（3）定位：可以通過定位系統(tǒng)實(shí)時(shí)定位。（4）搜索：在地圖上尋找目標(biāo)位置。點(diǎn)擊“路徑尋優(yōu)”，會(huì)彈出“路徑導(dǎo)航”及“路徑規(guī)劃”子菜單，各個(gè)功能如下：（1）路徑導(dǎo)航：輸入起始點(diǎn)和終點(diǎn)，可以計(jì)算出一條最短路徑。（2）路徑規(guī)劃：選擇若干個(gè)結(jié)點(diǎn)，可以計(jì)算出經(jīng)過這些結(jié)點(diǎn)的一條較優(yōu)路徑。

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

2．1MapInfo軟件簡(jiǎn)介MapInfo由美國(guó)MapInfo公司開發(fā)，是一款地理信息系統(tǒng)二次開發(fā)軟件，能夠提供數(shù)據(jù)可視化、信息地圖化的桌面解決方案。它集成多種數(shù)據(jù)庫(kù)數(shù)據(jù)、結(jié)合計(jì)算機(jī)地圖方法、采用數(shù)據(jù)庫(kù)技術(shù)、融入地理信息系統(tǒng)分析功能，可以為各行各業(yè)所用的軟件系統(tǒng)提供服務(wù)［2］。MapInfo全稱為Mapping＋I(xiàn)nformation即地圖對(duì)象＋屬性數(shù)據(jù)。MapInfo采用“空間實(shí)體＋空間索引”的拓?fù)潢P(guān)系模型，其空間實(shí)體是地理實(shí)體的抽象，類型包括點(diǎn)、線、面，每個(gè)空間實(shí)體對(duì)象都具有自身所有屬性，一個(gè)圖層由多個(gè)空間實(shí)體構(gòu)成。空間索引能夠定位到給定的空間坐標(biāo)，快速搜索到坐標(biāo)范圍中的空間對(duì)象。MapInfo利用雙數(shù)據(jù)庫(kù)存儲(chǔ)模式（空間、屬性數(shù)據(jù)），空間數(shù)據(jù)以MapInfo的自定義格式保存在文件中，屬性數(shù)據(jù)存儲(chǔ)在關(guān)系數(shù)據(jù)庫(kù)的屬性表中，他們之間通過一定的索引機(jī)制互相通信［3］。

2．2Mapx控件簡(jiǎn)介MapInfo公司在1996年推出了基于ActiveX技術(shù)的MapX控件，MapX控件隨著MapInfo的功能升級(jí)而不斷完善。MapX控件提供了二次開發(fā)的功能強(qiáng)大的地圖化組件。可以嵌入到在可視化程序開發(fā)環(huán)境中如VisualBasic、VisualC＋＋等，只需將MapX控件放入到窗體中，進(jìn)行設(shè)置屬性、調(diào)用方法和事件，就可實(shí)現(xiàn)地理空間數(shù)據(jù)的常用操作及可視化，并可以實(shí)現(xiàn)空間查詢、地理編碼等復(fù)雜的地圖信息系統(tǒng)功能［4］。MapX與MapInfo使用一致的地圖數(shù)據(jù)格式，主要功能有顯示MapInfo格式的地圖數(shù)據(jù)，支持地圖的放大、縮小、平移、選擇等操作，圖層的自由控制，支持動(dòng)態(tài)圖層和自定義圖層，專題地圖制作，簡(jiǎn)單的地理查詢等。本軟件基于MapX組件進(jìn)行二次開發(fā)。2．3路徑規(guī)劃軟件實(shí)現(xiàn)本軟件把西安市路網(wǎng)電子地圖數(shù)據(jù)顯示在單文檔上，安裝MapX、MapInfo及VisualStudio2008開發(fā)平臺(tái)，導(dǎo)入MapX．h和MapX．cpp到工程。其中MapX內(nèi)置了常用的標(biāo)準(zhǔn)地圖工具，例如放大、縮小、平移、選擇等，在菜單的單擊事件中編寫相關(guān)的代碼即可實(shí)現(xiàn)相應(yīng)的功能。

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

3．1基于Dijkstra算法路徑導(dǎo)航功能實(shí)現(xiàn)

3．1．1Dijkstra算法簡(jiǎn)介軟件路徑導(dǎo)航功能利用Dijkstra算法實(shí)現(xiàn)，Dijkstra算法思想［7］：迅速地?cái)U(kuò)展頂點(diǎn)集S中的每一個(gè)頂點(diǎn)v，S中s頂點(diǎn)和v頂點(diǎn)之間的最短路徑已經(jīng)計(jì)算出來(lái)。頂點(diǎn)集S初始化為｛s｝，在搜索s和v之間最短路徑的過程中，S不斷擴(kuò)展，Dijkstra最短路徑算法本身便可以尋找距離源點(diǎn)s最短路徑的頂點(diǎn)v（v∈V－S），以此類推，順著頂點(diǎn)v的邊，尋找是否存在一條最短路徑到達(dá)另外一個(gè)頂點(diǎn)v2。當(dāng)處理完v2后，算法通過＜s，v2，v3＞這條路徑計(jì)算得到s到v2的最短距離。當(dāng)s擴(kuò)展到等于v時(shí)，算法終止。

3．1．2基于Dijkstra算法路徑導(dǎo)航功能實(shí)現(xiàn)步驟（a）初始時(shí)，S只包含源點(diǎn)，即S＝｛v｝，v的距離為0。U包含除v外的其他頂點(diǎn)，若v與u有邊，U中頂點(diǎn)u距離為邊上的權(quán)，若u不是v的出邊鄰接點(diǎn)，u距離無(wú)窮大。（b）從U中選取一個(gè)距離v最小的頂點(diǎn)k，把k加入S中（該選定的距離就是v到k的最短路徑長(zhǎng)度）。（c）以k為新考慮的中間點(diǎn)，修改U中各頂點(diǎn)的距離；若從源點(diǎn)v到頂點(diǎn)u的距離（經(jīng)過頂點(diǎn)k）比原來(lái)距離（不經(jīng)過頂點(diǎn)k）短，則修改頂點(diǎn)u的距離值，修改后的距離值的頂點(diǎn)k的距離加上邊上的權(quán)。（d）重復(fù)步驟第（b）步和第（c）步直到所有頂點(diǎn)都包含在S中。

3．2基于粒子群算法路徑規(guī)劃功能實(shí)現(xiàn)

3．2．1粒子群算法簡(jiǎn)介［8－9］設(shè)有n個(gè)粒子組成的一個(gè)粒子群算法，其搜索區(qū)域空間為D維，Xid＝（X1，X2，…XD）指粒子i在D維空間中的位置，Vid＝（V1，V2，…VD）指粒子i在D維空間中的飛行速度。Pid為粒子的個(gè)體極值，即粒子i在自己的尋優(yōu)歷史中找到的最優(yōu)解，Pgd是目前為止整個(gè)群體中所有粒子發(fā)現(xiàn)的最好位置。

3．2．2粒子群算法進(jìn)行電子地圖路徑尋優(yōu)步驟［8－9］（a）在西安市地圖4525個(gè)節(jié)點(diǎn)中選取n個(gè)必經(jīng)節(jié)點(diǎn)，初始化粒子個(gè)數(shù)m（m＜n）、迭代次數(shù)Nc、慣性因子c1、學(xué)習(xí)因子c2等參數(shù)。（b）初始化粒子群，每個(gè)粒子的位置表示一條路徑，粒子的速度表示一個(gè)隨機(jī)交換序。（c）據(jù)粒子當(dāng)前位置計(jì)算其下一個(gè)位置Xid。計(jì)算A＝Pid－Xid，A是一個(gè)基本交換序，表示A作用于Xid得到Pid，計(jì)算B＝Pgd－Xid，B是基本交換序，根據(jù)式（1）計(jì)算速度Vid，并將交換序Vid轉(zhuǎn)換為一個(gè)基本交換序，根據(jù)式（2）計(jì)算搜索到的新解。（d）根據(jù)路徑規(guī)劃問題的適應(yīng)度函數(shù)M，如式（4），計(jì)算每個(gè)粒子的適應(yīng)度值，例如，有10個(gè)節(jié)點(diǎn)，某個(gè)粒子個(gè)體適應(yīng)度值為這10個(gè)必經(jīng)節(jié)點(diǎn)的最短距離，將每個(gè)粒子的個(gè)體適應(yīng)度值與歷史記錄中其個(gè)體最優(yōu)值比較，若優(yōu)于個(gè)體最優(yōu)值，則用此個(gè)體適應(yīng)度值替代個(gè)體最優(yōu)適應(yīng)度值，同樣，把每個(gè)粒子的個(gè)體最優(yōu)值與粒子群算法的全局最優(yōu)值進(jìn)行比較，若優(yōu)于全局最優(yōu)值，則利用個(gè)體最優(yōu)值進(jìn)行更新。（e）判斷當(dāng)前迭代是否達(dá)到最大迭代次數(shù)，滿足則終止，輸出最優(yōu)解，否則轉(zhuǎn)至步驟（c）。

3．2．3與基于蟻群算法的路徑尋優(yōu)比較路徑尋優(yōu)問題是在給定節(jié)點(diǎn)的條件下，找到一條遍歷所有節(jié)點(diǎn)且每個(gè)節(jié)點(diǎn)只能訪問一次的距離最短的路線。蟻群算法在路徑尋優(yōu)問題應(yīng)用中取得了良好的效果，但是也存在一些問題：如參數(shù)α，β值設(shè)置不當(dāng)，求解速度會(huì)很慢且所得解的結(jié)果不理想；蟻群算法計(jì)算量大，求解時(shí)間較長(zhǎng)，最優(yōu)線路是所有的螞蟻選擇同一路線，但實(shí)際在給定一定循環(huán)數(shù)的條件下很難達(dá)收斂，如本軟件用蟻群算法進(jìn)行路徑規(guī)劃時(shí)在給定1000次迭代下，每次執(zhí)行出現(xiàn)的結(jié)果會(huì)不同；蟻群算法收斂速度慢、易陷入局部最優(yōu)，規(guī)劃路徑不一定是最優(yōu)路線。為緩解以上問題，采用粒子群算法進(jìn)行路徑規(guī)劃。粒子群優(yōu)化算法的基本思想是通過粒子之間的協(xié)作和信息共享來(lái)尋找最優(yōu)解，優(yōu)點(diǎn)在于不用調(diào)節(jié)過多參數(shù)。粒子群算法利用當(dāng)前位置、全局極值和個(gè)體極值，指導(dǎo)粒子下一步位置，每個(gè)粒子利用自身經(jīng)驗(yàn)和群體經(jīng)驗(yàn)調(diào)整自身的狀態(tài)。粒子群算法可以優(yōu)化參數(shù)，具有相當(dāng)快的求解速度。實(shí)驗(yàn)表明，粒子群算法在給定迭代條件下，得到的規(guī)劃路徑比較穩(wěn)定，運(yùn)行時(shí)間也較蟻群算法快。

4總結(jié)

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

參考文獻(xiàn)

［1］王華東，李巍．粒子群算法的物流配送路徑優(yōu)化研究［J］．計(jì)算機(jī)仿真，2012，29（5）：243－246．

［2］阮曹華，徐緒忠，李華貴，等．在MapInfo電子地圖中搜尋最短路徑的實(shí)現(xiàn)［J］．微計(jì)算機(jī)信息，2017（28）：189－180．

［3］彭剛，王艷琴，王濤，等．基于MapInfo與MapX的電子地圖［J］．計(jì)算機(jī)系統(tǒng)應(yīng)用，2011，20（9）：153－156．

［4］楊斌，葉云霞，劉小勇．基于MapX的組件式GIS集成系統(tǒng)的開發(fā)與應(yīng)用［J］．測(cè)繪與空間地理信息，2005（3）：29－32．

［5］劉德利，張亞雙．基于MapX的水資源信息查詢系統(tǒng)的設(shè)計(jì)與開發(fā)［J］．吉林水利，2006（3）：5－7．

［6］陳先龍，翁勇．基于MapX的GIS－T應(yīng)用開發(fā)實(shí)例［J］．交通與計(jì)算機(jī)，2003（4）：72－74．

［7］潘開靈，董晶晶．基于Dijkstra算法的物流運(yùn)輸最短路徑的研究［J］，中國(guó)集體經(jīng)濟(jì)，2011（28）：121－122．

［8］黃嵐，王康平，周春光，等．粒子群優(yōu)化算法求解旅行商問題［J］．吉林大學(xué)學(xué)報(bào)（理學(xué)版），2003，10（41）：77－480．

［9］吳高超．基于粒子群算法的路徑規(guī)劃問題研究［D］．秦皇島：燕山大學(xué)，2016（5）

作者；王磊；楊思燕 單位：陜西廣播電視大學(xué)信息與智能技術(shù)學(xué)院