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

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

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

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

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