原文传递
考虑节点耗费的时变随机网络最短路径问题研究
| 论文题名： | 考虑节点耗费的时变随机网络最短路径问题研究 |
| 关键词： | 城市交通;时变随机网络;路径规划;节点耗费 |
| 摘要： | 近年来,随着中国社会经济的迅猛发展和人民生活水平的逐年提高,国民车辆的保有量不断增加,因此,城市交通变得日益拥塞,因车辆慢行和发动机空耗而引起的汽油燃烧不充分所带来的尾气污染日益严重.人们越来越希望城市智能交通系统（ITS）以及车载导航系统能够迅疾快速地给出路径规划，使得车辆能够高速快捷地到达目的地。因此，交通管理者和业界研究人员非常关注行车路径规划和车辆的实时导航问题。然而，现有的一般车载导航系统所提供的路径规划存在如下问题:第一，以两点之间的物理距离最短为目标来规划最短路径，而不是以最短行车时间作为规划路径的目标；其次，没有重视车辆在路口处时间耗费问题，车辆在路口处选择左转、右转、直行或掉头，所耗费的时间是不同的，不可以将其统一归结到对应的路段上；第三，对交通网络的时变性和随机性重视不够。因此，本文以行车时间最短为目标，对考虑节点耗费的时变随机网络最短期望行车时间路径问题进行了研究，具体内容如下： 基于道路网络图是时变的、车辆于不同时间在每条路段和每个节点处的时间耗费均是取有限个数值的离散型随机变量的假设，首先建立了考虑节点耗费的离散型时变随机网络一般最短期望行车时间路径预规划问题、出发时间确定的最短期望行车时间路径预规划问题、具有最晚到达时间约束的最短期望行车时间路径预规划问题的数学模型，并设计了求解以上问题的最优路径搜索算法——逆序标号法，对问题进行求解；为了方便数据的存储和计算，引入向量标签描述车辆于每个时间段在路段和节点处的时间耗费；再次，对逆序标号算法的思想、步骤及其模块进行了详细的介绍，得到该算法的时间复杂度为此处为公式；最后，考虑到车辆在行驶过程中，道路状况会发生实时变化，对考虑实时信息的实时路径诱导问题进行了算法设计，并对算法的步骤进行了详细的介绍。 基于道路网络图是时变的、车辆于每个时间段在每条路段和每个节点处的时间耗费均是服从三角形分布的连续型随机变量的假设，给出了考虑节点耗费的连续型时变随机网络一般最短期望行车时间路径预规划问题、出发时间确定的最短期望行车时间路径预规划问题、最晚到达时间约束的最短期望行车时间路径预规划问题的数学模型；并将逆序标号算法推广到考虑节点耗费的连续型时变随机网络中，得到了解决该问题的最优路径搜索算法。 |
| 作者： | 蒋睿 |
| 专业： | 计算机科学与技术 |
| 导师： | 孙俊清 |
| 授予学位： | 硕士 |
| 授予学位单位： | 天津理工大学 |
| 学位年度： | 2016 |
| 正文语种： | 中文 |
检索历史
应用推荐
