资源描述：
《基于随机时间依赖的k期望最短路径研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、管理学硕士学位论文基于随机时间依赖的k期望最短路径研究王冰哈尔滨工业大学2007年6月国内图书分类号：F224.3国际图书分类号：65管理学硕士学位论文基于随机时间依赖的k期望最短路径研究硕士导导研究生：王冰师：李力副教授师：李端教授（香港中文大学）申请学位：管理学硕士学科、专业：企业管理所在单位：深圳研究生院经济管理学科部答辩日期：2007年6月授予学位单位：哈尔滨工业大学ClassifiedIndex:F224.3U.D.C:65DissertationfortheMasterDegreeofManagementTHESTUDYOFk-E
2、XPECTEDSHORTESTPATHSBASEDONSTOCHASTICTIME-DEPENDENCECandidate:WangBingSupervisor:Prof.LILi,Prof.LIDuanAcademicDegreeAppliedfor:Specialty:Affiliation:DateofDefence:Degree-Conferring-Institution:MasterofManagementEnterpriseManagementShenzhenGraduateSchoolJune,2007HarbinIns
3、tituteofTechnology摘要摘要现实的交通网络和通信网络具有随机性和时间依赖性，在随机时间依赖的交通网络中，对于一组给定的起始节点和目的节点，通常要选择一条期望时间最短的路径行走。但在许多实际应用领域，如用户在使用咨询系统或决策支持系统时，除了希望得到最优决策参考外，还希望得到次优，再次优决策参考。当某条路段拥塞或崩溃，就需要寻求其它的次最短路径；当计算出的最短路径可能是不可行或不可接受的方案时，可行或可接受的方案要从k最短路径集合中选取。此外，在高级旅行信息系统中，出行者具有多种类型的需求，例如除了要求路径期望时间最短以外，可能还
4、要求换车次数不大于某个值，或者要求行走时间小于某个常数。因此，反映在最短路径问题上，不仅要寻找从初始节点到目地节点的最短路径，而且还要确定第二短路径，……，直到第k短路径，即一个k最短路径集合。本文建立了静态随机条件下初始节点和目的节点间求解绩效保证路径的模型，根据动态规划理论设计并实现了求解的算法程序，总结了Bayesian推论在动态实时条件下对O-D矩阵预测方面的应用，利用该理论对观测到的数据进行二次更新，以此得到更为准确的实时交通流量信息。关键词k期望最短路径；绩效保证路径；贝叶斯推论；O-D矩阵-I-哈尔滨工业大学管理学硕士学位论文A
5、bstractStochasticandtime-dependentpropertiesarefoundinmanymoderntransportationsystemandcommunicationnetwork.Inthestochasticandtime-dependentnetwork,foreachgivenorigindestinationpairataspecifictime,thetime-shortestpathwillbegenerallychose.However,thetravelersneedthesecondbest
6、andthethirdbestdecision-makinginsomeconsultingsystemsordecisionsystems.Whenthelinkiscrowed,thetravelerswilllookforthesecond-shortestpath;whentheresultsfromtheshortestpathsareunfeasibleorunacceptable,thefeasibleandacceptableplanwillcomefromthesetofk-shortestpaths.Besides,inth
7、eadvancedtrafficinformationsystem,thetravelerswilldemanddifferently:notonlythelowestexpectedtime,butalsothetimeislessthanaconstant,orthechangingnumberisnomorethanaconstant.Ontheproblemoftheshortestpaths,theshortestpaths,thesecondshortestpath,……,andthek-shortestwillbeneeded,w
8、hichisasetofk-shortestpaths.Inthispaper,Firstly,buildingthemodelofperforman
