基于改进网络最大流的道路通行能力优化研究

廖 晔，王顺意

(1.永州职业技术学院 建筑工程系，湖南 永州 422500；2.西南交通大学 土木工程学院，四川 成都 610031)

近年来，随着城市化进程的不断加快，城市路网结构愈趋复杂，对城市路网结构的定量研究及优化改造具有重要意义[1]，与此同时，网络最大流理论被广泛应用于军事运输、物资调度路径优化等诸多行业领域[2-4]。

当前，国内外学者基于网络最大流理论展开了一定的研究，部分学者建立了相关优化模型。卜祥涛[5]从网络拓扑结构和网络最大流、网络巧扑结构和网络交通流相结合2个角度，提出路网新增路段对交通网络性能影响的度量指标。郭波等[6]以两源单汇网络为例，在资源到达终点所需时间最短约束下，研究、计算最短传输时间的上下界。詹雯[7]基于改进标号算法建立网络增广链的最优路径选择模型。高明霞等[8]通过寻找网络最大流增流关键边、次关键边等，确定路网中实行逆向车道管理的备选路段。李运等[9]结合设置优先通行规则与最小费用最大流算法，实现有交通冲突情况下的交通流分配。

另有部分学者设计了新的计算方法。栗雪娟[10]系统分析和研究图论中求解路网最大流的各种算法、适用条件和优缺点。李玉兰等[11]借助图论中最大流最小割定理，给出了路网容量的计算方法。杨晓萍等[12]以网络极大流为基础，建立了理性条件下城市道路网容量的计算模型。孙同江等[13]采用Petri网论法和计算机图形仿真法相结合的方法求解了运输网络最大流。苏镇洪等[14]采用图论的多端最大流算法和衍生割集算法，研究了道路网络容量的计算方法。何家莉等[15]建立了道路最大平均流量的计算方法，并采用小生境混合遗传算法进行了求解。胡适军等[16]针对网络流割树法的局限性，结合船舶流特点，给出了水网航道交通容量的计算方法。李冬梅等[17]探讨了道路路段的通行能力和交叉口的通行能力的计算方法。罗文等[18]针对多约束变容量条件下的应急物资调度问题，构建了基于几何代数的条件约束最大流分析模型；

上述研究成果针对路网容量、路径优化进行了初步研究，但是鲜少全面考虑道路通行能力及其优化改造。本文建立了一种改进的网络最大流模型。首先，基于最基本的网络最大流模型计算道路最大通行能力；然后，考虑通行的道路选择性，建立最短路模型，计算各个单源到各个单汇的最短路径并通过A*算法筛选出有效路径；进而，利用最短路模型结果加强原模型中的约束条件，利用单纯形法求解实际最大通行能力；最后，建立以道路扩宽成本最低为目标函数的线性规划模型对道路进行改造。

1 问题背景

某校园占地约3000亩，按照“一轴二带三环六区”的规划骨架，由南至北，逐步展开。该校区一共有5万人，早上从宿舍区赶往各教学楼、实验楼及图书馆的人络绎不绝。那么，现有校园道路设计规划的最大通行能力多大，能否满足学生及时赶往教学区，如果要将通行能力增加30%，应如何改造校园道路。

现已有校园平面图，通过对该校园的道路状况进行简化、标记等处理，将某一集中区域简化为一点，道路简化为一条线，并且根据网络地图测距测量出各点距离与道路宽度，简化图如图1所示。图1中，△代 表源，□代表汇，○代表路中支点，线上数字代表道路长度，单位为m。各道路宽度d如表1所示。

图1 道路简化图Figure 1 Road simplification map

表1 道路宽度表Table 1 Road width table m

明显的，问题中的道路最大通行能力属于多起点(O点)、多终点(D点)网络最大流问题。首先可以考虑建立一个基本的网络最大流规划模型，利用标号法进行求解；由于行人往往会选择较短路径进行通行，并且在出发前已有固定的目的，于是可以将每个单源到单汇分开考虑，利用最短路模型选择出两者间较短的有效路径；最后在初始模型的基础上再次增加约束条件，利用单纯形法进行求解。

2 改进网络最大流模型建立

2.1 道路饱和流量计算

由于已知校园内道路分布简化图，设各道路饱和流量为Cij，则有

其中，dij为每条道路的宽度，v为学生行驶的平均速度，S0为每人占地的平均面积。

由于南北区离每一教学区的距离各不相同，学生采取的行驶方式也会有异，一般采取骑自行车与步行2种行驶方式。查找资料可知，正常步行速度为1 m/s，正常的自行车行驶速度为3 m/s，再根据假设，步行与骑自行车的学生人数相同，可得

即可得各道路饱和流量为

可知各道路饱和流量如表2所示。

表2 道路饱和流量Table 2 Road saturation flowmeter 人/s

2.2 基于网络最大流的线性规划模型

对于基本的网络最大流问题，一般可以通过线性规划求解。因此，首先建立起基于网络最大流的线性规划模型。

由于规划设计图中的交通网络较为复杂，为了方便与合理分配流量，此处将整个交通体系利用网络流原理进行求解。即交通网络有向流为：

其中，X是顶点集，A为 有向弧集，C为有向管道容量集，即C={cij}。网络上的流，是指定义在弧集合A上 的一个函数f={f(vi,vj)}，并称fij为弧(vi,vj)上的流量。

1) 目标函数。

整个区域的流量取决于所有出发点的通行人数总和，即所求的网络流f的流值。

为求得最大通行能力，即要求得最大流值，因而可以确定目标函数为

2) 约束分析。

① 人流量守恒约束。

对于整个区域来说，出行人数在通行中不会增加或减少，即人流量始终满足于一个动态守恒状态。因此，出发处人流量始终等于汇集处人流量。据此，可得约束条件

② 节点平衡约束。

对于任意中间点，流入量等于流出量，即对于每一个i(is,t)有

③ 道路通行容量约束。

受道路宽度限制，每条道路的通行容量是有限度的，且不同道路的通行容量存在着差别。因此，在实际中，每条道路的通行容量不能大于其最大容量。因此，对于每一条弧 (vi,vj)∈A，可得约束条件为0 ≤fij≤cij。

3) 模型确定。

综上目标函数和约束条件的分析可以得到基于网路最大流的线性规划模型为

2.3 最短路模型

给定一个赋权有向图，即给定了一个有向图D=(X;A;C)，对于每一个弧a=(vi,vj) ，相应地有权w(a)=wij，又给定D中的2个顶点vs,vt。 设P是D中从vs到vt的一条路，定义路P的权是P中所有弧的权之和，记为w(P)。 最短路问题就是要在所有从vs到vt的路中，求一条权最小的路，即其求一条从vs到vt的路P0，使

当然，在通行过程中，并不会每人都选择最短的路，因此假设从某源到某汇的过程中，学生只会选择与最短路径相差30%的路，即可行路径满足

2.4 道路最大通行能力改进模型

一般情况下，学生去教学区并不是漫无目的的出发，而是身在第k个源的学生只想到达第l个汇。假设在交通流中，从第k个源到第l个汇的人数与总人数的比例是一个确定值Ckl，则有

则目标函数为

在实际交通流中，由于源与汇的数量较多，某些道路会出现双向通行的情况，对此，本文在原模型的基础上，采取分别讨论各源到各汇的通行情况的方法，对原模型中的约束条件进行了改进。

由于道路可通行的双向性，每条道路的流量为双向通行流量之和，即有

则约束条件为

3 改进网络最大流模型求解

此模型为基于网络最大流的线性规划模型，查阅相关资料可知，常用的网络最大流法有Ford-Fulkerson算法、Edmonds-Karp修正算法、dinic算法几种。本文采用最常用的Ford-Fulkerson经典算法。

Ford-Fulkerson算法采用深度优先，其实质是判断是否有增广链存在，并设法把增广链找出来，即从一个可行流出发，不断地经历标号过程与调整过程。任意设定一初始可行流，结合该算法，并通过Matlab求解，可得到最大流如图2所示。

根据图2可以得到，在基于网络最大流的线性规划模型下，校园道路的最大通行能力为14+4+16+12=46人/s。

典型的最短路模型采用的算法为 Dijkstra 方法，其基本思想是用给节点记标号来逐步形成起点到各点的最短路径及其距离值。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它表示从vs到该点的最短路的权(称为P标号)，或者表示从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的顶点数多一个，由此，至多经过P-1步，即可求得从vs到各点的最短路。

对于可选择路径的筛选，为了增加求解效率，本文依次求出s到t的第k短的路径，再与最短路径的1.3倍作比较，直至第k短路超过路径的1.3倍，停止循环。并通过A*算法依次求解出第k短路。

设起点为s；终点为t；对于一个点v，dt(v)表示从v走到t的最短路径的长度。一个状态x表示的是从s走到某个点的一条路径，把这个点记作x.v，把这条路径的长度记作x.len。接着，可以使用以下启发函数

初始状态中，x.v=s；x.len=0，每次让优先队列中f(x)值最小的状态x出队，再根据图2中所有从x.v出发的点发展下一层状态，让它们进队列。在每次出队列的状态x中，第一次遇到x.v=t时，就找到了从s到t的第一短的路径，其长度就是f(x)，第k次遇到x.v=t时，就找到了从s到t的第k短的路径。

Dijkstra算法的具体流程框图如图3所示，根据其流程图在Matlab环境中编写程序，可得到各源到各汇的最短路径与最短路长，源2到汇18的最短路结果如图4所示，粗实线代表可通行道路。

本文采取矩阵计算单纯形法，在Matlab环境中求得在新的限制条件(只走较短路程)下的最大通行量，此时各道路的通行量如图5所示。

在图5中，各道路上的负数代表向相反方向通行的流量，单位为人/min。由此可得到，考虑到最短路径以及双向性后，最大通行能力为1380 人/min，即23人/s。

图2 最大流通行示意图Figure 2 Maximum flow chart

图3 Dijkstra算法流程Figure 3 Dijkstraalgorithm flow chart

图4 源2-汇18可通行道路Figure 4 Accessible road from source2 to collection18

图5 道路通行量示意图Figure 5 Road traffic flow diagram

此结果与原模型的结果相比通行量减少，这是由于“人们会选择较短路径”以及“出发前已具有特定的目的地”，说明本模型的建立较为成功，更加符合实际性。

该校区一共有5万人，若5万人都在外通行，在最大通行能力下，所需时间为36 min，属于正常通行时间。即可知显示道路设计能满足学生及时通往教学区。

4 道路通行优化改造

提高道路通行能力的方法有很多，可以增设道路、扩宽道路宽度、改变学生出行方式与形式等。由于增设道路工程过于复杂，学生量过大导致改变学生出行方式的方法也不可取，所以本文主要考虑扩宽道路宽度来提高通行能力。

问题要求改造校园道路使道路通行能力提高30%，要求在满足道路通行能力提高的条件下，给出改造校园道路的最优方案。为此，本文再次建立线性规划模型，目标函数及约束条件如下。

1) 目标函数。

在通行能力提高量一定的情况下，道路的宽度也不能一味的扩宽，所以此时的目标为成本最低，在道路成本单价一定的情况下，将设为各条道路扩宽道路后的面积之和，即

其中，yij为第i-j条道路的增加的宽度，lij为第ij条道路的长度。

2) 约束分析。

与上述模型相似，约束条件存在节点平衡约束、源汇点平衡约束、道路容量限制，除此之外，还应增加道路通行能力限制。根据上述模型求得最大通行能力为46人/s，即有

为满足实际情况，可知在每个源处，流出量始终是大于流入量的，即

3) 模型确定。

综上目标和约束条件的分析可以得到基于网路最大流的线性规划模型为

假设各道路通行方向为上述模型中方向(若最终流量为负，则改变通行方向)，运用LINGO软件求解以上线性规划模型，解得在道路通行能力提高30%并且改变道路最小的情况下，只需将7-12号道路扩宽2 m，将6-15号道路扩宽5 m。结合道路通行量示意图可知，适当扩宽路网中的关键道路，可以提高道路通行能力且道路改造成本较低。

5 结论与讨论

基于图论网络最大流理论基础，建立了一种改进的网络最大流模型，设计了优化求解算法，并结合实例对道路通行能力进行了定量研究及优化改造，主要得到以下结论。

1) 基于基本的网络最大流的线性规划模型下，校园道路的最大通行能力为46 人/s，考虑到最短路径以及双向性后，最大通行能力为23 人/s。

2) 在道路通行能力提高30%并且改变道路最小的情况下，只需将7-12号道路扩宽2 m，将6-15号道路扩宽5 m，具有较高的可行性。

3) 模型考虑了学生通行的道路选择性，排除了与最短距离相差较大的路径，与实际情况更加符合；改进模型进一步考虑了道路双向性，加强了原模型的约束条件。

4) 最大通行能力的减少是由于“人们会选择较短路径”以及“出发前已具有特定的目的地”，表明本模型的建立较为成功，更加符合实际性。研究成果可为城市道路路径优化、设计改造提供参考。