基于边介数的大城市公交网络优化模型

大城市交通拥堵问题是目前研究的热点，它对居民出行影响越来越大.从北京、广州等大城市的交通现状看，无法在短期内得到有效解决.很多国内外专家就拥堵问题对复杂网络理论进行了研究［1－2］，它是研究复杂网络的有力工具.吴建军等对城市交通系统的复杂性进行了研究，提出缓解交通拥堵的策略和运输网络级联失效的预防策略［3］;Motter等引入介数定义节点的负荷，提出一种级联失效模型［4］;Yan G等为控制通信网络中的信息堵塞和改善网络信息传递效率，提出基于节点度的广义路由算法［5］;Wang W X等提出集成动静态信息的混合路由算法［6］和基于本地信息的路由策略［7］;这些算法和策略是在通信网络特征基础上提出和论证的，是为研究方便，假设所有节点(路由器)数据处理能力相同，边权都为1，最短路为边数最少的路径，显然这与交通网络特征不符.

因此，本文结合公交网络优化设计的实际，在分析居民出行策略的基础上，应用复杂网络理论，提出基于边介数的大城市公交网络优化模型及其实现算法.它同时考虑了不同的路段权重和节点处理能力，并对协调参数β最优值进行了深入分析和求解.

1 居民出行策略分析

在日常出行中，居民一般以最短路策略选择路径到达目的地.中小城市最短路策略是有效的，在大城市出行需求量较大，集中在最短路会造成交通拥堵严重，使最短路出行时间变长，成为非最短路或无法通行的路径.居民的这种出行策略是目前大城市交通拥堵的主要原因之一.

对于选择小汽车、出租车等方式出行的居民，可根据经验和当时的情况，重新选择出行路径，绕过交通拥堵点，这样虽然相对最短路绕远了，但是缩短了由于交通拥堵损失的时间.城市公交车是按照固定站点、固定线路和固定时刻表为居民提供服务的交通方式，在发生交通拥堵时，无法重新选择路径，只能在公交网络优化设计时，融合绕行策略，绕过交通拥堵点，实现重新选择路径的目的.

绕行策略是在公交网络优化设计时，使公交车能适时绕过这样的拥堵节点，使居民公交出行时间变短，线路准点率提高.它是以牺牲一部分公交网络效率为代价换取居民公交出行成本的降低.

2 拓展边介数

为使公交网络优化设计时实现绕行策略，应用复杂网络理论中的边介数识别交通拥堵.边介数为网络中所有经过该边的最短路径数量与最短路径总数之比［8］.为适应公交网络特征，引入参数β，将边介数进行拓展.

定义1有效边介数定义为对于给定的参数β，网络中所有经过该路段的最短路径数量与最短路径总数之比.记作Bβ(i)，则

其中:Bβ(i)为路段i的有效边介数，njk为节点(j，k)之间最短路径的数量，njk(i)为节点(j，k)之间最短路径中经过路段i的数量，β为协调参数，V为网络中全部节点的集合.

定义2规定L(p(s→t):β)为对于给定参数β，节点(s，t)之间路径的长度，则节点(s，t)之间的有效路径是使L(p(s→t):β)值最小的路径.其中L(p(s→t):β)=，N 为路径p(s→t)包含的路段总数，r(i)为路段i的阻抗，s.显然搜索有效路径时，路段i的有效权重为Bβ(i)r(i)，它是在有效边介数的基础上建立的，在有效路径上布设的公交线路就是有效线路，有效线路形成的公交网络就是有效网络.

根据复杂网络理论和有效路径的定义，协调参数β在这里表征有效路径偏离拥堵节点的程度.当β=0时，有效路径为网络最短路，即居民出行为最短路策略;当β＞0时，有效路径开始偏离拥堵节点，部分居民出行时采取绕行策略;当β＜0时，有效路径更倾向于经过枢纽节点，即居民出行易先到枢纽站点换乘.由此可知，参数β变化过程模拟了居民出行策略的变化，当β＞0时，有效路径体现了居民出行应用绕行策略的情况，参数的大小体现了居民出行绕行的程度，最优参数值求解详见下文.

3 基于边介数的公交网络优化模型

为均衡网络效率和居民出行时间，在搜索有效路径的基础上，应保证公交网络运输效率最大化，因此，目标函数为两个:1)L(p(s→t):β)值最小化;2)公交网络运输效率最大化.

L(p(s→t):β)最小时的有效路径在β＞0时模拟了居民出行时采用绕行策略的情况，应用绕行策略优化的目的就是使所有公交乘客出行时间缩短.目标函数表达式为

绕行策略使公交车运行过程中，会绕过介数较大的节点，它们一般都是相对重要的节点或枢纽站点，若过多乘客绕过，必然会使公交网络运输效率低下.为使公交网络运输效率最大化，设计目标函数表达式为

其中:Z为公交网络运输效率，人次/s;xij为线路i上路段j的公交客流量，人次;rij为线路i上路段j的阻抗，s.

单条线路的约束条件包括线路长度，路线非直线系数，路线客运能力，复线条数等.整个线网的约束条件包括线网密度，乘客换乘系数，站点覆盖率，线网覆盖率等.它们的计算可参考文献［9-10］，从而建立公交网络优化模型.

4 优化模型算法实现

建立的公交网络优化模型为双目标规划模型，大城市公交网络比较复杂，采用解析法求最优解计算量较大，有些模型可能不存在唯一的最优解．因此，本文提出一种操作性较强的算法，计算过程较为直观，可控性较强．

4.1 搜索备选线路集

计算路网中各个路段的有效权重，基于绕行策略，应用带约束条件的k最短路算法搜索备选线路集，其算法如下:1)取一起终点对(s，t)，应用Dijkstra法搜索它们之间的最短路径sp1，检验sp1是否满足线路长度约束，若满足则将sp1作为备选线路，并取下一起终点对进行搜索备选线路，否则转入下一步，其中spk表示k最短路径．2)当确定spk-1时搜索spk，对Vs中的点进行标号和更新，取一点h，它的标号值为 Ph=，则 Sk=并确定spk．若Ph=Sk且spk过点h，则更新h的标号，更新公式与标号公式相同;若该点已没有邻接点，则标号更新为无穷大．其中Vm为m最短路径经过的点集合为最短路邻接点集合，Li为节点i到起点s的最短距离，Lij为邻接点i、j之间的距离，Sm为m最短路径的长度．3)检验spk是否满足线路长度约束，若满足则将其作为备选线路;否则返回步骤2．4)检查是否是最后一对起终点，若是则得到备选线路集合SP，否则返回步骤1．

这样基于绕行策略得到备选线路集合SP，根据参数β取值，部分路径可绕过交通拥堵点，因此备选线路集合中的线路都是有效线路．

4.2 有效线路布设

根据目标函数，采用效率最大化原则布设有效线路．分别计算备选线路的运输效率，将运输效率最高的备选线路布设在路网中，然后对客流OD矩阵进行更新，其算法思路为:计算线路各个断面的断面流量、各个站点流量以及站点容量［11］．1个站点可能同时被多条线路共用，此时，站点流量为经过该站点的各个断面流量之和．检验各个站点流量和站点容量，若各个站点流量均小于站点容量则经过该线路的OD量能全部被运送;若站点流量大于站点容量，则布设的线路只能运送部分客流OD量，具体分为3步．

第1步:确定超载站点集合．选取超载站点遵循就近原则，即线路断面的超载流量向公交行驶逆方向的站点就近分配，分配流量与各站点的上客量相等(或小于最后一站点上客量)，分配到超载客流的站点就是超载站点．

其中:ΔSl为超载站点l上的超载流量，人次/h;Yl为超载站点l上的背景流量，人次/h;Xl为超载站点l上新增流量，人次/h．

存在实数m满足

其中:Glk为站点k对超载站点l贡献的流量;qkij为从站点k上车的OD量;(l-p)表示l减去p，其他类似符号同理．

则站点l后的(m-1)个站点上车经过站点l的OD全部留剩，站点(l-m)上车经过站点l的OD部分留剩．站点l后m个站点进入超载站点集合Vs．

第2步:确定站点(l-m)的OD更新量．在同一站点(l-m)的乘客，具有同等上车的权利，同时具有同等留剩的机会．所以站点(l-m)的OD更新量计算公式为

其中:Qlij-m为从站点(l-m)上车，为超载站点l贡献的客流量．

第3步:某些站点可能是多个超载站点的贡献者，取站点OD更新量时，为保证全部站点均不超载，每一OD留剩量取它在线路上各站点留剩量的最大值，即OD矩阵［i，j］更新值为

OD矩阵更新完毕，重新搜索备选线路和布设有效线路，直到所有的起始点对都布设一条有效线路，再进行逐步的调整优化，得到满足线路约束的有效网络．

5 确定最优参数β

5.1 参数分析

根据前面的分析可知，参数β与居民出行时间之间的函数关系曲线应为先下降再上升．当发生交通拥堵时，部分居民采取绕行策略，偏离枢纽节点可绕过交通拥堵点，这时可缩短居民出行时间;随着参数β的逐渐增大，居民出行路径逐渐偏离拥堵点，离交通拥堵点越来越远，居民出行时间就越来越短;当参数β达到一个临界值βc时，居民出行路径偏离交通拥堵点缩短的时间与居民绕远增加的时间相等．当参数β继续变大时，居民总的出行时间开始逐渐增加．

显然，参数β的最优值与实际网络和城市交通拥堵程度有关，交通拥堵越严重，临界值βc越大．通过分析不同β可观察绕行策略下居民的出行轨迹，从而验证该策略在大城市公交网络优化设计中的合理性．

5.2 参数求解

长春市交通拥堵严重，其中主干道人民大街、南湖大路、自由大路、亚泰大街、解放大路、吉林大路等“堵点”较多，其他市区支路交叉口拥堵也较为严重．以长春市道路网作为基础网络求解参数β的最优值．将长春市划分为163个交通小区，应用TransCAD搜索并记录它们之间的有效路径，经过分析计算可得到各个网络指标值．

根据反复计算的结果，参数β与拥挤网络效率E1、平均出行时间的变化趋势见图1．从图中可以看出，当居民平均出行时间最短，网络效率最高时，β的最优值为0.1．β ＞0时，的变化趋势与参数分析中的结论一致;β＜0时，有效路径倾向于经过枢纽站点，由于枢纽站点处理能力较高，增长较慢．越短，E1越高，这与图中趋势一致．

参数β与零流网络效率E0、拥挤网络效率E1以及由于拥挤造成的效率损失ΔE的变化趋势见图3．从图中可以看出，由于交通拥挤，存在网络效率损失．相对于E0，E1的峰值右移，β值由0变化增长至0.1．在β=0.1时，损失值急剧减少，这种相变现象是由于绕过交通拥堵产生的积极影响．当β继续增大时，出行路径逐渐绕到负荷较低的路段，交通拥堵影响较小，效率损失也逐渐降低．β＜0时，由于枢纽节点发生拥堵，网络效率损失保持较大的数值．

图2 不同β与、的变化趋势图

图3 不同β与E0、E1、ΔE的变化趋势图

6 结论

1)根据绕行策略优化城市公交网络，既可充分利用枢纽站的高效处理能力，又可使公交出行适时避开交通拥堵，缩短出行时间，因此可适合在大城市或存在交通拥堵的城市应用．

2)基于边介数优化的大城市公交网络可使部分乘客出行时避开交通拥堵点，这将增强网络对蓄意攻击的抵抗能力，改善网络的鲁棒性．

3)双重策略提高公交网络的可靠性．绕行策略是将公交车作为机动车一种，考虑整个交通系统的拥堵对公交系统的影响;站点容量模型考虑了由于线路运输能力限制产生的拥堵对公交系统的影响．

4)以长春市路网为基础求解β最优值，结果表明，最小化网络平均出行时间、最大化网络效率可确定β的最优值．

［1］汪小帆，李翔，陈关荣．复杂网络理论及其应用［M］．北京:清华大学出版社，2006．

［2］PORTA S，CRUCITTI P，LATORA V．The network analysis of urban streets:a dual approach［J］．Environment and Planning B:Planning and Design，2006，33(5):705－725.

［3］吴建军，高自友，孙会君，等.城市交通系统复杂性:复杂网络方法及其应用［M］.北京:科学出版社，2010.

［4］MOTTER A E，LAI Y C.Cascade-based attacks on complex networks［J］.Physical Review E，2002，66:65102.

［5］YAN G，ZHOU B，HU B，et al.Efficient routing on complex networks［J］.Physical Review E，2006，73:46108.

［6］WANG W X，YIN C Y，YAN G，et al.Integrating local static and dynamic information for routing traffic［J］.Physical Review E，2006，74:16101.

［7］WANG W X，WANG B H，YIN C Y，et al.Traffic dynamics based on local routing protocol on a scale-free network［J］.Physical Review E，2006，73:26111.

［8］ BOCCALETTI S，LATORA V，MORENO Y，et al.Complex networks:structure and dynamics［J］.Physics Reports，2006，424:175 －308.

［9］王炜，杨新苗，陈学武.城市公共交通系统规划方法与管理技术［M］.北京:科学出版社，2002.

［10］胡启洲，邓卫.城市常规公共交通系统的优化模型与评价方法［M］.北京:科学出版社，2009.

［11］赵淑芝，田庆飞，曹阳.基于站点容量限制的公交效率网络设计模型［J］.吉林大学学报:工学版，2011，41(增刊1):81－84.