适用于无向网络的动态Dijkstra算法优化

网络拓扑发生变化时,利用静态Dijkstra算法重新计算最短路径树(SPT)会造成冗余计算;动态Dijkstra算法解决了这个问题,但目前动态算法一般是基于有向网络模型进行的研究;在已有的动态Dijkstra算法基础上,提出适用于无向网络的动态Dijkstra算法;算法主要解决了在无向网络中如何确定待更新节点的问题,对网络中的一条边权值增大、减小的处理方法进行了详细描述,并对已有的算法的筛选机制进行了优化;为了验证算法的正确性,用仿真实验实现了该算法并与静态算法进行性能比较;实验结果表明,新算法更能提高节点更新的时间效率。

一种基于Dijkstra算法的航空平台组网技术

针对航空平台在超低空和超视距飞行过程中,传统单一的TDMA网络难以满足无盲区通信需求,提出一种基于Dijkstra算法的Ad Hoc组网技术。通过建立实时邻居信息表、网络拓扑表和动态路由,在工程应用中实现了具有中继功能的地空-空空高速实时无线传输网络,满足了部队通信网络大范围覆盖和实时性需求。

景区应急疏散的动态路线规划算法研究

为实现旅游景区行人的安全疏散,提高行人疏散效率,文章以实际适用性和行人动态疏散为要点,提出一种基于Dijkstra算法,兼顾道路长度、宽度、坡度、实时人群密度等行人疏散效率影响因素的景区行人动态最短时间应急疏散路线规划(DSTEERP)算法。文章选取南宁市青秀山风景区和广西大学作为仿真区域,运用MATLAB软件进行人群疏散仿真和结果比对。结果表明:在实验设定下,DSTEERP算法与静态最短时间应急疏散路线规划(SSTEERP)算法和静态最短距离应急疏散路线规划(SSDEERP)算法相比,总疏散时间和人均疏散时间在青秀山风景区中缩短40%以上,在广西大学中缩短70%以上,验证了DSTEERP算法的可行性和有效性。

一种动态限制搜索区域的最短路径规划算法

提出一种动态限制搜索区域的最短路径规划算法,它是根据实际道路网络的空间分布特性,动态限制搜索区域,以降低算法的搜索规模,降低算法的时间复杂度和空间复杂度,提高算法的运行效率。实验证明,对于实际城市道路网络结构相对比较规则的最短路径规划,此算法极大地提高了规划的效率。

车辆导航系统的动态最优路径搜索方法研究

对车辆导航系统中线路引导信息的供给与需求进行了综合分析 ,提出了一种新的具有真实最短路径意义的实时动态最优路径 ,并设计了搜索该路径的改进 Dijkstra算法与改进 A* 算法 ,前者适用于多车导航 ,后者适用于单车导航。

面向驾驶员个性化需求的动态路径诱导方法

基于物理规划的思想,研究面向驾驶员个性化需求的动态路径诱导方法。首先,分析个性化动态路径诱导问题,构建路段交通阻抗的个性化评价指标体系;然后,基于物理规划思想,进行个性化动态路径诱导:面向驾驶员对道路的"可行性"需求动态确定交通路网搜索的几何空间;面向驾驶员对道路的"偏好性"需求,对几何空间内的交通路网阻抗进行个性化评价;面向驾驶员对道路的"最优性"需求,基于Dijkstra算法在动态交通路网中进行最优路径搜索;当路网中的交通阻抗发生变化时,及时更新路网信息,重新搜索从车辆当前位置到目的地的最优路径。研究结果表明:该方法既能体现驾驶员的个性化需求;仿真算例验证了该方法的有效性和可行性。

基于优化蚁群算法的动态路径规划问题研究

为解决传统的交通流分配模型在处理突发的交通事故、交通拥堵等实时交通信息时,无法对其作出合理及时的处理的问题。将动态交通网中实时变化的交通信息加入到路径规划模型当中,构建了基于优化蚁群算法的动态路径规划模型,通过与传统动态路径规划模型的比较,证明该模型收敛速度更快,且能有效避免局部收敛现象,实现了交通网络中车流量的合理分配,在大规模动态交通网络中表现更为明显。

基于行程时间多步预测的实时路径导航算法

针对现有车辆导航算法仅考虑单一数据,使所得路径实际行程时间比预期更长的问题,首先建立了基于卡尔曼滤波理论的行程时间多步预测模型;其次,提出了综合利用实时数据、行程时间多步预测数据及历史数据的实时路径导航算法,并改进了其实现的核心算法Dijkstra_pred。实验结果表明,基于三类数据的实时路径导航算法所得路径的实际行程时间从整体上优于仅采用实时数据的导航算法,且路径变化较少。

基于遗传算法的驾驶员动态路径诱导研究

动态路径诱导的目的在于向道路行驶者提供基于实时交通信息的合理、高效的行驶路线,以保证车辆在路网上运行的总费用最小。将遗传算法应用于动态路径诱导,通过引入任意迪杰斯特拉算法解决了遗传算法应用于最短路径的初始种群的选择、交叉和变异问题,提出了运用遗传算法求解动态网络中最短路径问题的新方法。最后,以西安市电子地图为基础,验证了遗传算法在动态路径诱导中的有效性。该研究为交通管理控制、驾驶员出行提供了更加准确和有效的路径诱导决策辅助信息。

动态路径诱导算法及其仿真

引入虚拟路径和拥堵因子,提出实时道路状况对路径规划算法权值影响的关系模型,在Dijkstra算法的基础上实现车辆的动态诱导,并以VB与MapX构建的GIS系统平台对该算法进行仿真,证明算法的有效性.

基于最短路径树的节点删除动态路由算法

提出一种基于最短路径树的节点删除动态路由算法。算法建立一个最短路径树更新集合,该集合包括被删除节点的断裂子树所有节点和其它节点连接的边,利用子树的结构信息,对子树节点的直系子孙节点和祖先节点进行更新,采用Dijkstra算法对其它子树节点进行更新。实验结果表明,该算法能有效减少节点更新计算次数。

动态路径诱导交通阻抗优化方法与实现

基于实时交通采集数据,获取合理动态规划最优路径,提出了考虑驾驶员出行行为因素的交通阻抗优化方法.研究了基于实时交通状态因素的动态路网优先等级指数的确定方法,重构了动态路径诱导交通网络模型,大大降低了路网的复杂度;基于多源实时数据,研究了动态路径诱导交通阻抗优化的计算方法,实现了路网的动态路径诱导,并通过GIS平台进行了仿真分析.该方法更符合驾驶员行为习惯,对于改进Dijkstra算法在动态路径诱导中的应用具有操作优势和显著意义.

可获知偶发拥堵持续时间的动态车辆路径问题

考虑真实交通路网,探讨了可获知偶发拥堵持续时间的动态车辆路径问题。在利用改进的Dijksta算法将路段行驶时间转化为客户点间最短行驶时间的基础上,根据常发拥堵信息,通过遗传算法安排车辆初始配送路径,根据实时获知的偶发拥堵因素影响下的路段行驶时间和其持续时间,以2-opt和insertion方法更新车辆配送路径,通过车载导航系统实时指导车辆行驶路线。数值试验表明,该方法可根据偶发拥堵信息更新车辆配送路线,以避开偶发拥堵影响路段,缩短总配送时间0.65~13.18min;获知偶发拥堵持续时间帮助多节省了配送时间-0.16~4.17min。节省的时间随偶发拥堵因素对路网影响的加剧而更显著。

时间窗约束下的AGV动态路径规划

针对自动化码头的多自动导引车系统(Automated Guided Vehicle,AGV)的路径规划问题,提出了一种基于时间窗的改进Dijkstra动态路径规划算法。算法按照任务优先级和地图中的先验信息顺序规划各AGV的行驶路径,在已规划路径的基础上,通过更新地图中的时间窗信息,继续规划后续路径,实现各AGV的无冲突且行驶时间最短的动态路径规划。结合实例及对比实验表明该算法能够有效减少多AGV之间的路径冲突,降低AGV的路径行驶时间,提高自动化码头运行效率。

基于实时交通信息的动态路径规划算法性能比较

本文综合考虑起始点间的所有路径的实时交通信息,将其作为影响选择概率的一个重要因素-阻抗,应用于蚁群算法当中,在此基础上进一步优化了传统的蚁群算法。通过与求解AR的两种方法-Dijkstra算法和蚁群算法的性能仿真对比。详细比较了与这两种算法在收敛速度和计算结果精确度方面的差异。结论表明改进后的蚁群算法在各方面均优于其他两种算法。

路径动态诱导策略研究

路径动态诱导中最优路径是一关键技术,文章通过对道路网特点的分析,提出了基于改进的Dijkstra算法、限制区域算法及数字地图技术下求解最优路径的策略。