车辆导航系统路径规划技术的研究

论文摘要

路径规划是GPS车辆定位导航系统的核心功能和关键技术,对其的研究和应用是影响智能交通系统（ITS）发展的重要环节。路径规划算法在嵌入式系统的应用更是随着我国私家车拥有量的日益增多而应用更为广泛。但是目前普遍存在着由于系统资源有限和路网数据的巨大而造成的运行速度慢、规划结果不合理、重新规划迟缓等问题。本文针对这些问题,首先从路网数据模型入手,针对用于车辆导航系统的物理存储格式的标准NDS,对其数据横向分块和纵向分层的思想进行了论述。接着对导航领域应用广泛的最短路径算法进行了梳理,研究了几种针对Dijkstra算法改进的扩展算法。在此基础上提出了一种双向扩展、分层搜索,在基础层格网内以弧段为扩展项、在基础层格网间和全国层以结点为扩展项的混合扩展算法.解决了嵌入式系统下的运行速度慢、规划结果不合理问题,破解了带转向限制路径规划的难题,缩短重新规划的计算时间。本文最后探讨了路径规划在实际工程中的应用---Anyway车载导航项目路径规划模块的开发,包括模块的需求分析、接口定义和设计实现的过程。对其中的主要步骤选点功能、最短路径功能和路线做成功能的设计思想、使用算法和程序流程进行分析,并对导航模块进行了实测。实验表明算法是可实现的、高效的,能够满足嵌入式的应用。

论文目录

• 摘要
• ABSTRACT
• 符号说明
• 第一章 引言
• 1.1 背景及问题的提出
• 1.2 国内外研究现状
• 1.3 研究的目标及其主要的内容
• 1.4 本文的组织结构及其章节编排
• 第二章 路径规划相关技术研究
• 2.1 约束条件
• 2.2 存在的问题
• 2.2.1 交通规则约束问题
• 2.2.2 地址空间不足问题
• 2.2.3 重引导效率问题
• 2.2.4 封闭和动态交通的影响
• 2.3 路网数据模型
• 2.3.1 地理数据的分割
• 2.3.2 路网数据模型
• 2.4 算法研究
• 2.4.1 图论及相关概念
• 2.4.2 最短路径问题
• 2.4.3 DIJKSTRA 算法及改进算法
• 2.4.4 目标导向算法
• 2.4.5 分层算法
• 2.5 本章小结
• 第三章 路径规划模块的设计
• 3.1 项目功能
• 3.2 项目框架
• 3.3 路径规划子系统
• 3.3.1 功能需求
• 3.3.2 非功能性需求
• 3.3.3 调用接口描述
• 3.4 路径规划模块设计
• 3.5 选点功能设计
• 3.6 路线做成功能
• 3.7 本章小结
• 第四章 最短路径算法
• 4.1 算法特点
• 4.1.1 基于弧段的探索
• 4.1.2 分层探索
• 4.1.3 双向扩展
• 4.1.4 混合搜索
• 4.2 领域模型
• 4.2.1 领域类及关系
• 4.2.2 对象间扩展类型
• 4.3 算法及流程
• 4.3.1 交通规则在弧段扩展中的应用
• 4.3.2 封闭功能实现
• 4.3.3 偏航后重规划的加速
• 4.3.4 二叉堆优先级队列
• 4.3.5 后续处理说明
• 4.3.6 算法过程
• 4.4 本章小结
• 第五章 模块实现及实验分析
• 5.1 实现效果
• 5.2 实验结果
• 5.2.1 近距离查询
• 5.2.2 中距离查询
• 5.2.3 远距离查询
• 5.2.4 不同优先模式的比较
• 5.3 综合分析
• 5.4 本章小结
• 第六章 总结与展望
• 6.1 工作回顾
• 6.2 成果及意义
• 6.3 存在的问题及进一步的工作
• 参考文献
• 致谢
• 作者攻读学位期间发表的论文