时间依赖的网络中最小时间路径算法

时间依赖的网络与传统网络模型相比更具有现实意义 ,具有广泛的应用领域 .交通网络和通信网络可以抽象为时间依赖的网络模型 .当模型中弧的长度是时间依赖的变量 ,最短路径问题的求解变得非常困难 ,早期的研究者通过具体的网络实例认识到传统最短路径算法在这种情况下是不正确的 ,因此给出限制性条件使得传统最短路径算法是有效的 .该文从最短路径算法的理论基础入手 ,从理论上证明了传统最短路径算法 ,如 Dijkstra算法和标号设置算法 ,在时间依赖的网络上不能有效地求解最短路径问题 ;并且 ,在没有任何限制性条件下 ,给出了时间依赖的网络模型、理论基础、求解最小时间路径的优化条件和 SPTDN算法 ,从理论上证明了 SPTDN算法的正确性 .算法的实验结果是正确的 .

最小时间路径算法模糊结构元改进

针对运输的最小时间路径问题,采用模糊数表示车辆在各路段的运行时间,建立模糊最小时间路径模型.该模型不仅得到两节点间的最小模糊时间值,而且得到最小时间路径;利用模糊结构元处理模糊数的运算,简化了模型的运算.实例表明:该模型有效地解决了交通网络中任意两节点间的最小时间路径问题.

时间依赖有向无环网最小时间路径算法

经典模型及算法可解决固定弧权条件下的最短路问题,然而实际应用中弧权往往是动态的,即弧权依赖时间变化。本文提出一种特殊最短路径算法,即在有向无环网络中最小时间路径算法的一种实现。该算法是一种改进的扩散法,克服了扩散法的一些显著缺点。文中证明了该理论的正确性,最后列举了一个传统算法不能解决的实例,证明了该算法的正确性。

机器人最短路径最小时间路径分析

本文研究了机器人在避开障碍物的前提下行进的最短路径及行进的最小时间路径问题;机器人在可行域内有可能改变行进路线的所有点,构成了一个赋权网络图,所以机器人从出发点到终点的最短路径问题就转化为在网络图中找一条从起点到终点的最短路;通过引入0-1变量,来选择避障物的转弯点,建立最小时间路径优化模型;采用搜索的方法,借助matlab语言编程找出最小时间路径。

基于时间依赖的物联网络模型的路径规划

本文针对基于物联网的物流网络中路径代价的时变性,建立一种时间依赖的物联网络模型,并在此基础上研究物流路径规划问题。针对现实中预测准确性随时间推移而降低,以及在预知程度较低时无法获得较好的路径规划等问题,提出一种带弧代价预知程度参数的最小时间路径算法SW PL以及基于SW PL的逐步规划解决方案。该算法考虑了预测的精度问题,在传统Dijkstra算法的基础上引入一种与时间相关的弧代价计算方法。实验表明,在预知程度较高和在预知程度较低但采用逐步规划的解决方案2种情况下,都能取得良好的路径规划效果。

无线传感器网络中基于线性聚合的启发式穿越算法

当智能目标穿越敌方无线传感器网络的穿行时间受限时,现有基于广度优先搜索的穿越算法不能保证路径满足约束条件.为此,建立了一种穿越模型,并提出一种启发式的近似数值优化算法:k-shortest path-线性聚合启发式穿越路径算法(kSP-LAHTP).算法利用Voronoi图将连续路径问题域离散化,以曝露度和穿行时间为衡量指标,结合线性聚合的启发式路由机制,使目标实现满足时间约束值的最佳穿越.分析和实验结果表明:算法很好地解决了目标穿越时间受限情况下的穿越问题;且随系数k的增加,算法搜索路径更接近实际最佳.

一种基于改进冲突搜索的多机器人路径规划算法

针对智能仓储环境下多载位自主移动机器人集群拣选-配送路径规划问题,提出一种改进型基于冲突搜索的多智能体路径规划算法.在模型方面,采用多载位机器人替代KIVA机器人,建立以最小化拣选-配送时间以及无效路径比为目标的数学规划模型.在算法方面,首先,提出一种基于优先级规则的多智能体冲突消解加速策略;然后,设计基于动态规划的单机器人拣选序列优化算法;最后,设计考虑转向惩罚的增强A^(*)算法搜索机器人最优路径.实验结果表明:所提出模型与KIVA系统相比有较大优越性;所提出算法能够有效缩短拣选-配送时间、减少无效路径时间.

城市道路网络交通效率计算方法研究

提出了一种基于OD对,综合考虑道路通行能力、自由流车速、流量、运行车速、出行时间等计算城市道路网络交通效率的方法,可用于评估城市道路网络的实时运行效率,也适用于路网中单个路段及部分路网交通效率的评估;并将该方法与其他交通网络效率算法如L-M算法及N-Q算法进行了比较;通过实例仿真,介绍了该方法在路网效率与OD需求关系分析中的应用。

关于动态最短路问题的探讨

主要研究网络优化领域中一种具有动态特征的最短路问题,给出了离散时间模型下关于时间和费用的动态最短路问题的描述,通过引入时间扩张图概念,将动态最短路问题转化为对应的静态网络中的最短路问题,讨论了两类动态最短路问题的复杂性并给出算法。