约束限制下的路网最优路径算法研究及其应用

摘要

在智能交通、网络通信、运输调度及物流工程等领域中,存在着大量有待于研究和解决的约束条件下的最优路径问题,这些问题通常比较复杂,解决起来有一定的难度,但是,是否对这些问题进行优化,如何优化对实际经济效益和社会效益有的很大的影响。
　　本文对不同约束条件下的网络最优路径问题进行了总结和概括,重点研究和讨论以下两类问题:第一,含有禁止转向通行限制的网络最优路径优化算法,以及最优路径出现P型、U型路线的路径记录与指向问题;第二,行驶路径必须经过网络中一些指定节点的最短路问题。研究中采用的方法及获得的主要成果如下:
　　1.推广了Floyd迭代算法,使其路径指向功能更加完备。通过在Floyd算法中引入正向和反向指向矩阵及其应用规则,构建出了一种解决含有禁止转向的网络最优路径问题的算法,这种算法能够方便的记忆和指出最优路径走向,包括最优路径出现 P型(绕圈路段)、U型(有往返路段)及这两种情况都出现的非简单路径的记忆和走向。与国内外的研究方法相比较,避免了对网络进行繁琐的手工预处理,因此,使用简便、效率更高。
　　2.对满足某些节点有服务限制下的网络最优路径问题,进行了初步研究。利用Floyd算法的特点,给出了一种用路径值上限进行筛选、优化的启发式算法,这种算法可以指出优化路径出现各种非简单路的走向。对研究的上述两类问题,本文分别建立了相应的数学模型及其算法,在理论上论证了算法的可行性和优化效果,通过例题对算法进行了演示。论文最后,在上述问题的研究基础上,提出了一些更具现实意义的研究展望。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 论文选题的应用背景与依据

1.2 约束限制下的路网最优路径问题的研究目的和意义

1.3 国内外对有约束限制的最优路径优化问题的研究现状

第二章 车载导航系统概览与最优路径优化算法问题

2.1 车载导航系统概览

2.2 最优路径问题及其分类

2.3 常用的最优路径算法

2.4 目前最短路径优化算法的部分研究热点

2.5 本章小结

第三章 有转向限制的网络最优路径算法及其应用研究

3.1 含有转向限制的网络路径问题概述

3.2 Floyd算法及其推广算法

3.3 解决含有转向限制路网最短路问题的推广Floyd算法

3.4 含P型和U型圈路最优路径算法及其路径读取问题研究

3.5 结束语

第四章 总结与展望

4.1 本文研究内容总结

4.2 展望

参考文献

致谢