《基于随机时间依赖的k期望最短路径研究》由会员分享，可在线阅读，更多相关《基于随机时间依赖的k期望最短路径研究（64页珍藏版）》请在金锄头文库上搜索。
1、管理学硕士学位论文基于随机时间依赖的k 期望最短路径研究王冰哈尔滨工业大学2007 年 6 月国内图书分类号：F224.3国际图书分类号：65管理学硕士学位论文基于随机时间依赖的k 期望最短路径研究硕士导导研究生：王冰师：李力副教授师：李端教授（香港中文大学）申请学位：管理学硕士学科、专业：企业管理所在单位：深圳研究生院经济管理学科部答辩日期：2007 年 6 月授予学位单位：哈尔滨工业大学Classified Index: F224.3U.D.C: 65Dissertation for the Master Degree of ManagementTHE STUDY OF k-EXPECTE
2、D SHORTESTPATHS BASED ON STOCHASTICTIME-DEPENDENCECandidate:Wang BingSupervisor:Prof. LI Li,Prof. LI DuanAcademic Degree Applied for:Specialty:Affiliation:Date of Defence:Degree-Conferring-Institution:Master of ManagementEnterprise ManagementShenzhen Graduate SchoolJune, 2007Harbin Institute of Tech
3、nology摘要摘要现实的交通网络和通信网络具有随机性和时间依赖性，在随机时间依赖的交通网络中，对于一组给定的起始节点和目的节点，通常要选择一条期望时间最短的路径行走。但在许多实际应用领域，如用户在使用咨询系统或决策支持系统时，除了希望得到最优决策参考外，还希望得到次优，再次优决策参考。当某条路段拥塞或崩溃，就需要寻求其它的次最短路径；当计算出的最短路径可能是不可行或不可接受的方案时，可行或可接受的方案要从 k最短路径集合中选取。此外，在高级旅行信息系统中，出行者具有多种类型的需求，例如除了要求路径期望时间最短以外，可能还要求换车次数不大于某个值，或者要求行走时间小于某个常数。因此，反映在最短
4、路径问题上，不仅要寻找从初始节点到目地节点的最短路径，而且还要确定第二短路径，直到第 k短路径，即一个 k最短路径集合。本文建立了静态随机条件下初始节点和目的节点间求解绩效保证路径的模型，根据动态规划理论设计并实现了求解的算法程序，总结了 Bayesian推论在动态实时条件下对 O-D矩阵预测方面的应用，利用该理论对观测到的数据进行二次更新，以此得到更为准确的实时交通流量信息。关键词k期望最短路径；绩效保证路径；贝叶斯推论；O-D矩阵- I -哈尔滨工业大学管理学硕士学位论文AbstractStochastic and time-dependent properties are found i
5、n many moderntransportation system and communication network. In the stochastic and time-dependent network, for each given origin destination pair at a specific time, thetime-shortest path will be generally chose. However, the travelers need the secondbest and the third best decision-making in some
6、consulting systems or decisionsystems.When the link is crowed, the travelers will look for the second-shortest path;when the results from the shortest paths are unfeasible or unacceptable, thefeasible and acceptable plan will come from the set of k-shortest paths. Besides,in the advanced traffic inf
7、ormation system, the travelers will demand differently:not only the lowest expected time, but also the time is less than a constant, or thechanging number is no more than a constant. On the problem of the shortest paths,the shortest paths, the second shortest path, and the k-shortest will beneeded,
8、which is a set of k-shortest paths.In this paper, Firstly, building the model of performance guaranteed shortestpath and designing the algorithm program based on dynamic programming.Secondly, summarizing the application of Bayesian Inference in the O-D matrixestimation. Thirdly, updating the traffic
9、 data according to the theory andproviding the more accurate traffic information to the travelers.Keywordsk-expected shortest path; performance guaranteed shortest path;Bayesian Inference; O-D Matrix- II -目录目录摘要 . IAbstract . II第 1 章绪论 .11.1研究的背景和意义 .11.2国内外研究现状及评价 .21.2.1国外研究现状 .21.2.2国内研究现状 .71.2.3国内外研究评价 .71.3研究的主要内容和创新点 .81.3.1研究的主要内容 .81.3.2研究的创新点 .8第 2 章 k短路径问题的相关理论基础 .92.1随机时间依赖网络模型与最优路径算法 .92.1.1问题的提出 .92.1.2随机时间依赖网络模型 .92.1.3 k期望最短路径算法的理论基础 .112.2经典Dijikstra算法介绍 .
