珠海市公交线网优化研究

第12卷第32期2012年11月1671—1815（2012）32-8622-06科学技术与工程Science Technology and EngineeringVol.12No.32Nov．2012 2012Sci.Tech.Engrg.珠海市公交线网优化研究徐小红刘炜*江铭杰（上饶师范学院图书馆，上饶334001；北京师范大学珠海分校应用数学学院，珠海519087）摘要依据珠海市公交线网的拓扑特点及公交乘客O-D 量（起点、终点的客流量），提出了以直达乘客运输量最大为目标函数的公交线网优化模型。

运用数学规划中求解指派问题和最短路问题的算法，对公交线网优化模型进行求解，得到最优公交线网规划方案。

此外，还运用了线路客流分布均匀性检验方法验证了优化方案的正确性。

关键词公交线网优化指派问题最短路问题中图法分类号O224；文献标志码A2012年6月27日收到，7月20日修改*通信作者简介：刘炜，男（1977—），北京师范大学珠海分校应用数学学院讲师，硕士。

研究方向：最优化理论与算法。

E-mail ：li-uwei1949@ 。

城市的公交线网是城市的生命线，与市民的出行息息相关。

它决定着城市未来发展的方向。

如何在现有条件下构建一个运行顺畅的城市公交线网，是城市交通规划部门迫切需要解决的问题。

公交线网的规划与设计，必须以公交乘客O-D 量为依据，以方便居民出行为目的，并兼顾公交企业效益。

因此，在规划与设计公交线网时，必须考虑如下目标：（1）线路走向必须与主要客流方向相一致，以满足乘客乘车需要；（2）尽可能组织直接运输，使全服务区乘客总换乘次数最少；（3）尽可能按最短距离布设路线，使乘客总乘行距离最短；（4）使线路上的客流分布均匀，以充分发挥运载公交的运能。

可见，公交线网规划实质上是一个优化问题。

目前，国内外已有不少学者对公交线网优化方法进行研究［1—5］。

通常是将公交线网优化归纳为一个非线性规划或二次规划问题。

但由于维数太大，求解往往不可能，因而不能获得最优解。

本文运用数学规划中的“指派问题”求解思想对珠海市公交线网进行优化。

1拟设线路起讫点的优化配对要确定公交路线，必须先确定拟设的线路起点与终点。

通常，在确定线路起讫点时，需要考虑以下两个因素。

（1）公交客流量。

在公交客流发生量或吸引量比较集中的场所，需设置起讫点站，流量特别大的交通区，可设置多个起讫点站。

（2）实际需要。

对某些特殊地点，如车站、码头、风景区、居民点等，即使其流量不是很大，但为了方便居民也需设置站点。

由于公交线路通常为双向线路，若某点为某线路的起点站，则它必为另一方向线路的终点站，故起点站、终点站的个数应为偶数，以便形成双向线路，而双向线路的条数为起点站或终点站个数的一半。

观察表1（数据来源于珠海市巴士公交公司技术部），发现A 、C 、D 、E 有较大的吸引量，而F 、I 、G 为长途汽车站、机场等一些居民生活必需的基本设施所在分区；并且在城市的边缘，为了方便居民出行，必须将它们设置为拟设线路起讫点。

又A 、C 、D 三个区域的人流量较多，所以应设置为2个起点、终点。

又因为公交线路通常是双向的，所以为了方便起见，我们把起点和终点都设置成同一点。

表1珠海市公交乘客O-D 量表（2007年）D OA 香洲B 新香洲C 吉大D 拱北E 前山F 上冲G 金唐H 南屏湾仔横琴I 金湾产生量总计A 香洲2574042002772032160114605400858072603180125700B 新香洲5820180426058201560840102096054021000C 吉大1404021006840147604920234034204440240055260D 拱北19740132012780116405400246026404260168061920E 前山2892013801926023940100205100228069002940100740F 上冲15540840906011580630024608403360108051060G 金唐258607201272014880264013207860132030067620H 南湾仔横琴14040660678012240612016809605880270051060I 金湾5700300258039001380360540324078018780吸引量总计155400117001020001309204980021960281403762015600553140确定了拟设线路起讫点后，便可对起讫点进行优化配对，以构成公交线路。

不同的公交线路所能运送的直达乘客量是不同的，这些直达乘客量不需要换乘。

要使全服务区的乘客总换乘次数最少，则必须使各线路的总直达乘客量最大。

即，在进行优化配对时，必须以全服务区总直达乘客量最大为目标函数。

一条公交线路只能有一个起点，终点，即一个起点（或终点）只能与一个终点（或起点）配对。

因此，起讫点优化配对间题，实质上是一个指派间题（Assignment Problem ），其数学模型为maxS =∑ni =1∑nj =1C ij x ij 。

其中，S —全服务区公交网总直达乘客量；n —线路起点或终点个数；C ij —i 起点与j 终点配对时，该线路所能运送的直达乘客量，它与线路走向有关。

2拟设线路的最佳走向起讫点最佳配对的关键在于确定直达乘客量C ij ，直达乘客量与线路走向有关。

为了使全服务区乘客总乘行时间（或距离）最短（各交通节点间距见表2（数据来源于珠海市巴士公交公司技术部）），在确定线路最佳走向时，以两点间行驶路程最短为目标，即每一起讫点对间的最短路线均被取为拟设公交路线的备选方案。

最短路问题可采用矩阵迭代法或Dijkstra 算法［1］求解。

表2各交通节点间距（单位：km ）12345678910111213141516171819202122103 5.1230 2.2 1.33 2.21.1 6.840 5.1 1.85 5.10 5.532.4 6.56 5.5036.2 5.2732.43608 5.20 3.5 2.29 6.53.50 3.1 6.6910 1.11.83.16.411 1.30 1.8 6.212 5.11.80213206 3.914 6.86.66.46.260 5.66.65.5 3.815 2.25.606.9 6.316 3.96.6011.91.32.7179 5.5 6.90 1.53.11811.9010.719 1.310.70 2.720 3.8 2.7 2.70 2.121 1.5 2.10 2.4226.3 3.1 2.40326832期徐小红，等：珠海市公交线网优化研究通过计算，各备选线路起讫点间的最短路线如表3所示。

表3各备选线路起讫点间的最短路线起讫点交通区号最短路线节点号A—C16—20—21A—D16—20—21—17—15—8A—E16—13—12—11—2A—F16—13—12—11—2—1A—G16—18A—I16—13—12—11—2—3—10—4—5—7C—D21—15—8C—E21—20—16—13—12—11—2C—F21—20—16—13—12—11—2—1C—G21—20—19—18C—I21—17—9—5—7D—E15—8—9—10—3—2D—F15—8—9—10—3—2—1D—G15—17—21—20—19—18D—I15—8—6—7E—F2—1E—G2—11—12—13—16—18E—I2—3—10—4—5—7F—G1—2—11—12—13—16—18F—I1—2—3—10—4—5—7G—I18—16—13—12—11—2—3—10—4—5某起讫点间的路线走向确定好以后，O点、D点均在该线路上的乘客O—D量即为该起讫点对不需要换乘的直达乘客量。

根据表3中最短路线及乘客O—D量表计算出备选路线直达乘客量Cij如表4所示。

表4各备选路线直达乘客量Cij终点起点A C D E F G IA2574027720746401722028560858057480C1404068401476038280519602604024300D6222012780116401296012960612008640E3612087360418201002051004800019140F5880011910041820630024607014023280G2586052620128100464005910786089640I92280393601938019080178801065007803公交线网优化如前所述，公交线网优化问题主要归结为起讫点配对优化及线路走向优化问题。

确定了各起讫点对间最短路线及各备选线路的直达乘客量以后，尚需解决的是求解0—1规划中的“指派问题”。

“指派问题”可采用匈牙利算法求解［1，2］。

在用该法解决公交线网优化问题时，需先对系数矩阵表（即直达乘客量表Cij，表4）进行如下修正。

3.1双向配对修正一般来说，公交线路都是双向的，即有线路R ij 就必有线路R ji，如本例中要求确定的是4条双向线路。

为了使最后的线路刚好成对，即若起点与终点配对，则必有终点与起点配对，所以必须把直达乘客量表C ij（表4）对称化，即取直达乘客量C ij=Cji=C'ij+C'ji2，C'ij原直达乘客量。

3.2避免自相配对修正同一交通节点不能成为同一条线路的起点与终点，即应避免同一交通节点的自相配对。

因此，令C ii=0（i=1，2，3，…，n）。

经过上述修正后，得表5所示的直达乘客量表。

表5修正直达乘客量Cij起点区号终点区号A C D E F G IA0208806843026670436801722074880C2088001377062820855303933031830D6843013770027390273909465014010E266706282027390057004720019110F436808553027390570003802520580G1722039330946504720038025098070I7488031830140101911020580980700 3.3线路长度修正公交线路不宜过长或过短，过短既增加了乘客的换乘次数，又使车辆在终点站停歇时间相对增加而降低营运车速。

过长会影响行车准点，造成沿线客流分布不均匀而导致运能利用不平衡。

若拟设的起讫点之问的长度大于最长限制距离或小于最短限制距离，则该起讫点间不应设置线路，因此，应取该起讫点间的直达乘量客C ij=0。

3.4一区设多站修正当某些区的出行量特别大时，往往要设置多个起讫点，此时，系数矩阵表中相应区的起点行、终点列要重写，重写次数等于该区起讫点个数。