0 引言

随着城市的日益扩张，城市居民交通出行问题越来越严重，构建合理高效的公共出行系统成为缓解这一问题的有效手段。在公交系统设计中，公交线网规划是最关键的部分，因此，如何依据现有的客流出行需求设计和优化相应的公交线网成为了城市交通研究热点。

国外对于公交线网优化起步较早，如Lampkin等^[1]在1967年就进行了公交线网规划的初步研究，他们以节约运营车辆设备为优化目标，将公交线路设计和线路车辆配置分为两个阶段进行优化。随后，Newell^[2]和Salzborn^[3]根据给定的公交资源，从乘客的角度优化发车频率，使乘客出行时间最小化。相比于国外，国内学者对于公交系统研究较晚，如1992年，刘清等^[4]展开了对公交线网模型和算法的研究，王炜^[5]对网络规划软件进行了相关研究。但早期的公交线网都是针对单条线路或小规模的网络进行设计，考虑因素较少，假设条件较多，模型较为理想化，与实际的公交线网设计要求存在一定的差距。

考虑到公交线网设计的实际需求，文献[6-12]从网络层面对公交线网设计进行了相关研究。由于网络规模变大，考虑因素增多，传统的解析式算法很难求解出有效解，因此这些研究都集中在如何设计有效算法上求解该问题。且研究表明，由于公交线网优化问题属于NP-Hard问题，智能算法相比于其他算法对于该问题求解更为有效^[13-15]。

通过对公交线网文献综述回顾，现有的公交线网规划主要是以乘客出行时间及运营商的车辆配置为主要优化目标，分阶段分别对公交线网结构及线路的车辆数量配备进行优化，且研究集中在城区公交线网设计问题，对于城郊公交线网设计很少涉及。

而在城市发展的过程中，由于城市扩张，城郊出行需求日益增长，仅仅考虑城区公交系统的优化建设很难满足现有的城市发展需求，据此，本研究针对城郊公交设计问题，引入物流领域Milk-run线路的Hub-spoke设计理念，其中Milk-run概念的提出是应用小批量的货物进行循环取货^[16]，hub站点可以实现货物聚集，形成规模优势^[17]，将其应用到城郊公交线网设计，可以用Milk-run线路及hub站点设计将公交站点分布密集区域的客流集中到hub站点，形成规模优势，实现大客流运输，以达到优化现有的城郊公交网络服务水平的目的。

1 模型构建 1.1 模型假设

城郊公交线网优化问题是公交线网规划及线路车辆配置组合问题，目的是为了获取最佳的线网布局及相应的线路发车频率，尽可能使乘客出行时间最小化。依据公交线网规划相关研究，对模型构建做出如下假设：

(1) 假设客流出行需求已知。

(2) 假设线路hub设置数量确定。

(3) 有直达服务的，乘客优先选择直达服务出行。

(4) 规划区域站点数量及站点位置确定。

(5) 可以分配到线路的车辆总数已知。

(6) 站点停靠时间已知。

(7) 不考虑交通状况对公交车辆运行速度的影响

1.2 模型构建

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

式中，Z为目标函数；o, d, h, i, j, k为站点标号；l为线路标号；D_o, D_d为客流需求起始点和终到站点集合，D_od为从站点o到站点d的单位小时出行客流需求量；T_od为单位人次从站点o到站点d所需的总在车旅行时间；W_od为单位人次从站点o到站点d所需的总等待时间；T_oh^h_od为单位人次从站点o到hub站点h的在车旅途时间；T_hd^h_od为单位人次从hub站点h到目的站点d的在车旅途时间；c_oh为站点o到站点h的在车旅行时间；x_ohl为0-1变量，当线路l连续相邻经过站点o和站点h时取1，否则取0；x_ojl为0-1变量，当线路l经过连续相邻站点o和站点j时取1，否则取0; RT_jh^l为0-1变量，当线路l通过站点j和站点h时取1，否则取0；T_jh^l为线路l通过站点j和hub站点h的在车旅行时间; c_oj为站点o到站点j的在车旅行时间; s为站点平均停靠时间；c_hd为hub站点h到目的站点d的在车旅行时间; x_hdl为0-1变量，当线路l经过连续相邻hub站点h和目的站点d时取1，否则取0;x_hjl为0-1变量，当线路l经过连续相邻hub站点h和站点j时取1，否则取0;RT_jd^l为0-1变量，当线路l通过站点j和目的站点d时取1，否则取0;T_jd^l为线路l通过站点j和目的站点d的在车旅行时间; c_hj为hub站点h到站点j的在车旅行时间; W_oh^h_od为单位人次从站点o到hub站点h的等待时间；W_hd^h_od为单位人次从hub站点h到达目的站点d的等待时间(其中该时间是由于hub站点换乘所导致的二次换乘时间，将其列为目标函数的一部分进行优化，实际使两次乘车行为有效衔接，减少换乘所带来的影响)；h_oh^h_od为站点o到hub站点h的Milk-run线路发车间隔，h_hd^h_od为hub站点h到目的站点d的发车间隔，RT_ik^l为0-1变量，当线路l通过站点i和站点k时取1，否则取0;x_ikl为0-1变量，当线路l经过连续相邻站点i和站点k时取1，否则取0;x_ijl为0-1变量，当线路l经过连续相邻站点i和站点j时取1，否则取0;RT_jk^l为0-1变量，当线路l通过站点j和站点k时取1，否则取0;L_o为线路起点站点集合；L_m为线路的中间站点集合；h_num为实际hub站点设置数量；h_set为预先设置的hub站点数量；L为线路集合；f_l为线路l的发车频率；T_l为线路l的单程旅行时间；B为车辆总的配置数量。

模型说明：式(1)为目标函数计算方式，为乘客总的车旅行时间和等待时间的和，式(2)为单位人次站点o到hub站点h的在车旅途时间计算式，式(3)为单位人次从站点o到站点d所需的总等待时间计算式，式(4)和式(5)分别为单位人次从站点o到hub站点h的在车旅途时间计算式和单位人次从hub站点h的在车旅途时间计算式，式(6)和(7)分别为乘客从站点o到hub站点h和从hub站点h到达目的站点d的平均等待时间计算式，式(8)为0-1变量RT_jh^l的计算式，式(9)为约束线网中实际设置的hub数量要与预设的hub数量一致，式(10)为所有线路分配的车辆总和不能大于现有可用的车辆总数量。

2 求解算法

为求解所构建的优化模型，本研究设计了相应的求解算法。首先，根据站点位置信息对站点进行分类，分类数量等于给定的hub数量，然后将规划每个类的Milk-run线路设计转化为经典的TSP问题求解，然后对于每条Milk-run线路选择最佳的hub位置，最后给每条线路分配相应的车辆数量，具体算法步骤如下。

Step 1  数据输入：将规划区域站点数量、站点间最短出行时间、客流需求及参数进行设置，包括站点平均停靠时间和hub设置数量输入。

Step 2  站点聚类：依据站点间的距离及hub数量，采用K-means算法对规划区域的公交站点进行聚类。

Step 3  Milk-run线路设计：得到聚类之后，进行Milk-run线路设计时，该问题就变成了经典TSP问题。本研究设计了局部最优算法，得到最优解，其中Milk-run线路设计步骤如下。

(1) 随机生成某一个初始Milk-run的线路。

(2) 计算并记录Milk-run的线路长度。

(3) 改变Milk-run的线路结构，计算并记录新的Milk-run的线路长度。

(4) 如果新的Milk-run的线路长度小于原Milk-run的线路长度，用新的Milk-run的线路替换原来的线路，并返回(2)；否则返回(3)。

(5) 判断是否达到算法终止条件，在本算法中终止条件设置为目标函数连续迭代P1代，目标函数值不发生变化，即认为目标函数没有优化空间。

其中所设计的改变Milk-run的线路长度有3种方式，分别见图 1~图 3。

① 站点交换：首先随机确定需要交换的站点对，如图 1(a)所示，为站点2和站点5，然后交换站点位置，交换之后的线路结构为图 1(b)。

② 线路截断对接：首先确定需要截断的点，如图 2 (a)所示，为站点3和站点4之间，截断对接之后的线路结构如图 2 (b)所示。

③ 线路截断翻转对接

Step 4  hub站点确定：由于Milk-run线路内任意站点都可作为hub站点，但是由于各站点位置不同及客流在站点间分布不均，需要找出最优的hub站点，其步骤入下。

(1) 首先设置站点计数器count=1，然后对一条Milk-run线路随机选择1个站点i作为唯一hub站点，依据该线路的客流需求，计算相应的出行时间T_i，并将站点i作为最优hub选取站点s_opt，T_i作为最优出行时间T_opt。

(2) 选择该Milk-run线路初始i+count作为唯一hub站点，同样地依据客流需求，计算相应的出行时间T_i+count。

如果T_i+count＜T_opt，则最优hub选取站点s_opt设置为站点i+count，最优出行时间T_opt设置为T_i+count，并使count=count+1，然后返回步骤(2)，否则使count=count+1，然后进入步骤(2)。

(3) 直到所有站点都被当作过hub站点，则停止计算输出最优结果s_opt。

Step 5  线路网络确定：线网布局由规划区域Milk-run线路，以及规划区域中最优的hub站点与规划区域外目的地连接的两站点直达线路组成。

Step 6  线路车辆数量分配及优化：通过前面的优化步骤对已经优化好的公交线路进行车辆数进行配置，其步骤如下。

(1) 首先对公交线网随机分配车辆数量。

(2) 然后对线路间的车辆进行调整，调整步骤如下。

① 依据客流需求、已经优化的线网布局及随机分配的车辆数量veh_ini，计算初始目标函数fit_ini，并将初始车辆分配记为最佳车辆分配方案veh_bes，将初始目标函数记为最佳目标函数fit_bes。

② 随机选择线路l_r1和线路l_r2。

③ 将线路l_r1的车辆配置数量转移1辆车到线路l_r2，并计算新的目标函数fit_new，如果目标函数fit_new＜fit_bes，则将转移之后的车辆分配方案作为veh_bes，将fit_new作为fit_bes，并返回步骤(2)，否则进入下一步。

(4) 是否达到停止条件。如果到达则输出最终车辆分配方案veh_bes以及目标函数为fit_bes，如果没有则返回Step 2，其中车辆分配停止条件时连续迭代P2代，目标函数不发生改变，即算法停止。

3 实际案例分析 3.1 案例数据及现有实际公交服务说明

(1) 数据说明

将本研究所提出的模型及算法应用到图 4的实际公交网络中^[15]，该网络为香港天水围区域的城乡实际公交线网，是典型的城乡公交线网案例。天水围区域为郊区聚集区域，有23个站点，分别标号为1~23，站点24~28为天水围区域所到达的5个城区站点，另外还有一个换乘站点T，该网络所有数据均依据文献[15]调查所得，另外站点平均停靠时间为1.5 min，网络中各线路配置的车辆总数为176 veh。根据假设条件中网络中hub的数量，结合实际网络规模大小及站点位置，通过K-means将天水围区域的站点分为3类，即hub数量为3。

(2) 现有公交服务说明

现有的公交线网布局如表 1所示，所有不能通过现有服务到达目的地的乘客需要在换乘站点T换乘，然后转由其他线路完成出行。根据文献[18]所获得的客流需求数据及站点间距离，在现有服务中，乘客出行总时间为1 578 830 min。

(3) 算法参数说明

在本案例中，Milk-run线路的局部搜索停止条件设置为：算法连续迭代50代，线路长度不发生变化时，停止Milk-run线路局部搜索，即P1=50，对于车辆分配的局部搜索停止条件设置为：算法连续迭代100代，目标函数不发生变化时，停止车辆分配局部搜索，即P2=100。需要说明的是，算法中P1和P2的参数取值都是根据测试结果进行的，将案例数据代入两个局部搜索程序中运行20次，然后依据其最优解出行的代数进行P1和P2的取值。

3.2 本模型的应用及分析

依据案例中的数据说明，结合文中模型及算法，采用Matlab语言实现算法编写，得到最终优化结果，如图 5和表 1所示，其中在图 5中，同一形状的站点表示聚类结果为同类站点，加粗站点表示一条Milk-run线路的hub站点。具体线路走向及车辆分配结果如表 1所示，线路标识为Ⅰ的表示Milk-run线路，线路标识为Ⅱ的表示hub到目的地的线路。

对其中3个hub站点，首先计算了郊区的23个站点之间任意两站点的距离，得到站点间的距离矩阵，然后代入Matlab中采用其自带的K-means命令，得到hub站点布局为4, 13, 21。

其中通过Milk-run线路及设置hub站点方式得到的线路运营方案中，该方式得到的乘客总体出行时间为1 512 495 min，相比于现有的出行方案出行时间1 578 830 min，减少了4.2%的出行时间。

3.3 优化结果分析

通过上述案例验证结果可知，对于城郊公交出行，采用Milk-run及hub站点设置能够有效减少乘客出行时间。其主要原因是：将站点聚类之后，能够有效形成规模优势，减少了乘客在中间站点停靠时间的消耗。

3.4 算法应用于大规模效率分析

本研究算法中hub站点的编码方式采用二进制变量，在确定hub站点之后，采用最短路判别方法对hub站点的归属站点进行了确定。启发式算法基本上都沿用了现有的成熟算法，且这些算法均在大规模网络中表现出较好的求解能力。为了验证本研究的启发式算法，对100站点的网络进行了Milk-run线路设置，数据包括100个站点间的最短距离，通过网络验证，说明该算法也能适应于较大规模网络的公交线网设计。

4 结论

本研究将物流领域的Milk-run及hub设置方法应用到城郊公交线网优化中，构建了相应的模型，并设计了针对该问题相应的求解算法。通过实际案例验证，说明该方法能够有效减少乘客出行时间。

本案例验证的是在原有车辆配置条件不变的情况下应用该方法的效果，因此实际操作过程中不需要额外增加车队规模，使其应用于实际更加便利。

通过该方法应用到大规模网络中，说明该方法也适应于大规模公交网络。

在公交出行过程中，乘客从出发地到目的地都必须经由hub站点进行换乘，在对城乡公交线网优化及设计过程中，应该重点考虑对Milk-run的运行车辆与hub站点到目的地的车辆换乘衔接问题，对hub站点的换乘设施进行配置及优化设计，提高换乘服务水平，从而提高整个公交系统的运营效率，这也是后续研究的一个方向。