基于改进遗传算法的公交调度优化设计

陶烨

摘 要：针对公交线路，研究制定出合理的公交车调度机制，对乘客和公交公司双方的利益都有非常重要的现实意义和价值。本文拉萨市一公交线路为例，根据其日均客流情况，建立以公交公司运营成本最小和乘客利益损失最低为目标的公交调度优化模型，并通过改进遗传算法对其进行求解，得到最优公交运营时间间隔和公交车配车数量。研究结果表明，采用优化后的公交调度机制，并用改进后的遗传算法求解，可以有效提升公交公司运营效率和乘客满意度。

关键词：遗传算法 公交调度 优化设计

长期以来，我国许多城市公交企业主要依靠管理者的经验和制定公交运营计划者的直觉，导致公交运营水平和服务质量低下，从而影响公共交通出行比例和公共交通企业的经济效益。因此，对公交调度的研究可以为现代公共交通提供技术支持和服务保障，实现公交调度运行的高效、高效，提供准时、快捷、舒适的服务，提高公共交通的吸引力，提高企业经济效益，促进居民出行。

国外学者Avila-TorresP等[1]对周期同步次数与运营成本构建双目标模糊规划模型，采用需求水平、置信度和模糊三个指标对模型进行评价，结果验证模型有效性。Sharaf AK等[2]开发了针对一般问题的整数线性规划模型，确定了最优的发车车次。国内学者尹诗德[3]以发车间隔为自变量建立公交调度模型运用混合布谷鸟算法进行求解，为求解公交调度问题提供了一种新思路。李欣然等[4]以乘客平均等待时间最小为目标建立优化模型运用粒子群算法进行优化，结果证明该算法能有效解决问题。杨海荣[5]考虑乘客费用和运营商成本建立优化模型最后用遗传模拟退火求解。丁勇等[6]以乘客费用以及社会效益为目标建立了优化模型运用遗传算法求解，结果证明拥有积极意义。任传祥等[7]以乘客时间和企业成本为目标，建立优化模型并用改进的遗传禁忌搜索算法进行求解，结果证明效率比传统求解方法高。

1 数学模型的建立

1.1 模型假设

公交调度的数学模型主要是对实际公交调度问题的抽象和概括，因此不可能充分考虑所有复杂的外部因素，必须对外部因素进行合理限制。公交调度模型具有复杂、受多种外部因素影响的特点。本文做出以下假设：

本文的研究对象是拉萨某一公交线路，发车不考虑重复路线忽视客流客观原因造成的统计误差;公交车辆为同一车型，且公交车运行情况良好;乘客到达站点数量服从均匀分布;公交车只运行一条公交线路上，且只考虑单程车运行;单位时间内乘客消耗的费用是固定的;单位乘次公交车消耗的成本是固定的。

1.2 目标函数及约束条件

在现实公交调度中，公交车调度优化模型的目标函数需要考虑两个方面，从乘客的角度需要最大程度上减少乘客因等车所消耗的费用损失增加发车次数。另一方面需要最大程度上減少公交公司的运营成本减少发车次数。以此为目标建立模型。

Pkj=ukj/Tk

mk=tk/Δtk

1.2.1 乘客费用损失

通过查阅国内相关文献发现前人在建立目标函数时，会以所有乘客的费用损失建立目标函数，本文以平均费用损失建立目标函数，以保证每位乘客在等车时都能够降低费用损失，其稳定性较之前者更高。

1.2.2 营运成本W2

公交公司的营运成本可表示为线路总发车次数与单位次数营运成本积的形式：

那么目标函数为：

Wmin=W1+W2

为了建立易于求解的优化模型。我们将该公交该线路的发车时段分为高峰时段和平峰时段。其中：

那么一天的费用损失函数F

F=min（F1+F2）

以满载率不低于60%为约束条件

以上数学模型中符号说明如下表1所示：

2 遗传算法的设计

2.1 操作算子改进

复制：在运营商选择方面，通过“优胜劣汰”的复制操作，引导集团向适应环境的方向发展。在迭代初期，整个搜索空间分布着群体中的每个个体。这时，优秀的个体在整个搜索空间中所占的比例很小，所以这个时候的选择机制应是宽松的。随着迭代的进行，在迭代的后期，优秀个体在搜索空间中占有很大比例，选择机制应严格，从中选出最优秀的个体。单一的选择机制是不合理的，应该随着遗传迭代来改变。本文首先计算个体适应度值。采用轮盘赌法执行选择过程，然后利用精英保留政策保留。即从优秀个体中除去遗传过程而直接从父代复制到子代。轮盘赌算法公式：

自适应交叉、变异：

为了增加种群的多样性以避免早熟的现象发生，较大的交叉率很好的丰富了种群的多样性，但是随着迭代次数的增多，种群逐渐向最优解靠近此时若再次采用较大的交叉率、变异率。又增加了新的个体分布在最优解的周围。降低了最优解在搜索空间中的比重延缓了收敛进程。所以交叉率、变异率前期应大后期应小，是自适应变化的。

崔珊珊[8]在设计自适应交叉率和变异率时，主要考虑平均适应值和迭代次数。

PC=PC0+（PC0-PCmin）*

pm=

pm=（pm0-（pm0-pmmin）*+pm0*）/2

其中：Pm1与遗传进化代数成反比关系，随着遗传进化代数的增加，Pm1的值减小;Pm2与群体平均适应值的好坏有关系，群体平均适应值越好，Pm2的值越小，见图1。

通过工具MATLAB并利用遗传算法求解TSP商旅问题，输出其当前最优值以及当前平均目标值的线性图，图中可看出在前二十次迭代过程中，当前最优值与平均最优值的下降速度几乎相同，在迭代20次以后平均最优值呈现稳态分布而最优值呈现缓慢下降趋势。由此可得，以当前最优值与平均作为参考是不合理的。改进如下：

本文引入理想状态下目函数最大适应度设为1，为将约束在（0 ，1）内采用倒数形式，已知互成倒数的两个数线性关系呈反比，同时我们要求变异率随着迭代逐渐减小。因此最终以作为参考。这样更好的保证了自适应变异率与迭代过程的联系。同时引入王倩[9]等，用四分位间距替换自适应交叉和变异概率中的固定参数。

改进遗传算法流程如图2：

3 实例分析

本研究以拉萨市某一公交线路为研究对象，对该线路发车时刻表进行优化。如图3所示是该线路每日的平均客流变化情况。

这里我们将公交车一天的运行时间分为 9 个时段，又考虑到，公交发车一天内的发车间隔在个时段内不会频繁更换，将该线路一天的发车时段用高峰时段、平峰时段进行标记，如表2所示。高峰时段的划分为：7：30-8：30，12：00-12：30，14：00-14：30，17：30-18：30，总3个小时。平峰时段的划分为：6：30-7：30、8：30-12：00、12：30-14：00、14：30-17：30、18：30-21：30，总12个小时，见表2。

根据建立的公交优化数学模型，采用改进过后的遗传算法进行实例仿真。主要参数出发间隔的变化间隔[5，30]，该值为0.5的整数倍。初始种群大小n=30，交叉概率PC=0.89，变异概率PM=0.01，最大迭代次数g=220。迭代次数权重系数0.6，平均适应度权重系数0.4。高峰时段成本损失的权重系数是0.6，平峰时段0.4，高峰时段到达率0.88，平峰时段0.65，高峰时段公交公司的成本消耗的加权系数是0.7，高峰时段乘客的成本损失的加权系数是0.3。平峰时段公交公司费用消耗的加权系数是0.6，平峰时段乘客登车的费用损失加权系数0.4。

最后通过仿真得到了拉萨市公交的最佳发车时间间隔。高峰时段的最佳发车时间间隔为9.4分钟，平峰时段的最佳发车时间间隔为16.4分钟。考虑到实际时间间隔通常是5的倍数，和每日计划不会改变，最终获得最优出发时间间隔，发车间隔10分钟在高峰时间20分钟在高峰时间，所以发车车次56次、平均满座率80%，公司运营成本节约20%，乘客满意度提高30%。

4 结语

本文對拉萨市某公交线路的公交调度进行了研究，建立了该线路公交调度优化的数学模型，利用改进后的遗传算法得到了该线公交调度的最优发车时间间隔和最优公交调度数量。数据表明，优化后的公交调度机制可以提高乘客满意度，有效降低公交成本。本文建立的公交调度优化数学模型对于其他线路的公交调度也有一定的积极意义。

参考文献：

[1]Paulinavila-Torres，Fernando López-Irarragorri，Caballero R， et al. The multimodal and multiperiod urban transportation integrated timetable construction problem with demand uncertainty[J]. Journal of Industrial and Management Optimization（JIMO），2018，14（2）：447-472.

[2]Sharaf A K，Fahad A R，Areej Z.Optimal bus frequency for Kuwait public transportation company：A cost view[J].Sustainable Cities and Society，2018，41：312-319.

[3]尹诗德.基于模拟退火的混合布谷鸟算法求解公交调度问题.2018.华南理工大学，MA thesis.

[4]李欣然，and 靳雁霞."量子行为粒子群优化算法在公交调度优化中的应用." 计算机系统应用 21.07（2012）：191-195. doi：CNKI：SUN：XTYY.0.2012-07-045.

[5]杨海荣.“基于改进遗传算法的公交车辆调度优化.”长沙理工大学学报（自然科学版）6.02（2009）：13-17. doi：CNKI：SUN：HNQG.0.2009-02-004.

[6]丁勇，姜枫，and武玉艳.“遗传算法在公交调度中的应用.”计算机科学43.S2（2016）：601-603.doi：CNKI：SUN：JSJA.0.2016-S2-136.

[7]任传祥，郇宜军，and 尹唱唱.“基于遗传禁忌搜索算法的公交调度研究.”山东科技大学学报（自然科学版）.04（2008）：53-56.doi：10.16452/j.cnki.sdkjzk.2008.04.015.

[8]崔珊珊.遗传算法的一些改进及其应用[D].中国科学技术大学，2010.

[9]王倩，李风军.改进的自适应遗传算法及应用[J/OL].重庆师范大学学报（自然科学版）：1-8[2021-05-13].