基于GIS的最優(yōu)路徑算法研究與實(shí)現(xiàn).pdf

1、最優(yōu)路徑規(guī)劃是網(wǎng)絡(luò)優(yōu)化的基本科學(xué)問(wèn)題之一，多年來(lái)產(chǎn)生了大量相關(guān)領(lǐng)域的研究成果，然而計(jì)算機(jī)網(wǎng)絡(luò)與通信系統(tǒng)，基于GIS的智能交通系統(tǒng)、移動(dòng)機(jī)器人、軍事指揮系統(tǒng)等眾多應(yīng)用領(lǐng)域出現(xiàn)的新問(wèn)題，對(duì)最優(yōu)路徑的研究又提出了新的任務(wù)和要求。論文在相關(guān)研究的基礎(chǔ)上，以軍工科研項(xiàng)目為主要需求，重點(diǎn)研究了作戰(zhàn)背景下滿足一定解算條件的單任務(wù)、多任務(wù)最優(yōu)路徑問(wèn)題，最短路徑的高效算法，多約束最優(yōu)路徑問(wèn)題以及時(shí)變網(wǎng)絡(luò)最優(yōu)路徑問(wèn)題。 論文的研究成果主要包括：

2、 （1）基于數(shù)字地圖線狀圖元文件，構(gòu)建了適于最優(yōu)路徑算法研究的道路網(wǎng)拓?fù)浣Y(jié)構(gòu)。 （2）設(shè)計(jì)并實(shí)現(xiàn)了作戰(zhàn)背景下滿足最短和最快解算原則的單任務(wù)、多任務(wù)最優(yōu)路徑輔助決策系統(tǒng)。針對(duì)多任務(wù)算法實(shí)現(xiàn)過(guò)程中出現(xiàn)的路段沖突，提出了同步法和異步法兩種解決方案。原型系統(tǒng)試驗(yàn)顯示上述算法有效可行。 （3）最短路徑算法效率是戰(zhàn)時(shí)輔助軍事決策、應(yīng)急救援等系統(tǒng)普遍關(guān)注和迫切需要解決的問(wèn)題。論文針對(duì)項(xiàng)目地理信息系統(tǒng)平臺(tái)中路網(wǎng)道路分布不均、道路不規(guī)

3、則等特點(diǎn)，提出了兩種最短路徑的改進(jìn)算法：比值系數(shù)τ分段取值的矩形限制搜索區(qū)域算法和帶啟發(fā)因子的直線優(yōu)化A*算法。上述兩種改進(jìn)算法穩(wěn)定性好，且在路段搜索范圍、算法的速度、資源消耗等方面較經(jīng)典Dijkstra算法有較大改善。 （4）針對(duì)多弧權(quán)網(wǎng)絡(luò)最優(yōu)路徑問(wèn)題，提出了多約束最優(yōu)路徑問(wèn)題的MCOP算法；將啟發(fā)式思想引入多約束最優(yōu)路徑問(wèn)題的研究，提出了多約束最優(yōu)路徑問(wèn)題的A*_MCOP算法。實(shí)例驗(yàn)證了上述算法的正確性以及A*_MCOP算法

4、的優(yōu)越性。 （5）系統(tǒng)研究了FIFO網(wǎng)絡(luò)、非FIFO網(wǎng)絡(luò)最短時(shí)間路徑的算法理論并給出相應(yīng)的證明。所提出的非FIFO網(wǎng)絡(luò)最短路徑理論為解決非FIFO網(wǎng)絡(luò)最短時(shí)間路徑問(wèn)題提供了新的途徑。文中還對(duì)各種等待約束情況下的“前向”、“反向”最短時(shí)間路徑算法進(jìn)行了設(shè)計(jì)和總結(jié)。 對(duì)于最優(yōu)路徑算法研究這一具有很強(qiáng)應(yīng)用背景的課題，本文從軍工科研項(xiàng)目需求出發(fā)，通過(guò)對(duì)已有算法的總結(jié)及現(xiàn)存問(wèn)題的分析，提出了一系列新的算法思想與算法理論。實(shí)際系統(tǒng)運(yùn)