基于改进蚁群算法的公交网络路径优化

武可心

(西安交通工程学院 交通运输学院，陕西 西安 710000)

0 引言

公交网络是城市重要交通系统之一，对社会经济发展和市民出行具有重要影响。传统的公交网络规划多采用整体重新规划，需要消耗大量人力物力，同时会对市民出行造成不便，并不适应于大中型城市的公交网络优化[1]。Pacheco等[2]提出了一种局部搜索和禁忌搜索策略的算法，以优化公交线路和车辆分配。Szeto等[3]结合遗传算法和领域搜索算法，建立了车辆频次和线路设计模型。Gambardella等[4]提出了一种直接修改线路方案的蚁群算法。Botee等[5]对α、β、ρ等参数进行了深入研究。本文将蚁群搜索算法应用于公交线路网络的优化问题上，同时改进惩罚机制，实验结果表明该方案能够明显提升公交网络性能，具有一定的研究意义和应用价值。

1 公交网络模型

Mandl道路网络是当前比较常用的典型道路网络模型之一，这里以该网络及站点客流OD数据为研究对象，分析公交线路网络优化问题。Mandl线路网络[6]如图1所示。共包含了15个公交站和22条线路，每段线路上的数据表示该段线路需要花耗的旅行时间。

图1 Mandl道路网络示意图

利用G=(N,A)模型描述Mandl道路网络，式中N表示公交站的集合，A表示连接公交站的线路集合。用OD表示客流量矩阵，其中odij代表在单位时间内第i个站点与第j

个站点间的乘客量，单位为：位/小时。乘客客流量矩阵OD可表示为式(1)。

OD={odij|i,j∈[1,2,3,…，N|}

(1)

在公交网络模型中，站点i到站点j的距离可表示lij，站点间的距离矩阵L可表示为式(2)。

L={lij|i,j∈[1,2,3,…，N|}

(2)

为了对公交线路网络的优劣进行定量评价，需要提出公交网络的评价函数，该网络的性能评价函数为式(3)。

(3)

约束条件如式(4)。

(4)

式中，l代表线路的长度；p代表线路的直达客流量，即乘客只需乘坐线路r就到达目的地的乘客数量；Z代表该线路的非直线系数；s.t.代表约束条件。

我们可以获得的已知数据包括公交站点集合N，客流量矩阵OD和站点间距离矩阵L。公交线路网络的目的是通过算法调整公交线路集合A，使得评价函数f的值达到最大。本文将蚁群算法引入到公交线路网络优化中，通过相应的改进与应用，从而实现对线路网络的优化问题。

2 蚁群搜索优化算法

蚁群算法是通过研究蚁群觅食行为，形成的一种群体智能优化算法。单只蚂蚁的行为看似简单且无规则，但蚁群群体却能在巢穴与食物之间的复杂线路中寻找出一条最优路线。蚁群搜索算法具有并行性、鲁棒性、正反馈性及良好的结合性等优势。将蚁群算法应用于实际的公交线路网络的优化问题，可有效提升公交系统的运行能力。基于蚁群算法的公交线路优化流程如图2所示。

图2 蚁群搜索算法流程图

其中，Gen表示公交线路迭代次数；size表示蚁群大小，acogen蚁群算法迭代次数。蚁群搜索算法主要内容包括线路调整规则、客流重新分配、信息素更新、惩罚机制等几方面内容。

2.1 线路调整规则

通过蚁群算法对每一条公交线路进行优化调整，首先将原有的公交路线作为蚁群算法的初始值，利用评价函数f生成初始的信息素，置于初始路径上，信息素[7]为式(5)。

(5)

式中，τ表示该线路段上的信息素值；f表示评价函数；ε表示加权常量。

然后，每只蚂蚁从起始站出发，利用信息素信息搜寻下一站，直到搜寻到达终点站。通过评价函数对搜寻到的新线路进行判断，假如搜寻获得的新线路优于当前的线路，则对当前线路进行更新替换。在线路搜索过程中，蚂蚁主要是基于信息素强度和启发式信息对下一站做出选择，第k只蚂蚁在站点i处选择下一站为j站的概率yij可表示为式(6)。

(6)

式中，τij表示信息素强度；ηij表示启发式信息；α和β分别表示信息素和启发式信息的影响因子；Tk表示第k个蚂蚁当前已经走过的站点集合。

2.2 客流重新分配

通过蚁群算法迭代出的一条新公交线路，将其替代原有公交线路，从而与原有的其他公交线路共同组成了一个新的公交网络。在对新的公交网络进行性能评价前，由于公交路线的改变，需要对网络中的客流量进行重新分配。公交网络进行客流重新分配后，再通过评价函数计算其函数值，才能真实反映出新公交网络的运行性能。

客流重新分配方法常用的有均衡分配和最短路径分配两种。其中，均衡分配方法具有较高质量的分配解，但不适应于大规模的道路网络。最短路径分配方法运行速度快，但忽略了公交线路的运载能力，假定公交路线的运载能力是无上限的，与实际情况不符。一辆公交车辆的运营能力为发车频次与标准载客量的乘积，本文采用最短路径分配法对OD矩阵中的客流量进行重新分配，并对最短路径中的每条线路进行了容量限制。分配方案流程图[8]如图3所示。

图3 客流分配流程图

2.3 信息素更新问题

信息素是蚁群个体间进行信息交流的重要信号，需要在蚁群完成路径搜索后进行更新。在进行信息素更新前，首先对蚁群搜索到的路线按照上节客流量重新分配流程进行客流的重新分配，进而利用评价函数计算函数值，依据新的评价函数值进行信息素的更新。

信息素的更新主要包括消退和加强两个部分[9]。消退是指模拟自然界的信息素特性，随时间蒸发减少每条线路的信息素强度。加强是指对蚁群经过的路径上的信息素进行加强。更新式如式(7)。

(7)

(8)

2.4 惩罚规则

公交网络模型中对线路提出了约束条件，若蚁群搜索过程中出现过多不符合约束条件的解，将会降低公交网络的运行性能。为抑制不符合约束条的解，引入了惩罚机制。主要对以下3种情况进行抑制。

(1)搜索路径出现回路；

(2)路径解的长度超出上限或下限；

(3)路径解超出非直线系数。

当出现以上情况，信息素更新后，对应受惩罚的路径进行信息素的额外削弱，削弱式[10]如式(9)。

(9)

式中，ρ表示信息素消减系数，通过调节系数的数值，可控制惩罚的强度。

3 实验结果

将Mandl道路网络作为实验对象，利用蚁群搜寻算法进行公交线路的优化，蚁群算法参数如表1所示。

表1 蚁群搜寻算法参数

公交线路优化调整前后的公交线路站点顺序如表2所示。

表2 公交线路站点顺序优化

对线路优化前后的评价指标进行统计，如表3所示。

表3 评价指标对比

表3为优化前后的评价指标对比。d0表示乘客直达目的地的占有率；d1表示乘客需换乘一次的占有率；d2表示乘客需要进行两次换乘的占有率；du表示公交路线不满意的占有率(即换乘大于2次或公交未能覆盖)。通过实验数据的对比可知，乘客的直达率由64.5%上升到84.7%，乘客的一次换乘率由22.8%下降至15.3%，乘客的不满意概率由12.6%下降至0%，公交网络的整体运行性能得到提升。

4 总结

本文将蚁群搜索算法应用于公交网络的优化问题，实现对公交网络的局部性调整及优化。设计了新型评价函数，并引入对不符合约束条件线路的惩罚规则，实验结果可知公交网络性能明显提升，验证了该方案的有效性。另外，可对线路调整规则问题进行更深入的研究，以进一步提升公交网络运行性能。