论文部分内容阅读
最优路径规划是网络优化的基本科学问题之一,多年来产生了大量相关领域的研究成果,然而计算机网络与通信系统,基于GIS的智能交通系统、移动机器人、军事指挥系统等众多应用领域出现的新问题,对最优路径的研究又提出了新的任务和要求。论文在相关研究的基础上,以军工科研项目为主要需求,重点研究了作战背景下满足一定解算条件的单任务、多任务最优路径问题,最短路径的高效算法,多约束最优路径问题以及时变网络最优路径问题。论文的研究成果主要包括:(1)基于数字地图线状图元文件,构建了适于最优路径算法研究的道路网拓扑结构。(2)设计并实现了作战背景下满足最短和最快解算原则的单任务、多任务最优路径辅助决策系统。针对多任务算法实现过程中出现的路段冲突,提出了同步法和异步法两种解决方案。原型系统试验显示上述算法有效可行。(3)最短路径算法效率是战时辅助军事决策、应急救援等系统普遍关注和迫切需要解决的问题。论文针对项目地理信息系统平台中路网道路分布不均、道路不规则等特点,提出了两种最短路径的改进算法:比值系数τ分段取值的矩形限制搜索区域算法和带启发因子的直线优化A~*算法。上述两种改进算法稳定性好,且在路段搜索范围、算法的速度、资源消耗等方面较经典Dijkstra算法有较大改善。(4)针对多弧权网络最优路径问题,提出了多约束最优路径问题的MCOP算法;将启发式思想引入多约束最优路径问题的研究,提出了多约束最优路径问题的A~*_MCOP算法。实例验证了上述算法的正确性以及A~*_MCOP算法的优越性。(5)系统研究了FIFO网络、非FIFO网络最短时间路径的算法理论并给出相应的证明。所提出的非FIFO网络最短路径理论为解决非FIFO网络最短时间路径问题提供了新的途径。文中还对各种等待约束情况下的“前向”、“反向”最短时间路径算法进行了设计和总结。对于最优路径算法研究这一具有很强应用背景的课题,本文从军工科研项目需求出发,通过对已有算法的总结及现存问题的分析,提出了一系列新的算法思想与算法理论。实际系统运行结果及算法实例表明文中所提出的最优路径算法的正确性和有效性。