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

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

多品种流中特定品种在结点上的流量有要求的最大流算法设计

本文首先分析多品种流交通网络的特性,在借鉴Ford-Fulkerson算法的基础上构造了求多品种问题最大流的基于多品种流的Ford-Fulkerson算法。然后分析了多品种流交通网络对特定品种在结点上的流量有要求的几种情况,并设计了这几种情况下交通网络求最大流的算法。在实际交通网络中多品种流问题普遍存在,对特定结点的品种的流量有要求的多品种问题更是不胜枚举,本文的算法为解决实际问题提供了应用基础。     

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

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

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

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

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

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

基于最小费用最大流算法的冲突车流分配

从最短路径角度研究交通分配问题,利用Dijkstra算法求解最短路径,根据道路容量和运行时间的限制,得出非冲突车流的优化路径,在此基础上假设冲突发生,采用设置优先通行规则与最小费用最大流算法相结合,实现有交通冲突情况下的交通流分配。     

一类点权网络的最小费用流问题

以城市路网为背景求最小费用流时不能忽略交叉口的费用和通行能力限制,但由于交叉口延误等费用和通行能力具有方向性,普通最小费用流算法无法直接应用于这类问题.文中以节点权重表示交叉口的延误和通行能力,将城市道路网表示为一个节点具有分方向权重的点权网络,提出了一个改进的最小费用路算法求解这类点权网络中的最小费用流问题.算法计算时间复杂性为O(nmf0).以一个数值算例说明了算法的应用.     

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

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

最小费用最大流算法在路径规划中的应用

针对一类动态路径规划问题，先利用最短路算法将其简化，把动态的路径规划问题转化为静态的路径规划问题，然后建立非线性规划模型，再利用最小费用最大流算法进行求解，得到了比较精确的结果，找到了一种解决传统算法一般难以求解复杂动态规划问题的方法。     

基于Petri网的网络最小费用最大流算法

将Petri网方法应用于求解网络的最小费用最大流问题,提出费用Petri网的定义,设计费用Petri网的变迁使能规则并提出求解最小费用最大流问题的Petri网算法.与以往的算法不同,该算法通过对库所进行标号寻找变迁的触发序列,并在该序列上增流.最后举例说明算法的应用.     

满足交通网络流量增长态势的扩能优化研究

在交通网络的实际应用中,流量的发展态势往往超出现存网络的最大流量承载能力,这就需要考虑如何提高网络的输送能力,即如何对交通网络进行扩能。本文基于发展态势的流量需求、扩能代价最低以及扩能拥堵程度高的线路条件,构造了最优的扩能算法。通过此算法,可以选择交通网络中最优的扩能路线。在交通运输领域,由于流量的发展态势需要扩能的问题普遍存在,本文的研究内容可以为交通网络的扩能决策、优化、设计等提供应用基础。     

���ڸ���ͼ���۵�·��������Ľ��㷨

在路网规划中,路网关键断面的确定对于解决路网中的交通瓶颈问题有很大的帮助。路网关键断面问题可以转变为寻找路网最大流最小割的问题。本文首先对现有求解网络最大流的各种算法进行了分析和比较。然后,基于图论中的辅助图理论和求解最大流中的Dijkstra算法,得到了一种求解无向路网中最小割集较为简便的算法,即通过构造辅助路网,利用求辅助路网最短路的方法得到最小割集,即原始路网的最大流。在此基础之上,利用VC++计算机语言程序实现了该算法。最后通过对天津市公路网的分析,进一步对本算法进行了说明。通过比较可知,这种方法是一种确定网络关键断面较为简便的算法,并且会对交通规划与管理提供重要的理论依据和数据支持。     

基于有限穿越可视图的进场航班流量波动特性研究

研究空中交通流量的波动特性是设计高效流量管理措施和控制策略的基础，掌握空中交通流量波动特性有利于空域资源配置与流量运行需求之间的均衡匹配。在3种时间粒度上，针对进场航班流量时间序列，一方面从复杂网络整体维度出发，采用有限穿越可视图对时间序列进行建网，利用k-core算法探究航班流量波动特性；另一方面从复杂网络局部维度出发，引入序模体方法，构造有限穿越可视图序模体，利用多元序模体类型转换规律来刻画流量的动态转移模式，进而掌握航班流量波动动态演化规律，为波动模式的预测提供了有效工具。研究结果表明：在有限穿越可视图方法映射得到的网络中，节点所属核阶数可以有效刻画流量波动强度，且与波动强度成正相关关系，即节点所属核阶数越大，波动强度越大，天津机场进场航班流量数据的强波动时 段为16:50-17:30；序模体越长，波动特性刻画能力越强，但鉴于受到空中交通混沌特性影响，序模体过长对于流量预测意义不大，推荐使用5节点序模体；波动模式状态转移图在有效刻画流量波动动态演化的同时，也可以计算波动模式的转移概率，3种时间粒度下转移概率分别为12.315%、 13.131%和10.638%，为波动模式的预测提供了有效工具。     

基于小波神经网络的路段短时交通流预测

应用BP神经网络来对路段短时交通流进行预测,预测精度和收敛速度都不是很理想,为了克服BP神经网络自身存在的非线性逼近缺陷,依据小波的时频域特征,将小波变换和BP神经网络结合起来,提出一种基于小波神经网络的短时交通流预测方法,给出了具体的网络学习算法,并结合实地调查数据进行了对比测试,分析结果证明了小波神经网络模型对短时交通流预测的有效性．     

大城市客运铁路枢纽客流分配模型

不同时段内,不同区位的旅客会根据不同的接驳方式及城际列车班次进行城际出 行.只根据城际间的出行成本无法准确地刻画旅客的出行.在已知不同时段内城市间各分区 OD客流、城际列车时刻表和铁路枢纽布局的前提下,构建城市内接驳交通网络;利用多项 Logit 模型,建立各个交通分区到铁路车站的接驳子模型;进而利用列车时刻表得到城际出行 成本,并考虑列车拥挤造成的成本增加,根据总成本最小原则及接驳子模型,构建分时段的铁 路枢纽客流分配模型.通过改进的MSA算法进行求解,得到各时段内各交通分区到铁路车站、 以及铁路车站之间的客流量.最后通过算例,对方法的可行性及有效性进行了验证.     

Improved Algorithm about the Maximum Flow in Road Network Using Auxiliary Graph Theory

In road network planning, locating the key sections will be very useful to solve the traffic bottleneck. Locating the key sections is equal to finding the maximum flow. To begin with, this paper analyzed and compared kinds of methods solving the network maximum flow problem. Second, this paper pointed out a convenient method based on the auxiliary graph theory and Dijkstra method. That is to say, the method could be used to get the minimum cutset and the maximum flow using the shortest path algorithm, and the VC++ program was also used. Finally, based on the road network of Tianjin, an example was given for further explanation. Through comparison, we know that it is a convenient method to locate the key sections and can support the transportation planning and management with theoretical basis and data.