城市轨道交通有效路径选择的改进Dial算法

结合城市轨道交通的基本特性,从网络节点的角度出发重新定义了有效路径以及换乘站点,并结合网络拓扑排序方法,在Dial算法的基础上提出了改进的Dial算法。最后,采用深圳市轨道交通网络的基础数据进行了实例分析,结果显示改进的Dial算法的可行性,并且计算效果优于原算法。     

基于广义成本的轨道交通最优路径模型研究

针对轨道交通换乘的多目标路径优化问题,采用两级分层的层次模型描述轨道交通网络,并结合乘客出行时考虑的因素,以成本最少和时间最短为优化目标;通过行为时间价值原理将成本和时间转化为广义成本,建立了基于广义成本的轨道交通换乘最优路径模型。利用轨道交通网络封闭性好的特点,采用了Dijkstra算法对其进行路径优化。最后通过Matlab对模型和算法进行实例仿真,实现了多目标下轨道交通换乘路径的最优化,验证了模型和算法的可行性和收敛性。     

基于交通流量预测的动态最优路径规划研究

针对传统算法仅适用静态路况的缺点,提出基于交通流量预测的动态最优路径规划方法.通过建立道路运营网络模型,计算流量碰撞概率和道路拥堵概率,重新定义路段的权值并改进了传统算法,实现了动态路况下的最优路径规划,并对传统算法与改进算法进行仿真实验,得到3种实验结果.结果表明,改进算法在交通高峰期得到的最优路径所需行驶时间比传统算法得到的最优路径行驶时间减少16%～23%,有效提高了交通调度效率.     

基于图论的边缘计算信任评估优化模型

针对边缘计算中资源受限等特性导致现有信任模型出现计算负载、路径冗余的问题,提出了一种基于图论方法并适用于边缘计算环境的信任评估优化模型。该模型将设备间复杂庞大的信任关系抽象成有向加权图再对其进行优化处理。首先,定义了设备间的信任关系,并采用基于信息熵理论的自适应聚合方法对信任值进行聚合计算,修正了信任值之间的差异度;其次,通过添加阈值、路径长度、时间窗等多重约束条件,事先过滤掉明显不符合要求的节点和信任边,降低信任路径形成过程中不必要的计算消耗;在此基础上,利用改进后的深度优先搜索(DFS)算法对信任路径进行冗余优化处理,避免了环路以及节点绕路问题,得到优化后的信任路径集合并计算得到最终信任值。最后,将所提方法与PSM算法以及RFSN算法进行了对比实验,结果表明本文算法能够有效减轻边缘设备的资源开销,并提升了信任模型的有效性。     

XML数据公交信息查询优化算法及实现

针对公交线路规划的问题,必须提供一个准确快捷的公交查询系统以满足人们日常出行的需求.研究了基于XML数据的公交查询系统,该系统采用B/S模式,利用ASP.NET框架和C#语言,实现了公交运行查询功能.在换乘查询算法部分及在Dijkstra算法的基础上,分析了路径寻优的原理,实现了路径距离计算的具体方法.并通过减少临时节点排序及数量的方式,改进了Dijkstra算法,最终减少了寻找路径的时间并简化了路径计算.最后,以天津市公交数据为例,用改进的Dijkstra算法对公交查询系统进行了分析验证,结果表明,利用改进的Dijkstra算法可以实现高效的公交信息查询,节约查询时间,节省内存资源.     

用于动态交通分配的合理路径集合算法研究

为了解决在基于路径的动态交通分配问题中,在每一个起点与终点之间的合理路径集合产生问题.首先,介绍了目前常用的路径集合产生方法,如Dial算法、路段删除算法、路段惩罚算法以及仿真方法等,然后在此基础上提出了可用于动态交通分配问题的合理路径集合产生以及路径合理性判断指标.在一个中型路网中,通过仿真方法确定了本文提出的算法的有效性和正确性,结果表明:以Dial算法、路段删除算法和路段惩罚算法为基础的算法给出的结果更加有效,而仿真算法给出的路径集合偏差较大.     

一种基于OBDD的WSN可靠性评估方法

为评估组播下WSN可靠性,基于有序二叉决策图(OBDD)提出符号OBDD_Multicast算法。该算法在WSN符号OBDD表示的基础上,对WSN的节点变量进行排序,通过节点扩展,利用OBDD的"与"和"或"操作构建组播下WSN可靠性函数的OBDD。OBDD_Multicast算法通过识别相邻节点冗余路径和s-t非连通冗余路径,避免冗余扩展,减少扩展过程中中间子网的数目,有效降低了可靠性分析的复杂性。实验结果表明,针对3×N型网络,OBDD_Multicast算法比Shrestha的OBDD算法耗时少、效率高。     

计算最短路径树Dijkstra算法的改进

针对用于网络寻径表刷新的OSPF路由选择协议中使用的计算最短路径树的Dijkstra算法在网络应用中的不足，提出了一种改进算法，用以计算边和节点上都有代价的图的最短路径树，以更全面刻画网络状态，找到更合理的最短路径树，通过对同一个网络自治系统最短路径树的计算，比较了改进Dijkstra算法和Dijkstra算法的差别，结果表明改进Dijkstra算法能够更加全面地刻画网络状态，找出的最短路径树更为合理。     

移动自组网中基于位置信息的路径优化路由算法

针对移动自组织网络中基于位置信息的路由算法在空洞存在时仅能生成非优化路径的问题,提出了利用空洞广播来构造优化路径的算法.在利用空洞检测技术收集网络中空洞的边界节点集信息后,将空洞信息进行广播.为减小网络开销,仅将边界节点集的凸包进行广播,并将广播限制在计算出的广播域内.当传输数据包到达广播区域内后,节点匹配目标位置与空洞边界节点集凸包的关系,并以此构造出通过空洞的优化路径.仿真结果表明该算法在存在空洞网络中通过构造优化路径,相对于GOAFR+算法最多降低25ms的传输时延.最后,对该算法在实际应用中的适用条件进行了分析.该算法适用于网络拓扑变化率较低,数据传输率较高的网络.     

A~＊路径规划算法的改进及实现

针对A＊算法在路径规划过程中因遍历节点多而导致搜索时间长和路径规划距离长的问题,对A＊算法进行了改进.改进算法采用两点间的欧氏距离作为估价函数,并以前向搜索和后向搜索交替进行的方式来减少路径规划时间.仿真结果表明,改进算法在搜索时间和距离上分别比A＊算法减少了0.0184s和42m,在搜索得到的路径长度和算法运行时间上明显优于A＊算法.     

配合大容量快速运输的实用常规公交线网规划方法

基于轨道交通和快速公交网络确定的前提下,在"逐条布设、优化成网"的规划方法基础上,提出大城市常规公共交通线网的规划方法.引入枢纽点吸引系数概念,用于调整与大容量快速运输线路站点及枢纽相邻区域的公交线路运行时间,按最短路算法确定备选公交线路集,以直达客流密度最大为目标确定公交线路走向,使常规公交线路在布设时优先通过或邻近换乘枢纽点,从而达到提高大容量快速运输系统吸引力、有效驳运轨道交通和快速公交客流,同时兼顾公交运营企业效益的目的.     

基于电网监测的无线传感器网络短路径路由算法

综合考虑距离、剩余能量、转发包数等因素,提出一种基于电网监测的无线传感器网络短路径路由算法(SPRA-PNM).SPRA-PNM算法通过短路径场的建立来预留多条较短距离路径,并在实际数据转发时选择剩余能量最大的节点转发,从而提高了传输可靠性和网络生命周期.实验仿真对路由转发数据消息时网络内的冗余消息包数量和网络的平均生存周期2种指标进行了性能评估.     

城市轨道交通枢纽换乘供需一致性研究

基于分形理论,提出了代表轨道交通线网中枢纽供给能力的站点-半径维数、代表枢纽换乘需求的换乘需求-半径维数,通过分析分形维数的一致性达到量化枢纽供需一致性的目的.最后以北京市轨道交通线网为算例,验证了模型和算法的有效性,并对算法中涉及的重要参数进行了灵敏度分析,讨论了出行行为对于分形维数和一致性指数产生的影响.结果表明:分形维数及分形一致性指数能较好地描述轨道交通线网的供需一致性特征.     

高铁复杂网络拓扑特征及节点中心性研究

以我国主要代表性城市为研究对象, 分析高速铁路网络特性与拓扑特征, 识别高铁网络中的节点城市及其功能作用。运用Space-P方法构建高铁网络模型, 利用复杂网络理论及Pajek分析软件, 从度值、平均路径长度、聚集系数及节点城市中心性等方面研究我国高铁网络的拓扑结构及节点中心性, 结果表明: 我国高铁网络整体聚集性较高、连通性较强, 东中部及沿海城市表现出高聚集性, 西部城市高铁网络连通性低, 聚集性较弱; 高铁网络具有小世界特征, 任意两节点之间通过较少的中转次数即可连通, 少数城市间需中转三次才能连通; 在高铁网络中, 度值较大的城市主要集中在我国东中部及沿海地区, 西部及东北地区城市度值较小且度中心性较大, 其接近中心性也较大; 而度值较小且介数中心性较大的城市具有较强的中转能力。     

综合运输体系下的货运网络能力计算

对综合货运网络进行了相应的变换,通过网络变换将交通方式间的中转约束转化为路段的能力约束。计算各个OD对的前K条短路作为该OD对的可选路径集合。考虑OD需求是否拆分以及货物中转能力对综合货运网络能力的影响,建立了综合货运网络能力计算模型,并给出了求解思路以及相对应的免疫克隆算法。最后,选用一个算例对上述模型以及算法进行了分析验证。算例测试表明,该模型以及算法具有较好的实用性。     

基于轨道交通的常规公交线网优化模型研究

在常规公交支持轨道交通的发展模式下,运用主轨道有效影响因子对研究区域进行梯度分级;提出了基于路段客流、广义票价费用、服务时间及环境费用的四维有效因子,并构建基于供需平衡与乘客出行有效费用的双层优化模型,利用考虑约束条件遗传算法对上层模型进行求解,并用该模型及其算法对基于地铁1、2号线的成都市公交线网进行优化.结果表明:...     

弹性需求下的轨道交通客流分配模型和算法

分析了轨道交通客流需求量的影响因素,以拥挤条件下的出行阻抗函数为基础,通过引入弹性需求条件下的轨道交通均衡配流条件,构建了弹性需求下的均衡配流模型．根据模型的特点,给出了改进的用于求解弹性需求下的轨道交通均衡配流模型的Frank-wolfe算法,最后通过一个算例说明了算法的有效性和合理性。     

可解决最优路径中含P型和U型等圈路指向的Floyd算法

城市交通中设置左转禁止限制,往往会导致含有特殊圈路的情况,经典迭代算法均不能指出含有圈的最优路径指向,而且都需要预先对网络进行复杂的拓扑转换或者数据结构处理。针对这一问题,本文提出了可解决最优路径中含P型和U型等圈路指向的Floyd算法,只要在Floyd算法中引入正、反向路径指针,构造出随Floyd算法同步迭代的禁行路线判断规则,由此形成的算法能够自动指出最优路径中含有圈时的路径走向。使用该算法,无须改变原有网络的拓扑结构,不但使用方便,而且计算效率高。     

双向搜索多约束路由启发式计算方法

为提高大型通信网络中搜索满足多约束条件路由的速度,提出一种双向搜索路由的计算方法.首先从源和目的节点同时出发,计算到达各中间节点的可达路径.然后在各可达路径中进行路径的筛选.可达路径是采用邻接矩阵变换方式获得的,筛选路径是根据非线性开销函数,采用启发方式择优选取.当两方向搜索的节点数累计达到n-2后,对接合并两方向到达中间节点的路径,从中再选择最佳路径作为路由输出.通过算例详细介绍了可达路径计算及启发式选优方法.阐述了算法的正确性及特点,分析了最大时间杂性.通过仿真实验评估,不仅更进一步验证了新算法的正确性,而且表明新算法在搜索路由速度上要优于其他算法.