优化公交车调度的多目标遗传算法模型

张思维，魏昕怡，邱桃荣

(南昌大学a.际銮书院;b.信息工程学院，江西 南昌 330031)

公交车对社会影响巨大，对城市发展起着最基本的推动作用。公交车的站点布局、线路规划、车型配备、票价制定、发车频率和车辆调度反映了一个城市的管理水平，因此对公交调度的理论与应用研究具有相当的现实意义。与此同时，在我国公交优先发展和公交系统快速发展的政策背景下，通过对公交调度理论方法的研究可以有效提高城市公交系统的资源利用率，提高运营效率和服务品质。研究公交调度优化理论不仅是服务企业进行科学决策、提高资源利用率的需要、也是推进国家优先发展公交的战略。

然而，公交的客流量不仅具有周期性和趋势性，且易受天气、突发事件、相邻站点之间的相互作用等因素的影响，具有较强的随机性。目前国内外关于公交调度优化的理论研究已有不少的成果。例如，赵靖等[1]考虑需求了起讫点及需求等级对响应型社区公交行车调度进行优化；韩霜等[2]、陈深进等[3]对公交调度的即时性和实时性进行动态调度研究；ZHONG X W等[4]利用基于列生成的退火模拟、特征分析等算法对公交调度进行优化；刘星程等[5]提出一种基于云计算和实时数据的公交车实时调度算法。随着研究的深入，公交车的均衡满载率[6]、异质性出行需求[7]、自动驾驶[8]等因素也广泛被相关学者在公交调度领域进行理论研究。但这些算法的复杂度较高，且多利用居民出行调查数据进行验证，无法进行大规模实际应用。此前的研究并未考虑到由于人们的工作时间的不同导致公交出行出现的明显平高峰现象，公交调度的优化模型的鲁棒性有待提升。

近年来，遗传算法作为一种结构较为简单的算法，凭借其优秀的全局搜索能力、信息并行处理能力、鲁棒性等优点[9]，在许多计算机领域有广泛的应用。彭颖等[10]利用遗传算法对数据最大熵的概率分布进行计算，进一步拓宽了遗传算法的运用范围。姜婧等[11]将改进的遗传算法运用到排课问题中，提高了算法的运行效率。

随着公交硬件系统的更新换代，公交一卡通制度不断升级以及IC卡的使用率不断提升，使得IC数据的可信度大大提高。针对上述问题和背景，本文融合IC卡及GPS数据，考虑到公交客流量呈现的高峰期与平峰期趋势，提出一种基于车辆运行成本、乘客出行成本为目标函数的多目标遗传算法模型对城市公交调度进行优化，并验证其可靠性。

1 基于多目标遗传算法的公交车调度优化模型

1.1 公交车线路“高峰”和“平峰”定义

1.2.1 术语的定义

根据生活常识，高峰期和平峰期显然可以通过对比不同时间内准备乘车人数(包括最后是乘公交车及最后乘坐其他交通工具的人)来定义。考虑到给定时间内准备乘车的人数难以统计得到数据以及最初想乘公交最后乘坐其他交通工具的人占比较小，本文忽略最初想乘公交最后乘坐其他交通工具的人，只考虑乘坐公交车的人，并为了数据收集的方便考虑用每趟公交车的实际载客量相关量来定义。

由于时段发车时间间隔不同，比如高峰期发车时间间隔短，本文使用每趟车的实际载客量?除以该趟车发车到下趟车发车的间隔时间Δt这个量(即平均每小时载客人数φ)来定义平峰期和高峰期。即：

1.2.2 “高峰”和“平峰”定义的合理性验证

(1)验证数据集

考虑到公交的运行易受道路基础设施等外界因素的影响，本文选择了受外界影响力较小的武汉市某快速公交作为研究对象。公交线路全长20 km，从始发站到终点站共24个站点。站点分布较为均匀，基本上1 km内有一个站点。该公交的运营时间为5:30～23:00。同时该公交型号一致，按照国家相关标准每辆车荷载100人，开车速度不超过25 km/h。同时研究当天的发车时间间隔在15，4.5以及6 min不等。

(2)验证方法

本文统计出一天相应时间段(即每趟车发车到下趟车发车的时间段)的平均载客人数φi(i表示第i段时间)，为了排除偶然因素的影响，本文根据每段时间游客量得到载客人数的频率，并画出相应的频率分布直方图。根据该天公交的发车时间以及乘客人数计算出每段时间的平均载客人数φi。

通过曲线拟合可以得到一条较好的连续曲线。根据我们拟合出来的曲线，得出平均每小时载客人数的最大值M和最小值m，根据我们定义的系数s，t(0

·若某段时间平均每小时载客人数U≥m+(M-m)×t则视为高峰期。

·若某段时间平均每小时载客人数U≤m+(M-m)×s则视为平峰期。

(3)验证的结果与分析

根据本文所定义的平高峰模型，绘制出平均载客人数的频率分布直方图，如图1所示。并s=0.25，t=0.75，M=18.54人/min，m=2.88人/min。经过计算可知，高峰期为6:05～9:45，12:00～12:55，17:05～19:00。平峰期为10:00～11:30，14:45～16:30。其余时间段为过渡期。此结论与生活常识是一致的，因此可以认为本文之前指定的对“公交平高峰”定义是合理的。但本文发现φi拟合结果与客运量的结果不一致，在中午出现了小高峰现象。这可能与快速公交在中午的公交调度不合理导致，因此对快速公交的调度进行优化成为不可避免的问题。

time quantum/h

1.2 基于多目标遗传算法的公交调度优化模型

1.2.3 模型假设

为了给模型创造一个稳定的环境，保证建模的方便和数据的正确性，本文对实际情况作出以下假设：

(1)不考虑恶劣天气、汽车运行故障、堵车等多方面的外界因素对快速公交运行的影响；

(2)不考虑乘客上下车的时间，乘客均一次性上车。

(3)公交司机严格按照发车时刻表发车并准时到达各个站点。

(4)公交车以20km/h的速度行驶，不考虑公交车加速、拥堵或减速驾驶等因素。

(5)不考虑乘客在车内所产生的时间成本，乘客对公交服务的满意度仅仅以其平均等车时间来衡量。

(6)假设在一个发车时间间隔内，客流量服从正态分布。

(7)所拿到的公交运营数据真实可信，能够反映乘客的乘车时间、公交运行成本等运营关系。

1.2.4 多目标优化模型的构建

多目标优化是数学规划的一个分支。研究多于一个的目标函数在给定区域上的最优化。本文从公共交通和乘客出行两个方面的利益出发，考虑乘客的出行成本和公共交通的运行成本。考虑到不同的乘客由于个人原因会使得出行时间不一致，本文通过计算乘客在站等待时间作为乘客的出行成本；而公共交通的运行成本包括油费、人力劳务费等费用。将本文考虑的因素综合起来建立以乘客出行成本最小和公共交通的运行成本最小的公交调度优化模型。

(1)乘客出行成本

本文乘客出行成本由乘客在站等待时间量化表示：

式中,T等是乘客出行成本，s是公交车站点编号，n是公交车编号，ts,n表示编号为n的公交车到达站点s的时间，qs是到达s站点总客流。?(t;μ,σ,a,b)是车站s乘客出行需求的概率密度分布，其表达式如下：

式中，φξ是对数正态分布的概率密度函数，Φϑ是对数正态分布的累积分布函数，b、a是本文研究时间的始末点，φξ、Φϑ表达式如下：

(2)公共交通的运行成本

C=(n1c1+n1c1+…)L

式中，C表示线路所有车辆的运行的总成本，ni(i=1,2,3…)、ci(i=1,2,3…)分别表示从车辆编号和单位公共交通的运营成本，L表示公交路线长度。

(3)模型整合

本文分别以乘客出行成本最小和公共交通的运行成本最小为目标，构建公交调度优化模型，模型如下所示。

minC=(n1c1+n1c1+…)L

s.t.ωmin≤ts,n-ts,n-1≤ωmax

式中，ωmin、ωmax分别为最大发车间隔与最小发车间隔。

1.2.5 多目标遗传算法模型的构建

多目标优化是在现实各个领域中都普遍存在的问题，每个目标不可能都同时达到最优，必须各有权重。究竟要怎样分配权重，这已经成为人们研究的热点问题[12]。同时，根据生物进化论发展起来的遗传算法也得到了人们的关注。将这两者结合起来，能够利用遗传算法的全局搜索能力，避免传统的多目标优化方法在寻优过程中陷入局部最优解，可以使解个体保持多样性。其核心为遗传三算子，即选择、交叉和变异。

(1)编码方式

为了实现考虑公交客流“平高峰”期的公交调度优化，遗传算法的编码方式与以往的编码有所不同。染色体中的每一个基因代表一个最小时间间隔点，本文将其设置为1min，例如，如果研究时段为半小时则基因一共有30个。染色体上的基因为0表示平峰期不发车，基因为1表示在平峰期时段发车，基因为2表示高峰期不发车，基因为3表示在高峰时段发车，基因为4表示在过渡期时段不发车，基因为5表示在过渡期时段发车。

(2)初始化种群

根据高峰期和平峰期的定义可知，平高峰期是一个时间段，因此基于“高平峰”优化的染色体里的基因对于“高平峰”是连续的。根据本文之前定义的高平峰计算方法，一条染色体开始应该是连续的平(或高)峰期，再是连续的过渡时期，最后是连续的高(或平)峰期。

在实际的公共交通运营过程中，本文考虑到公交车长时间不发车情况为小概率事件。一般公交调度的发车间隔不会超过10min，本文除去了连续10个以上基因为“不发车”的染色体。

(3)选择、交叉、变异操作

选择操作是根据种群中的个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。在解码的基础上计算每个个体的序值和拥挤距离。本文通过序值前后进行选择，若序值相同则比较个体的拥挤距离。通过相应的选择方法对每个个体进行选择，保留满足条件的个体而淘汰不适应者，适者生存。并对保留下来的个体进行交叉、变异操作。

本文随机设置了多个交叉点以便对不同染色体中的基因片段进行交换[13]。交换遗传后，将更优秀的个体与父代个体进行非支配比较并放入下一代新种群中。通过对染色体的破坏和修复，将减小发车数和减少乘客在站等待时间作为变异操作。

(4)算法的设计

算法流程图下图2所示。

图2 算法流程图

3 实验结果与分析

由于提出的算法考虑到了“平高峰”，因此本文在设置研究时段时必须同时包含客流高峰期及平峰期。本文取某公交5:30～13:00时间段作为研究对象。为了统计的方便，我们每隔10min将研究时段划分成小阶段进行客流量的统计。本文根据研究时段内的客流特征，对客流的到达概率分布进行正态分布的拟合，拟合结果如下表1所示：

表1 拟合参数表

根据公交车调度情况，根据本文对染色体配置可知发车间隔为1min，即公交车将以1min、2min、3min等1min的倍数进行调度。根据本文对染色体初始化安排设定ωmin=1min，ωmax=10min。设定种群规模为60、迭代次数为100次、交叉概率设为0.8、变异概率设为0.025。

根据以上对数据的分析和参数的设定，我们可以对研究时段的公交调度进行优化计算，生成非支配解集；并对乘客总等待时间的计算结果(取中值进行研究)进行升序排列。得到公交调度时序图如下图3所示：

Time senes/min

4 模型分析与讨论

4.1 “平高峰”优化前后实验结果对比分析

本文算法的一大创新点便是将“平高峰”引入到算法多目标遗传算法模型当中，因此考虑“平高峰”前后优化对比是十分必要的。按照以往的多目标遗传的经典算法，不考虑“平高峰”时，染色体的基因编码方式有两种：基因为0为不发车、基因为1为发车。本文将两种优化前后的染色体基因序列分别进行测试，得到的结果如下表2所示。

表2 优化前后的成本对比结果表

通过测试我们可以清楚地看到优化前后的目标结果明显优于优化前。优化后的乘客出行时间比优化前的数据降低了13.75%，同时公共交通的运行成本也降低了1.7%。不管是对于乘客还是对公交公司，优化后的公交调度方案均比优化前的成本要低。这也从结果的角度说明本文的算法的优化能力更加强悍。

4.2 “平高峰”优化前后乘载率对比分析

为了进一步对比分析优化前后的公交调度情况，本文引入了乘载率，即一定时间内反映线路上运行车辆乘客满载程度的相对值。它是体现城市公交服务质量和水平的重要指标，也是公交营运调度部门编制营运作业计划以及进行现场调度的依据之一。乘载率被定义为乘客对公交车座位的占有率，即实际乘载人数与公交车辆座位数的比值。

本文对优化前后的乘载率进行计算后得到的结果如下图4所示。可以观察到“平高峰”优化前的模型的乘载率起伏较大，甚至有个别时间段的乘载率达到2以上。而优化后的乘载率更趋于平稳，且乘载率几乎收敛于1。

图4 优化前后的乘载率对比结果图

乘载率一定程度上反映了乘客的候车舒适度。由此可见，利用“平高峰”因素优化后的多目标遗传优化模型不仅减少了公共交通的运行成本和乘客平均等待时间，还大大增加了乘客的候车舒适度。

5 结语

实验结果表明，本文提出的基于“平高峰”因素的多目标遗传优化模型相比与传统的模型能够更好地对公交调度进行优化。测试结果表明，本文提出的优化模型不仅能够有效降低公交公司与乘客两方面的成本，还能提升乘客的候车舒适度。在今后的对公交公司决策优化公交调度具有一定的参考意义。本文将针对以下方面做进一步研究：本文的目标优化模型只考虑到了两个指标，可以利用两个以上指标展开讨论；进一步优化优化模型和数据处理方法，寻找优化能力更强的算法。