基于Floyd算法的中小城镇环境公交线网优化

陈 彦, 胡晓军，卢 川，何帅龙

(1.合肥学院生物与环境工程系，安徽 合肥 230601；2.合肥学院建筑工程系，安徽 合肥 230601；3.安徽省交通规划设计研究院规划分院，安徽 合肥 230088)

公交线网布局方法大体是对城市开展的，对中小城镇关注的较少。又中小城镇具有公交线路少，长度短，乘客出行量小的交通环境[1]。若线路布设不恰当，便会降低路网的运载能力，损失客流。所以，对中小城镇公交线网优化布局研究有较强的现实作用。

在公交线网优化研究上，文献[2-3]均是以改进 Dijkstra 算法为手段，来确定备选线路的最佳走向；文献[4]提出了以直达客流最大为目标的公交优化模型；文献[5]以乘客时间与企业成本之和最低为目标，运用改进的模拟退火算法，消除不同线路的站点重复；文献[6]建立了规划阶段公交线网空间可达性的优化模型，并用遗传算法求解；文献[7]考虑首末站布局位置为约束，基于遗传算法求解可达性与可达强度的优化模型；文献[8]同步优化线网与发车频率，建立混合整数规划模型，比较换乘比与设定的下界值，设计改进遗传算法求解；文献[9]基于公交客流时空的不均衡性，建立以人均舒适度最大为目标的公交线网优化模型；文献[10]以寻求客运成本最低为目标，建立了启发式方法优化网络；文献[11]基于遗传算法，通过最小化的改变路网走向，来运输系统中的交通量；文献[12]运用累积前景理论对城市公交网络进行优化。文献[13]提出了“逐条布设、优化成网”的方法，即用最短路径确定线路走向，以直达客流量最大为目标，逐条增设线路到网络中的一种线网布设方法。

通过上述对公交线网的相关研究，可以发现研究基于不同的优化目标，目标可分为乘客、企业层次的优化及二者并重的双目标优化，选取不同的约束条件(公交线网覆盖率、线路重复系数、换乘比例、线网长度等)，建立不同的模型目标函数，最后采用不同的算法，得出与模型设定相吻合的最优解，很难实现全局最优。

针对中小城镇的公交线网的规划布局中，从选定起讫点到布线，均是在站点与站点之间的布设。本文考虑在站点之间设立一个新的插入点，结合路网的公交乘客出行OD(起终点间的交通出行量)，以直达乘客最大化为目标，基于Floyd算法确定公交线路具体走向，优化了线网布局，提高了公交对客流的运输效果，方法简单实用，可操作性强。

1 Floyd算法

Floyd算法是一种用于寻找给定的加权图中任意两个顶点间最短路径的算法[14]，边权可正可负。

设立权矩阵D，其中

算法步骤：

1)输入权矩阵D(0)=D；

假设各节点间的公交行驶时间如图1所示。

图1 某道路节点间行驶时间图

由上述可得到其相应的邻接矩阵D如下

矩阵D中元素dij(i，j=1，2，…，7)为节点vi到vj的距离，其中dij=∞为节点间无路径。此处直接编程计算分析。输入邻接矩阵D，可输出各节点之间最短路径值矩阵D1和最短路径矩阵D2。

由输出的矩阵D1和D2可得任一点的最短路径值和最短路径，比如V1到V7的最短路径值为13，最短路径为V1→V2→V3→V5→V6→V7。文章基于逐条布设、优化成网方法，并假设在本次所选取的小城镇中，各断面流量均小于断面运载能力。考虑工程实际情况，线网中存在尚未运输客流，通过插入节点法，来提高线网的直达乘客量，从而增大了线网的不换乘比，对中小城镇线网如何优化布设有一定参考。

2 案例分析

图2为某小城镇的交通分区及道路网络，路网数据为公交车行驶时间，乘客O-D量如表1所示。

图2 某中小城镇交通分区与路网示意图

起点终点ABCDEFGHISUM A85352706246189465938421 721 B38633480204104544544701 350 C54450282502112687446601 930 D65850648636180584256822 022 E1881201241362468768042816 F38561011066818765432517 G1207886886265267053595 I426863353637466218389 SUM2 1171 7682 1731 4138034404644734499 651

由表1可知，以A、B、C、D为起讫点，拟设2条双向线路。其余E、F、G、H、I为重要节点。

2.1 备选线路的最佳走向及直达乘客量

由于是第一条线路，故不对行驶时间复线修正。线路按最短行驶时间布设。输入相应的邻接矩阵D，由软件生成结果，采用反向追踪法，同时，对直达乘客量矩阵修正。可得各备选路线起终点间的公交线路情况，如表2所示。

表2 各备选路线起终点间的公交线路

2.2 优化线路的布设及乘客O-D量修正

直达乘客量矩阵修正后，得出备选线路的最大直达乘客量Zij+Zji值，取直达乘客最大化线路为公交网络中的线路，按最短路线布线。

在选中的区域中，ZBC+ZCB=2 015，为各备选线路中的最大直达乘客量，故取B→C、C→B为公交线路，并按其最短线路5→4→9→14→13→12→17→16→21布线。

根据[Zij+Zji]max来设置公交线路[i，j]后，基于前述假设，线路上客流均被全部输送，则在原乘客O-D矩阵中，去除该线路运载的O-D量，对其进行第一次修正。

2.3 复线系数

公交线路布设后，对行驶时间进行修正[15]，即乘以复线系数K0。本次拟用复线系数以50%的比例求解。即若复线条数为1，则复线系数取1.5；复线条数为2时，取2.25，以此类推。具体复线系数取值，可结合具体工程项目作调整。

此时，只剩下A→D、D→A两对起终点，故设线路A→D、D→A为公交线路，具体的线路走向为1→6→7→8→13→18→19→24→25。

线路直达乘客量ZAD+ZDA=550+892=1 442。各断面流量均由该线路全部运送，可得相应的第二次修正的乘客O-D矩阵如表3所示。

表3 第二次修正的乘客O-D矩阵

2.4 路线布设方案对比

显然，由表3可以看出，乘客O-D矩阵中存在潜在的客流量，此处增设两条线路：第三条线路A→E、E→A，第四条线路B→C、C→B。在已设有线路的路段上，对其行驶时间进行修正，且各断面的流量均小于运载能力，全部被运送。对修正后的公交车行驶时间矩阵，运用Floyd算法，编程计算分析，输出各点之间的最短路径值和最短路径。为方便乘客的出行，追求运送人流量最大化。此处，对比以下两种方案。方案一：以最短路径进行布设线路；方案二：在起终点间添加合理节点，对线路稍作调整，以起点→插入点，插入点→终点之间最短路径布线。

1)以各节点之间为最短路径为备选路线

由软件运行结果可得， A→E(或E→A)的最短路径值为356， 最短路径为1-2-7-12-17-22-23。得出， 线路直达乘客量ZAE+ZEA=399+377=776。B→C(或C→B)的最短路径值为470，最短路径为5→10→15→20→19→18→23→21。该线路直达乘客量ZBC+ZCB=228+232=460。

2)对线路稍作调整作为备选路线

综上所述，将两种方式的结果进行对比，如表4所示。

表4 两种方案结果对比汇总

显然，在合理的范围内，对线路进行调整，对运送人流量的最大化有影响，方案二对路线稍作调整，提高公交车的实际运载量，不换乘比增大，达到优化线网的作用。所以，在实际项目工程中，不能局限于严格的按照最短路径来选取备选线路，可稍作调整线路，避免损失客流，出现车辆运载效用不高，居民出行得不到改善等情况。最终得出公交路线的走向，如图3所示。

图3 公交网络优化图

3 结论

(1)本文在选取最短路径为备选方案时，引入了Floyd算法，并使用MATLAB R2016a进行编程求解，最终得到公交优化方案，在追求直达客流最大的目标下，尽可能的采取最短路径，提高实际直达乘客量、减小乘客的换乘比例。

(2)在实际的中小城镇公交线网优化的过程中，可打破以往站点与站点之间的布设线路，避免一味的追求最短路径，在点与点中插入一个节点来调整线路走向，使得线路走向与客流走向更加相一致，优化公交线网布局，为推进中小城镇公交线网优化提供有益参考。