基于遗传算法的景区公交调度优化研究

林鑫 张海波 郑鳗芝

摘 要：在公交调度管理的过程中，公交运营方利益和乘客利益需要合理兼顾，而公交车发车间隔是公交调度优化的关键。本文以四川省成都市蒲江县樱桃山风景区为例，根据景区公交线路布局情况，以降低运营方运行成本、减少游客出行成本为优化目标建立目标函数，对公交运营成本和乘客等待成本进行合理的线性加权，求解最优公交发车时间间隔。最后，运用遗传算法进行求解，得到优化后的公交车在不同时间段的发车间隔。

关键词：公交调度;发车间隔;景区公交;遗传算法

中图分类号：U492.22;TP18 文献标识码：A 文章编号：1003-5168（2021）32-0010-03

Research on Optimization of Bus Dispatching in Scenic Spots Based on Genetic Algorithm

LIN Xin ZHANG Haibo ZHENG Manzhi

（Southwest Jiaotong University Hope College， Chengdu Sichuan 610400）

Abstract： In the process of bus dispatch management， the interests of bus operators and passengers need to be balanced， and the bus departure interval is the key to the optimization of bus dispatch. Taking the Cherry Mountain Scenic Spot in Pujiang County， Chengdu City as an example， according to the layout of the scenic bus routes， this paper takes reducing the operating cost of the operator and reducing the travel cost of tourists as the optimization objectives， and establishes an objective function， and applies reasonable linear weighting to the bus operating cost and passenger waiting cost， so as to solve the reasonable bus departure time interval. Finally， the genetic algorithm is used to solve the problem， obtaining the optimized bus departure interval in different time periods.

Keywords： bus dispatching;departure interval;scenic bus;genetic algorithm

为最大限度地吸引游客，提高景区服务质量，当前急需制定合理的公交调度方案。SCHEELES以乘客出行时间成本最小为目标，以车辆容量、客流分配为约束条件，建立以车辆发车频率为优化目标的非线性规划模型[1]。DORIGO等在研究公交线网问题时，以线路条件、道路条件、车辆运营时间为约束条件，建立了乘客出行OD矩阵的数学模型，以优化车辆发车频率[2]。FABIANC等在优化公交调度的过程中考虑了乘客的换乘时间，运用遗传算法解决了公交车发车频率问题[3]。国内学者也在相应问题上进行了大量研究。朱金寿等在建立多目标规划模型时考虑了公交公司的经济成本和乘客的出行成本，并用遗传算法对模型进行求解[4]。陈涛在大数据中挖掘乘客的出行规律，并结合影响公交调度的因素，建立公交调度优化模型进行求解[5]。

在模型求解算法的运用中，研究人员分别采用遗传算法、蚁群算法、模拟退火算法等对公交调度模型进行求解[6-8]。总之，以上研究都同时考虑了运营企业和乘客的利益，对城市公交调度方案进行优化。本文结合景区出行特点，借鉴传统公交的服务-需求关系建立多目标数学模型，运用遗传算法进行求解，最后对四川省成都市蒲江县樱桃山风景区公交发车频率提出了优化建议。

1 公交调度模型的建立

1.1 公交调度的概念

按照客流数据的实效性，公交调度可分为静态调度和动态调度。静态调度是指根据客流的历史分布规律，结合运营企业的运输能力，提前制定好公交调度方案，包括车辆发车间隔、车辆运用计划以及工作人员排班表等。动态调度是指利用现代技术手段获得客流分布的动态变化情况，在事先制定好的调度方案基础上，实时调整调度方案，以合理安排不同情况下的车辆发车频率、车辆运用计划，属于静态计划的补充。本文从静态调度的角度出发，对公交发车频率进行优化。

1.2 模型的建立

1.2.1 模型假设。在实际的公交运营管理过程中，多种因素会影响公交运营。为简化研究过程，在建立调度优化模型的过程中，要对诸多外部因素加以约束。因此，本研究做出如下假设：公交车辆所有车型相同，即运载能力相同;所有车辆逢站即停，不允许超车;在运营各时间段内，乘客到达站点服从均匀分布;车辆匀速运行，运行时间包括停站时间;投入运营车辆足够;同运营时段内发车间隔相同;乘客只用等待第一班到达车辆即可上车;车辆单位里程运营成本保持不变;所有乘客出行成本相同。

1.2.2 变量定义。把景区运营时间分为I个时间段，时间段的集合为I={1，2，…，i，…}，i表示第i个时间段。第i个时间段的时长为t，第i个时间段車辆的发车间隔为Δt。S为景区公交运营路段的总长度，r为公交车单位里程的运营成本。J代表站点的总数，站点数的集合为J={1，2，…，j，…}，j表示第j个站点。第i个时间段的客流量为vi，第i个时间段内平均每分钟到达j站点的游客数量为v。第i个时间段内发车时间最大间隔为Δt，最小间隔为Δt。游客候车的单位时间价值为e，单位为元/min，公交车的额定载客量为C。

1.2.3 模型建立。设游客的出行成本为N，企业的运营成本为M。单位时间的游客出行成本计算公式为：

假设游客到达站点服从均匀分布，则第i时间段游客的平均候车时间为Δt/2。一个运营日内所有游客的出行总成本为：

运营公司在一个运营日内的总发车次数为：

一天的总运营成本为：

1.2.4 目标函数。调整车辆发车间隔主要考虑两个因素，一是运营公司的运营成本，二是乘客的出行成本。但是，这两个因素对车辆发车时间间隔的影响是对立的。所以，在同时考虑两个因素的情况下，要引入加权系数λ和λ。对多目标问题加权合并，将其转换成单一目标函数：

1.2.5 约束条件。考虑景区服务质量，车辆空间利用可以适当宽松，但不能过于拥挤，即满足式（6）约束条件;车辆发车时间间隔应有约束范围，以保障运营公司和乘客的利益，即满足式（7）约束条件;为保障运营公司的经济利益，要限制运营公司的运营成本，即满足式（8）约束条件。

2 遗传算法求解过程

2.1 编码

本文对变量采用二进制编码（0，1）。在定义染色体长度时，要考虑时间段划分、最小发车时间间隔和最大发车时间间隔。一天的运营时间段数为I，染色体的长度为4I。设定发车时间间隔最小为1 min，最大为8 min，即区间长度为8。不同时间段内发车时间间隔为一个3位数的二进制数。

2.2 初始种群

在产生初始种群的过程中，采用随机挑选的办法，在随机产生的数个个体中选择出最好的个体加入初始种群，并且不断重复这个过程，直到达到目标种群规模，选择出含有X个个体、染色体长度为4I的二进制数。

2.3 适应度评价

根据适应度计算函数计算出不同个体的适应度，选择适应度大的个体投入下一次的遗传过程。在计算过程中，为进行适应度值的比较，一般其适应度值取正值。引入一个适当的适应度最大值Z，将目标函数转换为适应度函数：

2.4 算子

2.4.1 选择算子。算子交叉过程中，原始个体不断交叉复制。在此过程中，对个体中的部分基因加以改变，从而产生新的个体。通过比较不同个体适应度值的大小，选择适应度高的个体，舍弃适应度低的个体。

2.4.2 交叉算子。在选择算子得到的种群中，随机选择两个个体进行交叉运算。设定交叉率为0.8，根据交叉率判断是否执行交叉。若不需要，则直接将个体纳入新的种群;若需要，则执行单点交叉，直到交叉次数达到设定的最大值，从而得出新的个体纳入种群。

2.4.3 变异算子。在交叉算子得到的种群中，随机选择个体，设定变异率为0.01，根据变异率判断是否执行变异。若不需要，则直接将个体纳入新的种群;若需要，则随机选择点位进行变异，直到满足约束条件或达到设定的最大变异次数，从而得到新的个体纳入种群。

2.4.4 终止计算。在变异运算得到的种群中，按适应度值进行比较，淘汰掉适应度值较低的个体，从上一代群体中选取适应度值较高的个体进行替代，从而产生新的种群，直到达到设定的运算次数。

3 案例分析

3.1 运营线路基本信息

本文针对成都市蒲江县樱桃山风景区旅游公交进行调度优化。该旅游线路全长为10 km，共设18个站点，固定发车间隔为5 min，统一票价为5元/人。选取樱桃节期间（4—5月）的一个周六作为研究时段进行静态优化。把一天的运营时段分为6段，分别为08：00—09：00、09：00—10：00、10：00—11：00、11：00—15：00、15：00—16：00、16：00—18：00，时间长度分别为60 min、60 min、60 min、240 min、60 min和120 min。6个时段的客流量分别为1 127人、1 221人、1 437人、6 325人、1 021人和904人，发车间隔最大分别为4 min、4 min、4 min、8 min、4 min和6 min，最小发车时间间隔均为1 min。公交车额定载客人数为60人，公交车单位运营成本为6.4元/km。

3.2 参数设置

遗传算法中设置的参数值为：交叉概率P=0.8，变异概率P=0.05，种群规模K=80，迭代次数G=500次。在运营公司利益和游客利益的权重选择上，以λ+λ=1为前提，倾向于考虑企业利益时，取λ=0.6，λ=0.4;在倾向于乘客方利益时，取λ=0.4，λ=0.6。

3.3 计算结果

当λ=0.6，λ=0.4时，各时间段内的发车间隔分别为3.5 min、3.1 min、2.9 min、5.9 min、3.2 min和4.3 min;当λ=0.4，λ=0.6时，各时段的发车间隔为3.2 min、2.3 min、2.0 min、4.2 min、2.6 min和3.3 min。在实际调度方案的制定中，可根据调度目标选择固定的权重系数，也可在不同时段内选择不同的权重系数。例如，在客流低谷期，可侧重于运营企业利益，选择λ=0.6、λ=0.4制定方案;在客流高峰期，可侧重于乘客利益，选择λ=0.4、λ=0.6制定方案。

4 结语

考量乘客的出行成本与运营公司的经营成本，建立綜合的非线性规划模型。该规划模型的优化目标为车辆的发车时间间隔，同时考虑了运营公司和游客双方的经济成本。最后，利用遗传算法求解最优解，得出最合适的发车时间间隔。

参考文献：

[1]SCHEELE S.A supply model for public transit service[J].Transportation Research Part B：Methodological，1980（12）：133-146.

[2]DORIGO M，MANIEZZO V，COLORNI A.The ant system：Optimization by a colony of a cooperating agent[J].IEEE Transactions on SMC，1996（1）：28-41.

[3]FABIAN C，ZHAO F.A genetic algorithm for bus schedule synchronization [J].American Association of Textile Technology，2006（13）：737-742.

[4]朱金寿，朱琪，杨勇刚.遗传算法在公交车调度优化中的应用[J].交通与计算机，2002（3）：62-64.

[5]陈涛.基于大数据和混合启发式算法的公交调度方法[D].杭州：杭州电子科技大学，2016：17-18.

[6]韦尚成.临界-遗传算法在公交调度中的应用[J].物流科技，2017（5）：101-106.

[7]任晓莉.基于禁忌搜索的智能公交调度研究[J].测控技术，2014（2）：124-126.

[8]蔡光跃.遗传算法和蚁群算法在求解TSP问题上的对比分析[J].计算机工程与应用，2007（10）：96-98.