多属性时间依赖网络的城市危险品运输路径优化

为了增加城市危险品运输路径的实用性,研究多属性条件下的城市危险品运输路径优化问题。用路段行驶时间、路段上发生运输事故的概率、交通损失、暴露人数和应急响应能力5个因素来描述路段属性。鉴于路段属性具有时间依赖性,将路段各属性定义为关于时间的离散变量,建立多属性条件下时间依赖网络的城市危险品路径优化模型。在模型求解中,通过节点所处时刻的分析以及基于信息熵的多属性决策方法,设计标号求解算法。计算结果表明:某路段属性的改变,会影响危险品运输路径的选择;当时间段不同时,得到的最优综合路径可能不相同。

随机时间依赖网络的K期望最短路径

首先给出了随机时间依赖网络模型、K期望最短路径问题的形式化描述 ,并针对公交网络推导出到达弧头结点的时刻所服从的概率密度函数、路径期望耗费的计算方法 ;然后 ,基于随机一致性假设和随机优势的概念给出了K期望最短路径问题的理论基础和算法并证明了算法的正确性 ;最后 。

多属性随机时间依赖网络路径优化

为了改善实时交通诱导,根据交通网络中路段属性具有随机时间依赖性的特点,将路段各属性定义为关于时间的离散随机变量,建立了多属性条件下随机时间依赖网络路径优化模型.基于信息熵的多属性决策方法,设计了模型的求解算法;优化了网络节点的搜索顺序,使每个节点的信息只通过一步更新就可得到,从而获得多属性条件下所有节点到给定终点的路径选择结果,出行者可以根据到达某节点的具体时刻选择行进方向.最后,通过算例给出了算法的实现过程,并说明了随机时间依赖网络不遵从"先进先出(FIFO)"条件.

基于预测信息的时间依赖网络路径规划算法

分析最小时间规划算法,针对算法在应用上存在的不足,在研究SPFA静态规划算法的基础上,结合该规划算法的优点,提出一种改进的最小时间路径规划算法。实例验证结果表明,该算法能够提供实时、高效、预测性强的规划路径,在城市交通中较好地满足用户的需求。

时间依赖网络路径模型及双层优化智能算法研究

时间依赖网络最短路径TDSP(Time-Dependent Shortest Path)是SP(Shortest Path)的衍生问题之一,与传统SP相比,TDSP在通信网络以及交通运输网络中更具有实际应用价值。在一些特定条件下,如FIFO网络或离散条件下非FIFO网络,TDSP可能存在实例多项式时间算法,而当边成本为一般函数时,已被证明不存在多项式时间算法。更具一般性,在不对边成本函数性质作限定的情况下,本文建立了时间依赖网络最短路径问题的优化模型,给出了求解此类模型的基于网络顶点优先权编码的双层优化智能算法。最后进行了算例分析。

时间依赖网络城市物流车辆调度的模型及算法

在城市配送中,车辆在不同时间段通过相同路径的行驶时间可能不同,时间依赖网络能更好地刻画城市物流车辆调度的实际特征,解决时间依赖条件下的城市物流车辆调度优化问题具有更强的实际应用意义。文在分析时间依赖网络车辆行驶时间的基础上,综合考虑顾客及物流公司两方面要求,以总配送时间、使用车辆数最小及客户满意度最大为目标,建立多目标时间依赖网络城市物流车辆调度模型;设计了遗传算法对该模型进行求解,并进行了算例研究,算例分析表明本模型在城市物流车辆调度方面是合理可行的,设计的算法是有效的。

时间依赖网络中国邮路问题

中国邮路问题是图论中的经典问题,得到了深入的研究和广泛应用。近年来,由于计算机网络与通信、智能交通系统等复杂应用领域的需求,时间依赖网络问题的研究具有更为重要的现实应用意义。本文首次提出了时间依赖网络中的中国邮路问题,建立了该问题的整数线性规划模型,并对该模型的上界进行了分析,最后给出了网络应用实例。

时间依赖网络中非FIFO弧的转化研究

经典最短路算法不能有效地解决时间依赖网络的最短路问题.时间依赖网络中的非FIFO弧的存在是导致经典的最短路算法失效的原因.本文对非FIFO弧的权函数为非连续(存在有限个非连续点)或者离散情况下转化为FIFO弧进行了研究,在允许等待的前提条件下,提出了解决此类问题的方法.建立在经典Dijkstra算法基础上,本文提出了时间依赖网络最短路算法.

时间依赖网络中有效交通路由的仿真平台

在理想的行驶条件下,经典的Dijkstra最短路径算法虽然可以计算出交通网络中两个任意节点的车辆行驶的最短路径,但这样做是没有实际意义的,因为在现实生活中交通流量会对最短路径的求解产生影响。本文介绍的时间依赖有效交通路由仿真平台,将每个节点的车流量信息转换成在该节点需要等待的时间,等待时间又可以看成某车辆以车速v走过的一段距离s。在原来Dijkstra最短路径算法的基础上,通过这样的等价变换,即可将现实生活中的交通流量考虑进去,从而求出任意两个节点的最优有效路径。

基于时间依赖网络的军事物流配送路径优化问题研究

科学技术的发展,网络信息化已经走进了寻常百姓家.而依赖于网络的军事物流在发展中却是逐渐发现自身的不足.而对于军队来说,军事物流是军队发展中最重要的环节,也是军队后勤的保障,优化军事物流配送路径,从实际情况着手,解决当前军事物流配送中的常见问题,对存在的重要问题逐级分解,满足军事物流在网络下的配送.

基于时间依赖网络的城市交通紧急疏散线路研究

研究时间依赖网络的城市紧急疏散交通线路问题。在对考虑疏散过程中交叉口延误和通行能力、紧急疏散网络防堵塞改造已有研究的基础上,对紧急疏散时城市交通网络的时变特性进行分析,提出了动态路阻交通紧急疏散线路的思想。考虑到紧急疏散时不一定满足FIFO要求的特性,将研究对象转化为时间依赖非FIFO网络交通紧急疏散线路的确定问题,建立了包括可变车辆行驶时间、交叉口延误和疏散等待时间在内的广义费用流最小化城市交通紧急疏散模型,采用最小费用流与时间依赖非FIFO网络最短路综合算法对模型进行优化求解,仿真试验结果证明了该思想方法的有效性。

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

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

时间依赖的混合型网络的分布式路由协议

提出了时间依赖的混合型网络模型(HTDN 模型),有效地描述了网络中链路权值随时间变化的特性,并且网络中的节点可以采用不同的等待策略;并给出了 HTDN 模型的路径优化理论。在此基础上设计了有效的分布式路由协议 DMDRP,能计算出 HTDN 模型中所有节点对之间的最短延时路径,并证明了协议的正确性。最后通过仿真试验,给出了 DMDRP 协议与传统路由方案的性能对比分析。

时间依赖的交通网络模型及最短路径算法

为了解决传统最短路径算法不能很好地应用于实时公交查询系统的问题,研究了时间依赖的交通网络模型和理论基础,提出了一种时间依赖的最短路径算法,以此算法为基础实现了南京市公交查询系统。实践证明,时间依赖的交通网络模型能更好地反映实际交通网络的运行情况。

基于时间依赖非先进先出网络的危险品运输路径选择

为合理选择危险品运输路径,降低危险品运输事故的发生概率,以危险品运输路径选择问题为研究对象,对运输网络的时变特性进行分析,提出了动态路阻运输路径的思想。考虑到危险品运输不一定满足时间依赖网络先进先出(FIFO)特性,因此建立了包括时间阻抗、费用阻抗和风险阻抗在内的综合阻抗最小的危险品运输路线模型,采用综合阻抗最小化与时间依赖非FIFO网络最短路径综合算法对模型优化求解。给出的算例表明,不同时间段内的最优路径会发生变化,验证了该模型方法的可行性。

顾及转向延误的时间依赖A~＊最短路径算法

建立基于路段的时间依赖网络模型,将转向延误时间引入到FIFO(先进先出)条件的定义中,并给出满足FIFO条件的路段到达时间和转向延误时间计算式。通过将时间因子引入到启发式评价函数中,发展了基于路段标号的时间依赖A*最短路径算法。试验表明,所提出的算法能预测并回避即将发生的交通拥堵,有效节省用户的出行时间。而其平均计算时间仅比传统算法增加10%左右。由于不再需要进行频繁的路径重优化,该算法能提高路径规划的整体效率。

时间依赖型同时取送货VRP及超启发式算法

为有效地协调正逆向物流,更好地体现城市物流配送速度时变的特点,降低物流配送成本,以时间依赖型同时取送货车辆路径问题为对象,建立其数学规划模型;设计了基于禁忌搜索的超启发式算法对其进行求解。在算法高层,设计了基于禁忌搜索评分制的选择策略及模拟退火的接收准则,实时监控底层启发式算子的性能并选择最优算子。通过基准实例测试及实验对比分析,表明了该算法能快速地找到满意解,所设计高层策略能保证算法跳出局部最优并快速收敛,从而证明了所提算法求解该问题的有效性。

动态容量网络中的最小最大时间流问题

动态(时间依赖的)容量网络与传统静态网络相比更具现实意义,在交通网络、物流网络和通信网络中都有着广泛的应用。在时间依赖网络最短路算法的基础上,研究具有实际背景的动态容量网络的最小最大时间流问题,给出求动态容量网络的最小最大时间流的多项式算法和算法的应用实例,其时间复杂度为O(mMv)。

最小时间路径算法的改进及在路径优化中的应用

由于城市交通网络中路径行程时间是随着时间的变化而变化的,求解最小时间路径比较困难,为此提出把交通网络抽象为时间依赖的网络模型的解决方法。对时间依赖网络模型和理论基础进行分析,指出文献[1]描述的最小时间路径算法存在的不足,即不能正确记录路径;通过引入一个记录路径的数组来对此算法进行改进,改进后的算法不仅解决了原算法存在的问题,而且可以满足n∶1的最短路径搜索,扩展了原算法的应用范围。最后用实验验证了改进算法的正确性和有效性。

一种求解交通网络中最短路径问题的人工蜂群算法

用人工蜂群算法解决寻找时间依赖网络中两点之间的最短路径问题,针对时间依赖网络中先入先出网络的特性,改进原算法中的路径选择策略,以优化生成的个体质量.该算法使用的策略为每个个体(即每条路径)添加一张散列表,用于记录搜索路径时遇到的路段,通过查找该表可发现当前个体的更优解.实验结果表明,该改进方法能有效提升算法最终解的质量,并极大缩短运行时间.