● 摘要
在研究路网模型和路网存储结构的基础上，以Mapinfo格式电子地图为例，给出了一种有效的路网拓扑算法。该算法综合应用了预判决及数据压缩的方法减少了运算量及地图存储空间，且由于充分考虑了数字地图误差，因而算法得到的结果能很好地反映实际路网。针对规模比较大的地图，给出了一个分区拓扑算法：将地图分成小块并逐一拓扑，合并成最后的路网结构。该算法能够减小拓扑对内存的需求量，并能提高拓扑的速度。 研究了各种路径规划算法。比较了Dijkstra算法和以欧式距离作为估价函数的A*算法的运算量之间的关系。提出并实现了一种交通约束条件下的路径规划算法，分析了算法的复杂性。仿真结果表明，该算法比起解决交通约束问题常用的对偶法减小了3-4倍运算量。针对权值随时间变化的动态网络，给出一种动态网络的路径规划算法。在已知网络所有权值的变化规律的情况下，该算法能够得到在任意给定时刻从起点到终点的权值总和最小的路径。 结合实际工程应用，给出了一种兼容自主式和中心式车辆导航系统的系统设计方案。该系统的终端不仅能够在监控中心的指令下完成导航、信息采集等功能，而且还能脱离监控中心自主完成导航功能。同时，该系统还为终端的地图更新提供了便捷的方法。