考虑路段随机行程时间异质性的交通网络可靠路径规划模型和算法

为应对交通网络路段随机行程时间异质性分布情况下,出行者路径选择决策对行程时间可靠性和不可靠性方面的关注,以均值-超量行程时间为优化准则,构建了一种新的可靠路径规划模型;为刻画交通网络中不同路段随机行程时间的异质性分布,以行程时间前四阶矩为输入,解析估计了均值-超量行程时间,以免于现有研究均一化的分布假设;利用均值-超量行程时间的理论特性,提出了以Dijkstra最短路算法和K-最短路算法为基础的精确和近似两阶段算法;以Monte Carlo模拟方法为基准,验证了基于前四阶矩的均值-超量行程时间解析估计方法的精确性;通过求解算例网络中所有OD对的最短均值-超量路径,分析了近似两阶段算法的精确性和计算效率。研究结果表明：现有研究中常用的路段随机行程时间正态分布假设会忽略偏度和峰度系数对可靠路径选择结果的影响,而均值-超量行程时间解析估计方法所得近似值与真值的相对误差不超过0.13%;当K-最短路算法中K为10时,近似两阶段算法求解的全网络OD对最短均值-超量路径中,有0.11%的OD对的最小均值-超量与精确两阶段算法求解结果不同,最大相对误差为3.35%;针对由随机选择的5个节点与其他节点组成的OD对,近似两阶段算法平均计算时间与精确两阶段算法平均计算时间的比值范围为0.87%~22.96%,表明近似两阶段算法不仅保证了其求解准确性,还可有效提高计算效率;提出的模型和算法能够接纳网络中不同路段随机行程时间分布具有异质性的现实特征,其路径规划结果能够更好地体现出行者对按时到达可靠性和迟到风险的关注诉求。     

随机交通网络最小条件风险路径问题

为了研究风险性对于拥挤交通网络车辆的路径选择行为的影响,定义条件风险值为路径目标函数,建立随机交通网络环境下最小条件风险路径问题数学模型,证明了路径的条件风险值的次可加性,把最小条件风险路径问题转化为基于路段的最小条件风险路径问题,构造基于动态规划的标号算法求解该问题,针对Sioux Falls Network展开数值试验,对在不同风险置信水平条件下随机交通网络最小条件风险路径的计算结果进行了比较分析。结果表明:不同风险置信水平条件下求解的最小条件风险路径是不同的,风险置信水平对最优路径的选择具有重大影响。     

转向约束网络中的对偶最短路径树原理及其原型算法

为比较有无转向约束条件下最短路径特征及其搜索算法的异同点, 基于对偶图理论证明了转向约束网络中从单个源点到所有弧的最短路径集构成其对偶网络的生成树, 提出了对偶最短路径树(DSPT)概念, 并利用其分析算法之间的关系。研究结果表明: 转向约束下的现有求解方法包括弧标号算法、节点标号算法和对偶网络法都可以统一到DSPT算法框架内, 而且与无转向约束的最短路径树(SPT)算法在路径搜索策略上是相同的; 对于转向约束网络中的最短路径问题可建立一个DSPT原型算法, 结合各种SPT标号技术能设计出更多的有效算法。     

模糊随机最短路径问题模型与算法

最短路径问题在现实生活中有着广泛应用,许多专家学者对此问题进行了深入研究.到目前为止,所有这些研究都是针对静态最短路径问题以及不确定最短路径问题中具有模糊或随机参数的问题.然而在现实世界中,有些系统中有很多不确定因素,因此很有必要对具有多重不确定参数的最短路径问题进行研究.本文主要研究具有模糊随机参数的最短路径问题,基于机会测度理论,分别建立了模糊随机期望值模型、机会约束规划模型及相关机会约束规划模型,然后设计遗传算法求解.     

坡度约束下曲面最短路径算法

给出了一种基于等高线求解坡度约束下曲面上两点间最短路径的搜索算法,自起点开始,路径方向始终尽量指向终点。通过已确定的增量变化高度,路径得以穿越各条等高线到达终点,最后给出了计算机求解的实例。     

有约束的随机最短路问题模型及算法

针对不确定网络,研究具有随机参数的最短路径问题,采用随机数表示路径权值的不确定性, 建立有约束的期望最短路模型. 基于随机模拟方法,设计了一种融合退火技术的遗传算法,引入退火机制处理有约束的优化问题.在进化过程中,动态调节对不可行解的惩罚力度,使不可行解逐步被淘汰出去, 最后收敛到问题的全局最优解. 给出的数值实例验证了该算法的有效性.     

随机时变特征下基于行程时间的路径选择算法

基于南京市实测数据分析了道路交通流实际随机、时变特征,证实现有行程时间最短路径算法相关研究中对道路交通流的随机、时变特征的假设与实际不符.以反例论证道路交通流实际随机、时变特征下,自适应算法(Adaptive Routing Policy)在求解行程时间最短路径方面的无效性.针对交通模式时段内道路交通流随机、时间无关的特征,以及路段行程过程中行程时间的确切概率分布难以知晓的实际情况,提出基于历史概率分布的历史期望行程时间最短k路径基础上的考虑风险衡量及当前道路实际交通流状况的路径选择算法.     

城市道路网络交通特性仿真模型及最短路径算法

就城市道路网系统宏观仿真中存在的问题进行研究，提出了更符合城市道路网系统实际特性的仿真模型，该模型对城市道路网交通特性空间分布的方向性差异及交叉口延误进行了抽象，并设计了基于该仿真模型的最短路算法。     

网络流量随机条件下的随机交通网络平衡分析

考虑到现实条件下交通网络的不确定性状态,提出了从确定型网络到不确定型网络状态下,出行者路径选择行为的改变,即由出行时间最短的路径选择行为转变为在追求一定行程时间可靠性的基础上选择出行时间最短的路径选择行为.考虑到网络上交通需求量的不确定性提出了最优可靠行程时间的概念.在此基础上将出行者追求最优可靠行程时间的路径选择行为纳入到随机交通网络平衡分配模型中,证明了模型的等价性和唯一性.最后在一个小型测试网络上对模型分配结果进行了测试,测试结果符合实际情况,表明模型能够较好地反映出行者的路径选择行为.     

随机时变路网环境下稳健路径选择及实证研究

交通拥挤、天气、突发事故等不确定性因素影响着城市区域之间的路网提供的 连通服务水平.本文对城市片区间道路连通路径选择进行研究.根据随机时变网络描述和 稳健路径选取原则,建立了最优化模型,并采用改进的Dijkstra 算法.通过深圳实例计算, 分析了出发时刻与最短路径行程时间和路段构成之间关系,并与确定性时变路网环境下 进行计算结果对比.结果表明,随机时变路网环境下鲁棒性最优算法选择稳健路径具有合 理性和可行性,可以很好地应用到区域动态连通情况的研究.     

动态车辆路径问题中的实时最短路径算法研究

分析了现有算法处理动态车辆路径问题时的缺陷,提出了一个动态网络环境下的实时路径评估模型,在此基础之上构造了一个改进的Dijkstra双桶算法.该算法能根据静态和动态的交通信息找出客户之间的实时最短路径,并对车辆的旅行线路进行调整,具有对随机事件和突发事件进行实时处理的能力,已用于解决动态车辆路径问题.实验结果表明,该算法能在动态网络环境下找到实时的最短路径,减少车辆旅行的总成本.     

面向城市交通网络的 K 最短路径集合算法

在城市交通网络中,为了优化交通流,需要搜索到符合出行需求 K 最短路径,并 将 OD（Origin-Destination）交通流合理分配到这些路径上.本文主要对搜索符合出行需 求的 K 最短路径搜索算法进行了研究,解决了已有算法仅能搜索出单条满足最短及 K 最 短条件路径的问题.根据 Wardrop 第二原则及路段阻抗函数理论,分析了路径集合搜索方 法对优化城市交通流的必要性,并定义了城市交通网络中 K 最短路径集合的概念及选择 条件,提出了一种面向城市交通网络的具有多项式时间复杂度的 K 最短路径集合搜索算 法.仿真结果表明,本文所提算法可以搜索出满足出行需求的所有 K 最短路径集合,在该 路径集合上进行交通流分配的效果明显优于传统方法.     

综合运输网络上多货类流量最短路分配

针对综合运输网络资源合理配置的需求,分析了综合运输网络上影响路径选择行为的用户偏好体系,并将其概括成客观类、主观类和调控类。在给出选择偏好在路径选择模型中的表达方法基础上,阐述了采用改进的最短路加载方法进行多货类运输流量分配的思路和执行流程,并面向可持续发展政策导向的运输网络规划,引入"诱导参数"对处于合理路径集中的联合运输路径进行优先选择。最后通过算例分析了不同"诱导参数"对双货类网络流量分布的影响,从政策调控的角度为综合运输网络宏观布局的评价模型提供理论参考。     

用于最短路算法的公交网络模型构建

公共交通线路网络的复杂化使乘客难于选择最优的出行线路。用于最短路算法的公交网络模型,解决了有向图难以承载票价和换乘这两个出行要素的问题,有效地把公交出行要素包含在弧中,使得最短路算法可以直接根据这些要素搜索最优出行方案。     

网络最短路径定界搜索算法

用Dijkstra算法求解大规模网络两顶点间最短路径时，需计算大量与最短路径无关的顶点，效率较低，双向定界搜索算法是首先对网络进行双向搜索，得到一条经任意点的最短路径，一般情况下，这条路径已非常接近、甚至等于最短路径。然后，以此路径的标号(即路径长)作为搜索计算的界，进行双向标号计算，对超过界的顶点不再计算，以提高计算效率．算法分析表明，用该算法可使计算效率提高约一倍。     

求网络中全部最短路的径路延伸算法

在分析已有最短路问题研究成果的基础上,提出了最小最短路网络的概念,给出了求网络上始点到所有顶点间全部最短路的径路延伸算法以及最小最短路网络、最小最短路树的算法.通过算例,验证了算法的可行性.算法简便,易于理解.     

交通路况感知下的自适应动态路径规划方法

针对传统路径规划算法在动态网络中的时效性和可用性不足,本文提出一种适用于时变 路网环境下的自适应动态路径规划方法。通过引入动态网络流式图划分思想,构建一种分层路 网的状态树索引,有效降低了动态路网中路径查找的计算代价,并扩展了传统路径规划算法在动 态路网中的普适性。在此基础上,将区域路况的时空变化信息融合到索引树中,进一步提出一种 基于时空层次网络的路径映射方法。并按照访问节点的距离逐步收缩最小包含区域来减少路径 查找视野,将路径查找过程转化为在层次图中的小范围寻址。为适应路网动态变化特征,路径映 射采用多路并行的双向探测策略,使得路径搜索迅速收敛于一个最优解,在动态路况变化和旅行 代价之间寻求平衡。最后,结合北京市实时交通路网数据集进行实验评估,在查询性能和自适应 调整方面验证了所提出方法的有效性。     

距离加权公交换乘复杂网络最短路算法研究

为研究乘客使用公共交通的实际出行距离,基于公交复杂网络中的换乘网络Space P拓扑结构,结合公交车站的经纬度坐标,建立以距离为边权的加权公交换乘网络。基于该加权网络,设计了综合考虑换乘次数和路径长度的最短路算法,该算法可保证在站间换乘次数最少的基础上通过的路径也相对最短。利用成都市公交网络进行实例分析,并与Floyd算法进行对比,结果显示,由该算法得到的平均最短路径长度增加3.7 km,但平均换乘次数下降0.64次,更符合乘客的出行习惯;随机选择一些车站进行最优换乘路径选取试验,结果表明,由该算法得到的方案在保证换乘次数最少基础上,得到的路径也基本最短,证明了算法的有效性。