多品种流交通网络的最大流算法研究

基于Ford-Fulkerson算法在单一品种网络中最大流量分配的思路,通过对多品种交通网络的网络特性进行分析,作者将多源多汇的交通网络构建成单源单汇的形式。在保证符合流量约束的条件下,设计了适用于多品种交通网络的最大流分配算法。在交通网络的实际应用领域里,多品种交通网络的问题普遍存在,因此该算法为解决实际交通网络的相关问题提供了基础。     

交通网络两个相邻结点之间有流量约束的最大流分配算法

交通网络最大流的分配是基于容量限制条件和流量守恒条件进行的,但在实际应用中,往往对交通网络中两个相邻结点之间的流量有具体的要求和约束限制。本文对交通网络中两个相邻结点之间的流量约束问题进行了分析,基于寻找增流链的算法,构造了带有上限或下限三种流量约束限制条件下的最大流分配算法,这些算法可以为解决实际的交通问题提供一定的应用基础．     

有运送路径限制的多品种流交通网络最小费用流算法研究

传统的交通网络最小费用流分配是针对单一品种,但在实际的交通运输应用中,交通网络中往往会出现多品种流的运送情况,而且也有可能对某些品种的运送路径进行限制.首先针对交通网络中的多品种流及其流动现象进行分析,借鉴Ford-Fulkerson算法中构造伴随增流网络的思路,建立了多品种流交通网络图的顺推重构方法,在此基础上,构造了有运送路径限制的多品种流交通网络最小费用流算法.在交通运输领域,多品种流最小费用流问题普遍存在,此算法为解决实际交通网络的相关问题提供了基础.     

有流量需求和分品种容量限制的运输网络最大流算法

基于Ford-Fulkerson算法求最大流的思路,对有流量需求的分品种容量限制的运输网络构造最大流算法,将有流量需求的转运节点分为转运节点和汇节点,同时构建单源单汇,寻找增流链进行流量调整。最后,通过示例对算法进行验证,计算出了满足流量需求和分品种容量限制的运输网络的最大流。     

交通运输网络中两个结点间有流量约束的最小费用最大流算法

对交通运输网络最小费用最大流的分配是在满足容量限制条件和流量守恒条件下,基于总费用最低的原则进行的,但在实际应用中,通常对交通运输网络中两个结点之间的流量有具体的要求和约束限制条件.针对交通运输网络中两个结点之间有流量约束的最小费用最大流问题进行了分析,总结了两个结点之间的流量不能超过限制值、不能低于限制值以及在一定范围内的3种约束条件.基于连续最短路算法中构造伴随增流网络的思路,设计了这3种约束限制条件下的最小费用最大流分配算法.利用这个算法,可以解决交通运输网络中两个结点之间有流量约束的最小费用最大流分配问题.在交通运输领域,两个结点之间有流量约束的最小费用最大流问题普遍存在,这些算法也为解决实际的运输问题提供了应用基础.     

运输网络转运结点有容量限制的最大流分配算法

对运输网络转运结点有容量限制的最大流分配一般是用结点一分为二的方法,但在大型、复杂的运输网络中,当有容量限制的结点很多时,这种方法将会使运输网络变得更加庞大,流量分配的过程变得更加繁琐。通过分析容量限制结点的特点,基于寻找增流链的算法,构造了基于大型、复杂运输网络中结点有容量限制的最大流分配算法。利用此算法,可以解决大型、复杂运输网络中容量限制的结点很多时的最大流分配问题,此算法也为解决实际的运输问题提供了应用基础。     

运输网络中有流量需求的转运结点最大流分配算法

运输网络中有流量需求的转运结点不遵从流量守恒条件,也不能按源、汇及中间结点归类．为解决这类转运结点的最大流分配问题,将这类转运结点分为汇结点和中间结点．根据Ford—Fulkerson算法寻找增流链的原理,提出了寻找这类转运结点增流链的方法、调整量计算公式和流量调整方法,形成了有流量需求的转运结点最大流分配算法．     

容量及转运点限制的多品种交通网最小代价流

传统的运送问题是在运送品种单一、运送条件理想情况下的最小代价流分配,但在实际的交通网络应用中,往往会出现多品种流的运送问题。同时,由于设备的限制,在同一个阶段的不同品种流的容量限制也可能不尽相同,不同品种在转运点的接发能力也不尽相同。本文主要考虑解决各品种的容量约束以及转运点的最大接发能力问题,分情况讨论复合指标修改规则,通过增流链调整规则修改复合参数,并根据汇的调整量修改复合指标,构造不需要改变网络拓扑结构的最小代价流算法。此算法不需要构造增流网络,也避免了二次求解问题。最后通过示例给出了具体的算法步骤,为以后在此基础上的优化研究提供基础。     

一种改进的求网络最小截集的算法

一个网络的最大流量,是由该网络最小截集的裁量决定的,网络的最小截集,就是该网络的瓶颈部位,网络最小截集中的弧,是该网络的瓶颈弧,而目前求解网络最小截集的Ford-Fulkerson算法,不能求出网络所有的最小截集,给实际应用带来一定的问题,文章提出了一种求网络所有最小截集的算法,算例表明,该算法的实际应用中是行之有效的。     

应用网络流模型解决航班衔接问题

针对单枢纽机场航线结构的特点，以所需飞机数最少为目标，提出了一种描述航班衔接问题的图论模型及优化算法。首先将航班衔接问题转化为航班节的衔接问题，并建立一个描述航班节衔接问题的二部图，将航班衔接问题转化为二部图的最大匹配问题，然后由二部图生成一个具有单源汇网络特征的辅助图，利用Ford-Fulkerson算法求该网络的最大流，进而得到二部图的最大匹配，从而得到了一个需用飞机数最少的航班节衔接方案，为利用计算机自动编制并优化航班衔接方案提供了一种可行方法。并且通过调整过站时间上限，可以得出不同的航班衔接方案，为制订生产计划提供了必要的灵活性。     

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

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

自行车-行人共享道条件下自行车交通流特性研究

研究城市路内自行车一行人共享道条件下的自行车交通流特性,对城市慢行交通规划、设计和管理有重要意义。论文首先设计了共享道交通流数据的采集方案,并选择南京市5条典型的自行车一行人共享道路段展开交通调研。其次,对共享道自行车交通流基本参数进行统计分析,包括交通流量、速度、密度及空间占有量等．再次,以实测数据为基础,分别建立共享道条件下自行车交通流基本模型,以及自行车交通流基本参数之间的相互关系曲线．最后,总结分析共享道条件下交通流与传统交通流特性的主要差异性。     

交通运输网络能力限制路段分析及扩能优化研究

交通运输网络是交通运输系统的重要组成部分,确定交通运输网络中的能力限制路段,设计合理的路网扩能优化方案都是交通运输部门需要面临的问题。本文依据最大流理论制订了路网能力限制路段的确定方法,建立了以换算扩能费用最小为目标的扩能优化模型并设计了相应的求解算法。算例表明,本文研究的模型及算法是有效的,且扩能优化方案中的扩能路段与路网能力限制路段基本上是一致的。     

最短路拍卖算法在交通流分配中的应用

拍卖算法是由Bertsekas教授提出的一种求解有向网络图最短路径的新算法,并已经发展成为求解线性网络流问题的综合算法.本文首先介绍了拍卖算法,分析了其特点,并将其与常用的标号设定算法和标号修正算法进行了对比.深入分析了交通路网的特点和交通分配中最短路求解的特性.研究结果表明,最短路拍卖算法特别适合于并行计算和大规模稀疏网络的求解,符合现实路网的特点和交通分配的要求.最短路拍卖算法应用于交通分配能避免大量不必要的计算,大大节省计算时间,在交通领域具有广阔的应用前景.     

静态多路径交通分配模型综述

静态交通分配反映路网交通流的拥挤性、路径选择的随机性等典型交通流特征,是交通规划方案评价和路网分析的重要方法.文章在介绍交通分配理论的基础上,对静态多路径交通分配的发展进行分析,并总结了静态多路径非平衡交通分配法的关键问题,分别对路阻函数及路权的计算、有效路径的定义、路网最短路算法、分配算法流程设计4个方面进行研究,总结静态交通非平衡分配法存在的不足,可为交通分配研究提供参考.     

基于交通量预测更新的爬坡车道设置研究

随着经济的快速发展，部分公路的交通量增长已超出设计时的预测值，对于其中的特定上坡路段，应以远景设计年限交通量预测更新值为基础，通过分析其通行能力从而判断是否需要设置爬坡车道。