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

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

基于多向堵塞的超点模型研究

在城市路网中,节点阻抗极大影响着路径选择及交通分配的结果.为弥补对节点转向阻抗研究的不足,优化路网流量分配,本文分析了已有节点结构模型,并在超点结构基础上,考虑节点转向的拥堵效应,完善对转向流量、阻抗等信息的记录,提出了转向堵塞后的路径选择方法,建立了基于多向堵塞的超点模型,并设计了求解算法.通过容量限制-增量加载的交通分配方法,演示了算例网络在考虑和不考虑节点转向阻抗下的流量分配过程,分析了网络中路径阻抗变化及路段、转向流量分布.结果表明：基于多向堵塞的超点模型可以有效地表达节点的转向阻抗变化,以及多向堵塞对于流量分配的影响,更符合实际中的交通分配.     

考虑转向延误的最短路径的节点标号算法

拥堵时段车辆在城市路网中交叉口处的延误甚至会大于其在路段的行驶时间,因而拥堵情况下在城市路网上应用不考虑转向延误的最短路径算法无法反映真实的交通状况.分析既有的考虑转向延误的最短路径算法,扩展网络法因过大的时间和空间开销而欠缺实用性,其余算法包括对偶网络法、节点标号算法和弧标号算法本质均为求包含节点权重和边权重的最短路径问题,最后求解均为节点标号算法.对典型节点标号算法Dijkstra算法进行改进,通过记录节点的紧前节点完成转向判别,并通过最小堆优化将该算法的时间复杂度从O(n2)优化为O(nlogn),并给出算法的数据结构,完成了软件编码,并通过计算实例对算法进行了验证.结果表明:考虑交叉口延误后城市路网最短路径发生变化,同时经过堆优化后算法的时间复杂度下降.     

���и��Ͻ�ͨ��������������о�

针对北京市三环内实际交通网络,分别构建城市道路交通网络和由城市轨道交通网络叠加形成的城市复合交通网络模型。基于复杂网络理论,采用Matlab计算节点度、聚类系数、平均路径长度、介数和节点紧密度等指标,分析了其分布规律,然后对这两个网络模型的统计特征值进行比较分析。结果表明,它们都具有一定的随机网络模型和无标度网络模型的小聚类系数特征,叠加后的城市交通网络直径和平均最短路径减小,平均度、聚类系数和节点紧密度都有不同程度增加,使整个路网的可达性得到了一定的提高,网络承载力变大。     

基于最短路径关键转向的交叉口应急交通管制优化

针对"点"对"点"式的救援交通组织问题,研究交叉口应急交通管制的优化方法.将事故点至救护点之间的时间最短路径作为规划救援路径,通过识别最短路径关键转向,并以保障关键转向畅通为主要出发点,对相关交叉口实行交通管制.为寻找救援路径上的关键转向,将道路网抽象为方向性点权网络,给出该类网络中最短路径关键转向的定义,并对Dijkstra算法进行改进,给出在该类网络中寻找最短路径及关键转向的有效算法.最后以一个实例说明了方法的应用.     

城市复合交通网络的若干特性研究

针对北京市三环内实际交通网络,分别构建城市道路交通网络和由城市轨道交通网络叠加形成的城市复合交通网络模型.基于复杂网络理论,采用Matlab 计算节点度、聚类系数、平均路径长度、介数和节点紧密度等指标,分析了其分布规律,然后对这两个网络模型的统计特征值进行比较分析.结果表明,它们都具有一定的随机网络模型和无标度网络模型的小聚类系数特征,叠加后的城市交通网络直径和平均最短路径减小,平均度、聚类系数和节点紧密度都有不同程度增加,使整个路网的可达性得到了一定的提高,网络承载力变大.     

基于转向的Logit交通分配算法

为避免交通分配中传统的网络扩展法在处理转向延误时的缺陷,通过分析网络基本要素节点、路段和转向之间的拓扑关系,借鉴Dial算法的基本框架,设计了一个基于转向的Logit交通分配算法。该算法以源点至路段的含转向延误的最短路径长度为依据处理各条路段,正向计算转向权重,反向分配路段流量和转向流量。算法计算结果与Logit路径流量和Dial算法数据相一致,该算法可直接求解既满足Logit路径选择概率又考虑转向延误对交通分配影响的路段流量和转向流量模式,而且Dial算法是其在转向延误为零时的一个特例。     

传播动力学视角下集装箱海运网络关键港口节点识别

将船期延误与重要港口节点的识别问题相结合，通过传播动力学模型，对世界集装箱海运 网络的传播特性进行分析，发现港口节点传播能力与度值满足幂为16.84的幂律分布，具有无标 度特征，且度值与传播影响力的相关性较强。以 SIS(Susceptible-Infected-Susceptible)模型为基 础，结合网络结构特性，比较不同节点传播影响力评估方法发现，节点间最短路径长度是衡量节 点传播能力的一个重要因素。基于引力模型，提出考虑度值、节点核心位置及节点间最短路径长 度的综合取值法，验证了改进引力模型在世界集装箱海运网络节点传播能力评估中的适用性，发 现综合取值法对模型精确度提高有促进作用。研究得到：世界各港口传播影响力排序，为关键港 口的识别提供了不同视角；高传播影响力港口普遍集中在亚洲区域，其次为欧洲地区；高连通性 与高传播影响力无正相关性。     

基于变权的多目标物流网络货流分配方法

为克服多目标物流网络货流分配问题中加权求和求解方法的主观片面性,在具有固定拓扑结构的物流网络的基础上,建立了以运输线路和物流节点能力为约束条件、以物流成本最小、最长单程运送时间最短以及网络使用率最高为优化目标的多目标物流网络货流分配优化模型,并提出了基于变权的模型求解方法:首先,构建了物流网络变权模型,通过状态变权函数实现变权操作,使变权结果不仅反映了决策者的主观偏好,而且与客观的目标状态值相关联;其次,根据物流网络变权模型计算基于优化目标变权综合的路径状态值,并进行最优路径选择和货流分配;最后,通过算例对优化模型及求解方法进行了验证.      

结合概率搜索定界的入度统计最短路径算法

Dijkstra 经典最短路径算法包括大量的排序运算,且需要对图中所有顶点进行计算,效率较低.本文针对有向网络,提出了与概率搜索定界结合的入度统计最短路径算法.该算法通过按概率搜索得到一条较短路径,依据路径长度和有向网络结构特征确定和顶点序号相关的节点阻抗最大值;采用入度统计算法代替经典的标号算法,在计算过程中根据节点阻抗最大值,采取一定方式剔除无效顶点(不在最短路径内的顶点),简化网络结构.本文提出的算法不需要进行排序运算,简化了运算过程,并且可以剔除大量的无效顶点,降低了网络复杂度.算例分析表明,相对于Dijkstra算法,结合概率搜索定界的入度统计算法大幅度提高了运算效率,具有实用性.     

考虑速度与拥堵的多式联运路径优化研究

对多式联运路径优化进行了研究.对于多个城市节点,扩展并建立不规则棱柱模型网络,不仅考虑不同运输方式的成本与时间,还将不同运输方式对应的速度与拥堵纳入模型.基于Dijkstra最短路径算法,创建一个包含速度与拥堵因素多式联运路径优化模型仿真系统,通过模拟动态参数,分析了该组参数下的速度与拥堵对多式联运最优路径选择的影响,为区域运输规划提供了重要的参考价值.     

基于改进BA模型的海运复杂网络演化研究

以复杂网络理论为基础,分析海运网络的拓扑结构具有无标度特性.据此,针对港口节点进行研究,分析节点连接概率的影响因素,通过加权量化和MATLAB编程得到节点吸引度,进而改进了BA网络模型中的节点连接概率.选取2007和2010年全球15个主要港口的相关数据,运用上述改进模型分别得到2 a的海运网络演化情况,验证了海运网络具有小世界和无标度网络特征,并得出2010年海运演化网络平均路径更短、集聚性更强,度值相差更悬殊,网络连接更加频繁与高效.     

中心式诱导路径优化计算方法

基于并行计算技术和网络数据存储方法, 考虑了出行者的偏好, 分析了多级网络分解方法和双端队列最短路径计算方法, 提出了一种新的中心式诱导路径优化计算方法。以长沙市和长春市城市路网的实际数据为基础, 在普通PC机群、联想服务器机群及惠普工作站机群3种不同计算性能的并行计算平台上进行试验测试。测试结果表明: 使用网络数据存储方法, 能够直接确定邻接节点与相应弧的存储位置, 节点信息的查询时间明显减小; 使用多级网络分解方法, 主要路段作为被切割弧的概率降低, 最短路径计算过程中处理器的通信量减小; 使用双端队列最短路径计算方法, 最短路径计算速度明显提升; 使用新的计算方法, 长沙市路网中400万条最短路径计算时间为46s, 长春市路网中1 170万条最短路径计算时间为72s, 完全能够满足中心式诱导路径优化时间小于5min的要求。     

城市道路交通网中最短路径搜索算法设计及其实现

交通网络中最短路径的搜索是地理信息科学与计算机科学等领域的研究热点。本文以石家庄市中心区域部分道路网为实践对象,结合道路网络的特点,在自定义节点一链拓扑结构表达路网的基础上,提出了一种适于最短路径算法的空间数据组织方式,运用迪杰斯特拉(Dijkstra)最短路径算法,以MapInfo的二次开发语言MapBasic为开发工具,在电子地图环境下实现了道路网络中任意两节点间最短路径的快速解算与刷新显示。     

公路旅客最少换乘次数乘车方案选择算法

对公路旅客最少换乘次数乘车方案选择算法进行了研究,建立了描述公路客运换乘网络的有向无权图模型,将两站之间最少换乘次数乘车方案选择问题,转换为在权图中搜索两顶点间的最短路径问题,同时给出求解换乘网络中单一最短路径的基本广度优先搜索算法和求解全部最短路径的改进广度优先搜索算法,并通过算例验证算法的正确性.最后对算法的执行效率进行了分析.     

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

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

基于GA的动态时延受限多播路由算法

探讨了包交换计算机网络中，具有端到端时延限制的动态多播路由问题．提出了一种基于遗传算法(GA)的动态时延受限多播路由优化算法．当节点加入或退出时，算法先利用Dijkstra第k最短路径算法求出节点到源点的最短路径集，再用遗传算法搜索最小多播树，仿真试验表明该算法可以动态求得满足时延约束的最小多播树．     

基于点线能力约束的多层级节点协同布局优化模型及算法研究

多层级物流节点布局对物流系统的降本增效具有重要作用. 提出物流网络简化处理策略,结合实际物理网络结构,以最短路径、共同弧段及通道运能三要素为重点构建了多层级物流节点的网络拓扑;在此基础上,结合不同层级物流节点的最大服务半径、服务能力及成本等属性,系统性考虑节点及通道运能,构建基于点线能力约束的多层级节点协同布局优化模型;结合模型决策变量特点,利用改进的和声搜索算法进行求解. 采用实际案例进行测试和应用,进行相应情景分析. 结果表明,模型及算法具有良好的适应性,为实际多层级物流节点选址提供一定决策依据.     

基于复杂网络的城市路网结构分析方法

在城市道路网络的基础上, 探讨了应用复杂网络理论的可行性和有效性。运用Dijkstra最短路径算法和Space L方法建立初始拓扑网络, 并建立了节点度、边度和节点路阻的特性指标模型。在反映路网功能真实性的前提下, 优化了拓扑网络, 并以某市中心城区道路交通数据为例进行实例分析。分析结果表明: 在初始网络中, 节点度数的均值为2.850 0, 标准差为0.670 8;节点路阻的平均值为84.680 0 s, 标准差为11.768 8 s;在优化网络中, 节点度数的均值为38.750 0, 标准差为24.683 0, 节点路阻的平均值为91.780 0 s, 标准差为18.862 8 s;东西向边的平均度数为42.00, 南北向边的平均度数为29.86, 内部边的平均度数为55.00, 外部边的平均度数为28.33。在优化网络中, 当度数较大的节点在路网中失稳时, 在非拥挤状态下, 最短路径路阻增大, 而在拥挤状态下, 网络会瘫痪。度数较大的节点与真实路网中交叉口重要程度相符, 能够体现交叉口重要程度的差异性。     

一种寻求多条最短路的新算法——生长路径法

为了寻找栅格状轨道交通运输网络中任意两个节点间的全部最短路径,根据数据结构中堆栈数据“后进先出”的原理,提出了生长路径法,它将从起点发出的初台最短路径压入堆栈,并利用边的编号和路径长度对堆栈内的路径进行生长和判断,合格的路径进栈,不合格的路径剔除,直到堆栈内所有的路径都生长至终点为止,利用这种算法可求出无负向边的有向网络中任意两节点间所有的最短路径。