基于改进自适应大邻域算法的公交线网规划方法

李光春，聂磊

(北京交通大学，交通运输学院，北京 100044)

0 引言

交通规划是保障城市公共交通发展的科学先导，而公交线网规划一直是其重要任务。合理选取公交站点和科学规划公交线网能提升城市公交服务水平，提高乘客绿色出行分担率，以及缓解交通拥堵等。

王炜[1]提出“逐条布线、优化成网”的公交线网规划方法，该方法实际可行性较强，是目前较为常用的公交线网布设方法之一。郭志勇等[2]提出“一路一线”的规划设想，该方法以直线道路规划公交线路，将公交线网与城市路网进行最大限度拟合。王佳等[3]提出建立公交骨架线路和公交接运线路的双层城市公交网络结构，建立并求解了双层优化模型。陈巍[4]等将线网规划和发车频率同步优化，提升线网服务效率。综合现有大量的理论与实践研究，公交线网设计问题主要分为以实际经验为主的设计，理想条件下的最优化设计和基于启发式算法的现实设计这3类[5]。

公交线网规划模型通常基于乘客出行需求和城市线网指标构建，近年来为契合城市规模扩张和公交服务转型，优化模型通常被分层考虑[6]。模型目标函数主要考虑：乘客出行时间[7]、出行换乘次数[8]、乘客时间成本与运营企业成本[9]、最大化乘客舒适度[10]、网络直达性与覆盖率等其他需求[11]。约束方面，通常需要结合实际情况考虑乘客需求、线网长度、服务效率、服务范围、接驳情况和非直线系数等规划要求。鉴于公交线网规划问题复杂度，精确算法求解规模受限，如遗传算法[12]、模拟退火算法[13]、禁忌搜索算法[14]、变邻域搜索算法[15]等启发式算法被用于该问题并表现出了较好的结果。但上述算法通常应用于数据集或小型实际案例，大型实际案例还鲜有较为高效的算法。

本文面向于求解公交线网规划实际大规模问题，提出一种乘客出行OD合并算法和基于自适应大邻域算法的公交线网规划方法。该方法考虑乘客路程距离将乘客出行OD进行合并，将公交线网分为主线和支线网络合理规划。在规划过程中考虑线网直达效率、线路长度、OD需求覆盖率和城市公交路网换乘情况等。所设计的改进自适应大邻域算法包括8种破坏/修复算子，同时设置自适应规则避免陷入局部最优。

1 乘客出行OD合并

线网规划问题是一个NP-hard 问题，问题复杂度较高，本文为实现计算实际较大规模城市案例，设计了一种两阶段算法首先对乘客出行OD 进行合并。该方法思路是将分散的乘客OD 按照空间距离合并至中心的需求节点，以实现公交备选站点的选取和城市路网骨架的构造。第1 阶段是交通小区(计算单元)的划分工作，交通小区是具有一定交通关联度和交通相似度的节点或连线的集合。参考交通小区划分规则，本文为合并乘客OD提出改进“路网切割，补充划分”的计算单元分割方法，算法流程如下。

第2阶段是在模块分割完成后，依次计算所有计算单元内部的合并中心点。该问题现实意义可理解为基于散布于区域中的乘客出行OD 如何有效设置公交站点。考虑到每个单元内节点数量较少，本文建立选址问题模型并使用Gurobi求解以获得中心点。对于所有单元内被合并点流量均归并至中心点，归并完成后删除所有被合并点。

2 主线及支线公交线网规划模型

2.1 模型假设及符号说明

本文问题是在给定乘客出行OD 需求、节点和节点间距离条件下，计算等同于预设线路集合N数量的由车辆站点k∈K构成的城市公交线网。其中，所设置任意线路n需要包含符合要求数量的站点k，站点间依次连接构成公交线路，所有公交线路共同构成公交线网。构建模型所需符号的说明如表1所示。

表1 符号说明Table 1 Notations

2.2 目标函数

目标函数为

总目标函数为

式(1)表示线网直达客流占路网总客流的比例；式(2)表示线网总长度与城市路网总长度的比值；式(3)表示线网覆盖的站点数量与站点总数之比；式(4)为总的目标函数。

2.3 约束条件

2.3.1 城市线网规划模型约束

其中，式(5)表示正反向连通性一致；式(6)表示同一线路中连通性一致；式(7)表示线路选中站点即为被服务站点；式(8)表示线路中节点的数量应与路段数量保持对应关系；式(9)和式(10)表示线路中任意节点只能有两个或一个相邻节点；式(11)和式(12)表示每条线路包含的节点数量应满足预设上下限；式(13)用以避免子环路的形成；式(14)表示每条线路的非直线系数应满足要求；式(15)用以判断节点i,j是否可互相直达；式(16)和式(17)表示线网的总长度满足预设上下限；式(18)～式(20)对决策变量进行定义。

2.3.2 支线模型更新

考虑到主线和支线网络在城市公交系统中功能定位和服务需求不同，其规划工作应存在一定差异性。本文所设计支线网络规划在完成主线规划的基础上进行，清除主线网络已服务的OD，该阶段更侧重于延展辐射的城市区域和满足主线线路间的换乘。支线模型做出如下修改。

(1)新增约束

每条支线至少与一条主线相连(有换乘节点)，即

(2)预设参数调整

对支线线路规划标准更新，如线路长度、节点数量、非直线系数、线网总长等约束按需求进行调整。

(3)目标函数权重调整

增加目标函数中节点覆盖率部分的权重。

3 改进自适应大邻域搜索算法

本文问题是一个NP-hard 问题，且考虑到城市实际乘客出行规模，选择自适应大邻域搜索算法求解。

3.1 编码结构与初始可行解

算法编码结构是设计元启发算法的先决条件，本文针对公交线网规划问题性质，选取自然数编码结构。为避免线路重复度过高、线路多样性不足和线路关联性较差等问题，本文在初始解生成阶段首先构建待选线路池。初始可行解生成方法如图1所示，其流程为：从全网随机选取一条边作为起始边，通过向两边合理延伸扩充线路站点，当生成达到一定长度或站点数后结束延展生成单条线路。若生成的线路满足单条线路要求，则将其加入线路池中。不断生成单条线路，当线路池所含线路数量达到预设规模后，从中选取一组预设数量的线路构成满足约束的解方案。

图1 初始解生成算法Fig.1 Initial solution generation algorithm

3.2 邻域构造

算法寻优效率通常和算子设置密切相关，一些现有元启发式算法算子缺乏与现实问题的契合性，本文结合公交线路特性，共设计8 种邻域算子，如图2所示。

图2 破坏算子和修复算子Fig.2 Destroy operators and repair operators

3.3 自适应规则

普通邻域搜索算法通常包含多种算子，但往往缺少不断更新的自适应机制，加入自适应规则能确保算子和当前解的适配度较高。本文设计自适应大邻域算法自适应规则如下。

(1)接受规则

当所得解优于当前最优解时，记录当前解为最优解。为避免陷入局部最优，本文设置80%概率接受一个较差解，其中较差解的定义为目标函数值大于等于0.8乘当前解的目标函数值的解。

(2)概率计算规则

(3)权重更新规则

定义权重为ψ，a和b表示上次迭代中的不同算子方法。若当前解为全局最优解，则ψ=2；若当前解优于记录解，则ψ=1；若当前解被记录，则ψ=0.5；若当前解不被记录，则ψ=0。权重更新公式为

3.4 算法流程

综上所述，本文设计算法整体流程如图3 所示。算法首先对原始路网数据使用节点合并算法缩减问题规模；其次将合并后节点作为备选站点输入，运用改进自适应大邻域算法计算缩减规模后的公交线网规划问题。在该问题计算过程中，第1阶段计算主线网络，第2阶段更新主线结果后计算支线网络，最终将结果进行汇总得到整体线网。

4 案例分析

为全面分析本文方法在线网规划中的应用效果，本文分别选取数据集案例和实际案例进行验证。案例均在一台搭载16 G内存和2.30 GHz i7-11800H CPU的笔记本电脑上完成。通过Windows 11环境下的Python3.9实现算法编写和案例计算。

4.1 公测数据集算例

本文选取Transportation Networks 数据集中的Sioux-falls 路网进行计算，该路网共24 个节点，76 条有向边，528 个OD 对(Sioux-falls 路网的具体细节可参考胡继华[16]的研究)。为更直观地进行算法层面对比，本文不对该路网进行节点合并且仅进行一次改进自适应大邻域算法，将所得结果与现有算法进行对比。图4 展示了算法迭代过程，表2 详细展示了计算结果。表3指标结果表明，本文改进自适应大邻域算法具有更高的直达率和更少的换乘次数，且不会出现二次换乘情况。

图4 Sioux-falls路网算法迭代图Fig.4 Sioux-falls network algorithm iteration

表2 Sioux-falls详细对比结果Table 2 Sioux-falls network detailed comparison

表3 Sioux-falls网络指标Table 3 Evaluating indicator of Sioux-falls network

4.2 邢台实际算例

为有效验证本文方法在现实中计算效果，本文选取邢台市进行验证，结合当地规章制度、实际路网情况和算法测试结果，参数标定如表4所示。

表4 参数设定Table 4 Parameters setting

本文所获原始数据为基于1372 个节点的乘客出行OD，设置合并距离上限φ=500 m，合并后站点所含发生交通量的上限β=10000 人，采用节点合并算法合并备选站点285 个。如图5(a)所示，大量散步节点被归纳至合并点，该情况在中心城区尤为明显。图5(b)将合并点以直径1 km画圆，合并点可有效辐射整个邢台城区，少有的未辐射区域为景区或大型设施等无法覆盖区域。同时，合并点覆盖重复率也较低，验证了本文OD合并算法的准确性。

图5 OD合并和覆盖情况示意图Fig.5 OD merging and coverage

表5 为邢台市实际计算结果指标，图6(a)为规划线网布局，图6(b)为线网客流覆盖热力图。如图表所示，本文所设计的公交线网规划方法对大规模实际问题具有良好的适用性，主要表现为以下两点。

图6 规划线网与道路和OD匹配示意图Fig.6 Network planning and matching condition of road and OD

表5 邢台线网评价指标Table 5 Evaluating indicator of Xingtai network

(1)整体网络覆盖率、服务率和服务效率均表现较高水平

整体网络站点覆盖率为78.94%，覆盖节点间的流量占所有节点间流量的84.67%，覆盖率较高。整体网络直达率为26.58%，一次换乘率为59.69%，超过80%的需求仅通过至多一次换乘即可满足，99.76%的出行需求可以在两次换乘以内实现，较好地满足了大部分居民的乘车需求。

(2)主线与支线规划合理

规划公交线路与城市路网匹配情况良好，主线百公里服务人次为3662.370，明显高于支线的747.299，大批客流通过主线线路运输，符合主线网络服务核心路段和OD 的设计目的。支线线路数为主线的2倍，但支线网络总长度为296774.31 km，与主线网络总长275817.00 km相差不大，符合设计短程支线接驳换乘的需求。此外，在主线网络站点覆盖率为45.6%的情况下，加入支线网络使整体覆盖率达到了78.94%，说明支线网络覆盖了较多主线网络未覆盖的节点，大幅提升了公交服务覆盖率。

5 结论

本文为解决实际公交线网规划问题提出了一套两阶段规划方法，其中，所设计的OD 合并算法能有效筛选公交站点和缩减问题计算规模；数学模型将城市公交线路分为主线和支线，分别以不同约束条件和参数设置体现其差异性；设计了一种对公交线网规划问题适配度较高的改进自适应大邻域搜索算法进行计算。通过公共数据集网络和邢台市数据进行案例分析，结果表明：本文自适应大邻域算法效果明显优于其他现有研究算法，主线和支线规划合理；该方法整体规划效果良好，线路服务水平较高。