论文部分内容阅读
随着时空数据库和智能交通系统的发展,如何解决最小代价路径的查找问题,逐渐成为热点。在道路网络的应用当中,用户真正感兴趣的,一方面是行驶时间最小的路径(最快路径),而这会随着时间的变化而变化;另一方面,道路等级、道路长度等因素也会影响用户对于路径的选择。目前提出的多数方法,大多只是考虑到道路的静态特性(如长度),来查找路径长度最短的路径,而这样的路径并不一定是最快的路径;同时也没有考虑道路的层次结构对于查询时间和用户择路偏好的影响;而且也无法对突发事件等实时交通信息做出响应。
针对所面临的问题,本文在深入分析国外相关领域的研究工作的基础上,分析了道路网络的层次结构和动态权重的特点,设计了一个同时考虑道路网络的静态特性和动态特性的分布式最小代价路径发现算法HTMFI(Hierarchy-basedTime-dependentMinimumcostpathFindingforgivenstarting-timeInterval,),和一个应用于移动环境当中的路径调整算法HTMA(Hierarchy-basedTime-dependentMinimumcostpathAdjusting),并且通过原型系统验证了方法的有效性。
具体来讲,本文的主要研究内容如下:
>提出了一种在给定出发时段条件下,基于道路层次结构的时变网络最小代价路径发现算法HTMFI,算法采用分布式的计算方式,返回最佳的出发时刻和相应的路径,使得在道路上的行驶符合道路层次结构的特点,同时也使得总行驶时间最短;
>针对移动环境,提出了一种最小代价路径调整算法HTMA,可以在路段状况发生变化的情况下,及时获取实时的交通信息,对原计划的路径进行调整;
>在原型系统中实现了上述算法,在真实道路拓扑数据和模拟交通数据之上的实验表明,本文提出的基于道路层次特征的最小代价路径查询算法,大幅度缩小了算法的搜索规模,降低了算法的时间复杂度和空间复杂度,提高了算法的运行效率,适合于解决分布式移动环境中的路径查询问题。