临界―遗传算法在公交调度中的应用

摘 要：随着我国交通问题日益不平衡，为了缓解交通压力，研究公交车调度问题很有必要。针对公交车辆调度的现状，通过分析乘客出行的舒适度以及公交车的满载情况定义了乘车感知波动价格。结合实际建立了乘客最小乘车费用以及公交公司最小总耗费为目标的一个综合优化模型；并引入拥堵弹性因子，分析了它对发车间隔的影响。同时针对传统遗传法的局限性以及收敛速度慢等缺陷，通过个体的相似度与父辈相似度的临界值相比较，动态调整变异时间和控制变异概率的方式对遗传算法进行改进。最后应用临界―遗传算法（C-GA）和简单―遗传算法（S-GA）分别对上述优化模型进行求解，通过实例证明了该算法在收敛速度和结果都优于简单遗传算法。

关键词：城市交通；调度优化；感知波动价格；临界―遗传算法；公交车；博弈

中图分类号：F570 文献标识码：A

Abstract： With traffic's problems is increasingly unbalanced in China， it is necessary to study on bus scheduling problem（BSP）for solving traffic pressure. According to the present situation in the scheduling of bus， considering the comfort' degree of passengers and condition of bus's guests are analyzed to identify the perceived fluctuation-price combined with the actual， an integrated optimizing model is established based on minimize trip cost of passengers and the minimize total cost of bus company and congestion flexibility factors are introduced to analysis it influence on the bus departure time interval； putting a way of dynamic adjust variation's time-based critical value and control variation's probability are improved in the paper to overcome limitation and slow convergence speed of traditional genetic algorithm at the same time and then adopting criticality-genetic algorithm（C-GA）and simple-genetic algorithm（S-GA）to solve BSP model， experiments shows that C-GA is better than S-GA in the speed of convergence and results.

Key words： urban traffic； scheduling and optimization； perceived fluctuation-price； criticality-genetic algorithm； bus； game

0 引 言

S着我国社会经济的快速发展，我国机动车保有量逐年增加，交通问题日益严重，用有限的道路面积承担尽可能多的出行是解决城市交通问题的有效途径，为此如何有效地调度公交车运行是其很重要的环节。大量国内外的学者从不同的角度对公交调度进行了研究，1993年，Malacly Carev[1]对公交车的非准点到站的分布以及不同发车间隔下乘客的到达分布进行研究，然而现在公交车发车往往限制于单位时段内固定发车频率。1998年，Paolo Delle Site等[2]研究了客运走廊上的公交调度优化模型。2011年，王超、徐猛[3]在Ceder[4]4种确定发车时间间隔的基础上，考虑了道路拥堵情况下对公交车发车间隔做了研究等。也有学者根据算法的不同对公交模型优化做了相关研究，2004年，童刚[5]以乘客和公交公司总效益最大为调度目标，建立了公交运营参数模型，通过遗传算法进行了求解，但是公交作为公益性设施，在运营中不应该是简单加权。2009年，郑小花、陈淑燕等[6]采用模拟退火算法，以乘客候车时间最小为优化目标的调度模型，而公交在运营中企业效应应该着重表现。2014年，崔明月、黄荣杰等[7]通过量子遗传算法对公交车辆调度进行了优化。2015年，马雁、王非等[8]通过改进遗传算法对公交车调度模型进行了优化。

公交车的调度问题是APTS中最重要的一环，其主要功能是实现公交车辆的自动调度与指挥[9]；实际出行过程中，乘客上下车的时间消耗也占据着很大的比例，尤其对于短途行驶的乘客。本文通过定义乘客出行感知波动函数，以公交公司总利益最大化、乘客等待时间最小化为优化目标，从实际出发，建立了相应的公交车调度优化模型，通过改进遗传算法进行求解；同时引入拥堵弹性因子，研究了路段处于拥堵状态下的公交车调度，通过实例说明拥堵弹性因子对发车间隔产生了很大的影响，以及算法的优效性。

1 公交调度优化数学模型的建立

对于特定的公交路线，影响公交调度模式和相关方案选择的因素主要表现在乘客和公交公司的利益之间的博弈，公交公司总希望发车间隔尽量的大，以此来减少班次数，保持其可变成本尽量低，而乘客却是希望获得较小的发车间隔以至于达到出行方便。二者博弈的结果就是要求调度方案尽可能地在二者之间寻找纳什均衡点。本文以此为目的，建立了如下的数学优化模型。

为了简化模型，现提出如下假设：（1）在某一个时间段内，车辆只能沿着规定的路线行驶；（2）公交车不准等客；（3）每辆公交车发车频率不受到乘客多少的影响并且相等；（4）所有到站乘客只能通过选择公交车作为其出行方式；（5）有足够的公交车供调度使用；（6）站点均匀分布；（7）在不考虑公交专用道下，相邻站点公交车行驶的过程中，行驶时间只与路段是否拥挤有关；（8）只考虑单向行驶。

符号、变量、常量的说明如下：

车站集：I=1，2，3，…，N同时表示共有N个车站（注：文中i-1仅表示i的前一站，无任何数值比较）；

车辆集：J=1，2，3，…，K同时表示可供调度的公交车共有K辆（注：文中j-1仅表示j的前一辆车，没有任何数值比较）；

t■■表示第j辆公交车到达第i站的时刻经适当转化后用于比较的实数；

s■■表示第j辆公交车从第i站的发车时刻经适当转化后用于比较的实数；

π■表单位乘客候车费用（元/人）；

π■表单位乘客坐车费用（元/人）；

λ■表示乘客在第i站的下车率（%）；

ρ■表示乘客到达第i站的到达率（%）；

T■■表示第j辆公交车在第i站最大停车时间（min）；

T■■表示第j辆公交车在第i站最小停车时间（min）；

H■表示最大车头时距；

x■为第j辆公交车从i站出发时的载客量（人）；

B为公交车定员（人）。

建立优化模型如下：

记∏■为乘客候车费用，则：

∏■？芪π■・■■t■-s■ρ■・t■-s■ （1）

其中：t■-s■表示乘客候车时间。

记∏■为乘客车内费用，其时间消耗主要由三部分组成，第一部分为所有乘客在公交车行驶时的耗时t■，第二部分为所有乘客上车的时间消耗t■，第三部分为所有乘客下车阶段的时间消耗t■。

t■=■x■・t■-s■ （2）

t■=■■■■・ρ■・s■-s■ （3）

t■=■■■・λ■・x■ （4）

其中：■表示单位乘客平均上车时间（min/人）；■表示单位乘客平均下车时间（min/人）；t■-s■表示列车运行时间；s■-s■表示前后两车的车头时距。

定义乘车感知波动价格δ■，即乘客出行中若乘车过度拥挤或者未能达到公交公司规定的满载率所承担的额外费用，据研究统计得δ■与乘客人数x■之间函数关系如下：

δ■x■=■ （5）

式中：ζ为公交公司规定乘客数未能达到平均满载率时的惩罚系数，ζ>1，ω为满载率，即如若当次乘客数量未达及公交公司规定最小乘客数ω・B时，则会收取额外的费用ζ-1・π■；θ为乘客波动系数，θB时，由于拥挤则会受到惩罚，多支付η-1π■；通过数据验证，可得下式：

η=maxx■/B； i∈I， j∈J （6）

则乘客下车阶段产生的广义费用：

∏■=π■・x■・1-ρ■・t■+t■+δ■x■・t■ （7）

则乘客出行的广义费用∏■表示为：

∏■=∏■+∏■+∏■ （8）

记∏■为公交公司可变费用，则：

∏■=■■∏・t■-s■ （9）

其中：∏表示公交车可变运营费用（元）。

由以上分析可建立以公交车每时段发车时间间隔为内生变量的数学优化模型：

minα∏■+1-α∏■

s.t.■ ？坌i，j （10）

其中：α乘客出行广义费用所占的权重系数；s■-t■表示为第j车在第i站停车的时间。

2 公交调度优化模型的求解

遗传算法（GA）于J.Holland教授等人⒎⑻岢龅[10]，是一种优秀的全局搜索算法，但遗传算法局部搜索能力很差，很容易出现早熟现象，对新的基因结构的产生具有局限性，从而导致遗传算法的收敛效果并不理想；交叉和变异算子是遗传算法中最重要的操作算子，交叉操作对于保证遗传算法寻优过程收敛到全局最优，以及提高寻优过程的收敛速度，都起着重要的作用；而变异操作则使种群保持一定的多样性[11]。本文通过临界值动态控制交叉顺序及调整变异概率，对传统的遗传算法做了改进，通过对公交调度模型的求解，验证了算法的更优性。

2.1 约束条件的处理

为了使算法具有自适应能力，现在采用惩罚策略对约束条件进行处理，假定μ■， μ■， μ■为式（11）中各约束条件的边际效用（罚函数作用强度的系数），则：

minLΔ■，s■，μ■，μ■，μ■？芪min∏■+∏■+μ■・■max0，s■-t■-T■■+μ■・■max0，T■■-s■-t■+μ■・■max0，s■-s■-H■（11）

2.2 染色体的编码

根据本文模型特点，采用二进制编码；根据统计，假设取发车间隔的值域为Δt|Δt=2，3，4，…，15，即：Δt■=2，Δt■=15；Δt由于Δt是满足2≤Δt≤15的14个整数，而且2■

2.3 初始化

随机确定L个染色体为初始种群，并根据Δt的约束范围2，15，选择初始种群的时候剔除无效的染色体；记种群集：■

=α■，α■，…，α■，…，α■，…，α■。

2.4 参数选择

遗传算法中，需确定相应的交叉概率p■以及初始变异概率p■。

2.5 适值计算

适应度的作用在于评价个体的优劣程度，适应度越大，个体则就越好，同时个体则有更多的机率遗传繁殖到下一代，反之则反。故而遗传算法要求适值非负，通过式（12）将最小的目标根据适值非负原则将其转化为求解目标最大值的形式。

f■=■ （12）

式中：z■为一较大的特定输入值；z■为个体f■对应的可行解。

计算中发现：易证明fx=e■ω・B≤x≤B为凸函数。当x■B时，波动率呈现指数级增长。从而导致的波动率差异过大，同时考虑到线性函数增长的平稳性以及大大降低求解难度，现将此凸费用函数用分段，线性规划近似，取ω・B，B的中点作为段点：则处理后的凸费用如图1所示：

以各段线性函数的梯度作为权重，则式（5）转化为：

δ■x■=■ （13）

将δ■x■代入式（7）中即可。

2.6 遗传产生后代操作

（1）复制

本文采用赌选择，即个体适值越大，则被选中的概率就越高，那么该个体被复制至下一代的机率也就越大，反之则反，个体被选择的概率由式（14）计算：

P■f■=gf■/∑gf■ （14）

其中：P■f■为选择概率；gf■为个体f■的适值。

（2）交叉操作

交叉就是通过原则产生一组新的染色体（解）的过程。变异算子在遗传算法中的主要作用就是使得种群保持一定的多样性。本文通过采用父辈临界值来控制变异时间，操作为首先划分出优良种群，进行多父辈POX交叉[12]，并且从中选择最优的两个父个体，但是不同于以往的是这两个父个体不直接放入子代种群，而是将这两父个体的相似度与父辈相似度的临界值作比较。

定义0-1变量：

θα，k=S■■-S■■=■ （15）

其中：S■■和S■■为两个体对应染色体α■和α■中的第k个基因，若k为相同的等位基因，tθα，k为1，否则为0。

于是父个体相似度C■：

C■？芾■■θα，xdx （16）

父辈相似度的临界值S■：

S■=■ （17）

其中：d■和d■分别表示染色体α■和α■上的第k个基因；L为种群大小。

如若C■≤S■，那么将这α■和α■放入到子代种群中，否则为了有效地避免近亲繁殖，则先对次优的父个体通过一次或者几次的突变，这样则即降低了父个体之间的相似度，同时又保留了优良个体，迭代至与最优父个体相似度C■'≤S■为止，此时再将父个体放入子代种群中。

通过上述策略，则能有效地避免新一作中父辈之间进行交叉，又有利于产生新个体，同时有利于搜索到新的解空间。

（3）变异操作

传统的遗传算法的变异操作中，事先确定一个固定的突变概率，本文采用动态调整变异概率，记S■为收敛度的临界值。具体操作步骤如下：

step1：计算染色体适值g■f■，将最优染色体进行保存，记录其适值gf■。

step2：计算下一代染色体适值g■f■，并且保存最优染色体，记录其适值gf■。

step3：依Step1，Step2方法以此记录各后代的染色体适值分别为：gf■，gf■，gf■，…。

step4：If gf■=gf■，则记S■=1；If gf■=gf■=gf■，则S■=2，以此规律If gf■=gf■=gf■=…=gf■，则使S■=n-1；否则S■=0。

step5：定义P■=p■+S■/100为突变概率，可见突变概率随着S■的变化而改变，从而实现动态改变变异概率。

根据上述提出的动态改变变异概率的特点，变异操作采用自适应变异算子的方法进行设计。

2.7 终止操作

（1）本文采用经典的固定遗传代数的方法，既设定当算法迭代到M代时即停止，得到各时段发车时间间隔的二进制串，再将其转化为实数；

（2）将上述得到的二进制串转化为相应的实数Δt，根据客流量，根据Ceder所提出的模型[13-14]，引入拥堵弹性因子μ■，考虑道路的交通拥堵情况下公交车调度问题。

定义μ■k时段列车的行驶速度与规定最大行驶速度之比；可见0

min ■ ， ■ ， Δt （18）

注： x 表示对x做四舍五入的取整运算，当μ■=1，■∞。

其中：L为全程路长，P■■为k时段所有站点客流量的最大值。

3 实 例

利用上述公交车调度优化方案以及算法设计，以兰州市1路车下行线路作为研究对象，通过相关统计调查，得到了相应参数值，算法中的主要参数见表1：

根据某一天内（非节假日）公交IC卡数据采集，通过a■■=a■・■对原始统计值的修正。

式中：a■为第j辆公交车到达i站时上下车的乘客的原始值；a■■为第j辆公交车到达i站时上下车的乘客的修正值；p为公交公司的运营人数。

乘客车内以及等车费用由式（19）计算：

π■=π■=G■/365×5/7×8×60 （19）

其中：G■为人均国内生产总值；依照2015年统计，计算可得π■，π■约为0.05元/min。

利用调查参数，依照本文提出的优化模型以及算法，将其在Eclipse集成开发环境上通过java程序语言运行迭代200次。通过计算整合，得到了各时段的发车时间间隔以及发车车次，见表2：

根据表2，可得公交车在不同道路状况下的折线图，如图2所示。

实际中在车辆数足够多的时候，发车频率与乘客到达率成正比关系，而交通拥堵也往往发生在客流量大的时段；由图2可知：在考虑道路拥堵因素时，则会一定程度上降低了发车频率从而去缓解当前的交通压力，如果一定程度地增大μ■，则发车频率则会相应的减少，这与实际情况相符。μ■增加，交通拥堵增加，此时就应适当降低发车频率，使发车间隔增加，从而有效地控制运营成本。