基于随机时间依赖的k期望最短路径研究

摘要

现实的交通网络和通信网络具有随机性和时间依赖性，在随机时间依赖的交通网络中，对于一组给定的起始节点和目的节点，通常要选择一条期望时间最短的路径行走。但在许多实际应用领域，如用户在使用咨询系统或决策支持系统时，除了希望得到最优决策参考外，还希望得到次优，再次优决策参考。
　　当某条路段拥塞或崩溃，就需要寻求其它的次最短路径；当计算出的最短路径可能是不可行或不可接受的方案时，可行或可接受的方案要从k最短路径集合中选取。此外，在高级旅行信息系统中，出行者具有多种类型的需求，例如除了要求路径期望时间最短以外，可能还要求换车次数不大于某个值，或者要求行走时间小于某个常数。因此，反映在最短路径问题上，不仅要寻找从初始节点到目地节点的最短路径，而且还要确定第二短路径，……，直到第k短路径，即一个k最短路径集合。
　　本文建立了静态随机条件下初始节点和目的节点间求解绩效保证路径的模型，根据动态规划理论设计并实现了求解的算法程序，总结了Bayesian推论在动态实时条件下对O-D矩阵预测方面的应用，利用该理论对观测到的数据进行二次更新，以此得到更为准确的实时交通流量信息。

目录

基于随机时间依赖的k期望最短路径研究

THE STUDY OF k-EXPECTED SHORTEST PATHS BASED ON STOCHASTICTIME-DEPENDENCE

摘 要

Abstract

目 录

绪论

1.1 研究的背景和意义

1.2 国内外研究现状及评价

1.3 研究的主要内容和创新点

第2章 k短路径问题的相关理论基础

2.1 随机时间依赖网络模型与最优路径算法

2.2 经典Dijikstra算法介绍

2.3 传统的k短路径算法

2.4 本章小结

第3章 静态随机条件下k期望最短路径问题分析

3.1 问题描述和相关参数设置

3.2 绩效保证路径模型建立及分析

3.3 设计思想

3.4 基于动态规划的程序设计和应用举例

3.5本章小结

第4章 动态实时条件下Bayesian推论对路径信息的更新

4.1 Bayesian相关理论基础

4.2 基于Bayesian推论模型对交通信息量的预测

4.3 应用举例

4.4 本章小结

结 论

参考文献

附 录

哈尔滨工业大学硕士学位论文原创性声明

哈尔滨工业大学硕士学位论文使用授权书

哈尔滨工业大学硕士学位涉密论文管理

致 谢