网站首页  词典首页

请输入您要查询的论文：

　

标题 临界—遗传算法在公交调度中的应用
范文 韦尚成



摘 要：随着我国交通问题日益不平衡，为了缓解交通压力，研究公交车调度问题很有必要。针对公交车辆调度的现状，通过分析乘客出行的舒适度以及公交车的满载情况定义了乘车感知波动价格。结合实际建立了乘客最小乘车费用以及公交公司最小总耗费为目标的一个综合优化模型；并引入拥堵弹性因子，分析了它对发车间隔的影响。同时针对传统遗传法的局限性以及收敛速度慢等缺陷，通过个体的相似度与父辈相似度的临界值相比较，动态调整变异时间和控制变异概率的方式对遗传算法进行改进。最后应用临界—遗传算法（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 引 言
隨着我国社会经济的快速发展，我国机动车保有量逐年增加，交通问题日益严重，用有限的道路面积承担尽可能多的出行是解决城市交通问题的有效途径，为此如何有效地调度公交车运行是其很重要的环节。大量国内外的学者从不同的角度对公交调度进行了研究，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·π■；θ为乘客波动系数，θ<1，当x■=B即此时乘客数为公交车车型定员时δ■=π■；当x■>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■<14<2■，故而Δt的二进制串长度至少需要4位，如表1：染色体的长度取决于时间段的数目，如果全天共分成n个时段，则染色体的长度为4n。
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为相同的等位基因，則θα，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<μ■≤1；
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可知：在考虑道路拥堵因素时，则会一定程度上降低了发车频率从而去缓解当前的交通压力，如果一定程度地增大μ■，则发车频率则会相应的减少，这与实际情况相符。μ■增加，交通拥堵增加，此时就应适当降低发车频率，使发车间隔增加，从而有效地控制运营成本。
优效性，现采用同组数据通过与S-GA分别计算目标最优值进行性能比较，结果如图3所示。
由于相比较S-GA的固定变异率，C-GA却采用自适应动态调整的变异，这样能较好地维持种群的可进化性，同时又大大的提高了算法的优效性；由图3可得C-GA在收敛速度上以及效率上明显优于S-GA。
现针对公交车优化模型，为了验证C-GA的可行性以及准确性，采用同数据与S-GA结果进行分析，如图4。
图4显示：算法得到解在各个高峰阶段，发车频率都较高，发车间隔小，此时主要体现出乘客的利益；而在低峰或者平峰阶段，发车频率小，发车间隔大，又恰好地反映了公交公司的利益；同时C-GA比起S-GA得到的发车频率在小客流量时间段发车频率都较小，客流较大时段发车频率都较大。众所周知每天8：00～9：00以及17：00～19：00为全天客流量最大的时间段，实际中此时段也往往是人们上下班，学生上放学的时刻，容易造成交通拥堵现象，前文也有相关分析，故C-GA在此情况下得到的发车频率的降低幅度会更大，在满足交通量需求的同时更好地均衡了乘客与共交公司的二者利益；由上述分析显示本文模型符合实际情况，算法有效。
4 结 论
本文从实际情况出发，在考虑乘客上下车的耗时，以乘客舒适度和公交满载率为基础，定义了感知波动价格函数来形象反映乘客出行过程中的广义价格变化，从而建立了以公交公司与乘客总耗费最小的公交调度优化问题；引入了拥堵弹性因子来，通过与正常情况下公交车发车频率的对比验证了拥堵弹性因子对公交车发车间隔产生了较大的影响，且能有效控制线路上的公交发车间隔在满足交通量需求的同时维护了二者利益，切合实际情况，对研究公交的吸引度以及公交调度有一定的意义。同时为了克服遗传算法的不足之处，设计了C-GA算法进行优化，并通过S-GA作比较通过实例证明C-GA对公交调度优化是可行有效的。由于本文的研究时间以及知识水平有限，论文中存在着很多有待改善的地方，比如客流到达分布以及不确定性未被考虑、过于简化旅客到达率，为详细研究、模型的相关参数较多，参数值的标定缺乏理论上的支撑等。后续工作中考虑随机客流分布研究，其他公交车运行的影响以及上下行等问题做进一步研究，使得模型更加贴近实际情况，为城市公交调度提供重要理论依据。
参考文献：
[1] Malacly C. Optimizing scheduled times allowing for behavioural response[J]. Transportation Research， 1998，32（5）：329-342.
[2] Paolo D. S， Francesco F. Bus service optimization with fuel saving objective and various financial constrains[J]. Transportation Research， 2001，35（2）：157-176.
[3] 王超，徐猛. 考慮道路交通拥堵的公交发车间隔优化模型[J]. 交通运输系统工程与信息，2011，11（4）：23-30.
[4] Ceder A. Public transit planning and operation： Theory， modeling and practice[M]. Elsevier， 2007.
[5] 童刚. 遗传算法在公交调度中的应用研究[J]. 计算机工程，2005，31（13）：29-31.
[6] 郑小花，陈淑燕，武林芝. 模拟退火算法在公交调度中的应用[J]. 信息化研究，2009，35（9）：45-47.
[7] 崔明月，黄荣杰，刘宏钊，等. 量子遗传算法在公交车辆调度中的应用[J]. 实验室研究与探索，2014，33（12）：1-4.
[8] 马雁，王非，周永年. 改进遗传算法在公交智能调度中的应用[J]. 科技通报，2015，31（9）：13-15.
[9] 张飞舟，晏磊，范跃祖. 智能交通系统中的公交车辆调度方法研究[J]. 中国公路学报，2003，16（2）：82-85.
[10] 王凌. 车间调度及其遗传算法[M]. 北京：清华大学出版社，2003：68-76.
[11] 李继哲，王书振，王东. 基于约束范围交叉操作的遗传算法[J]. 北京交通干部管理学报，2004，14（3）：232-261.
[12] 梁旭，黄明，宁涛，等. 现代智能优化混合算法及其应用[M]. 北京：电子工业出版社，2014：54-55.
[13] Ceder A. Bus frequency determination using passenger count data[J]. Transportation Research Part A： General， 1984，18（5）：439-453.
[14] Ceder A， Golany B. Creating bus timetables with maximal synchronization[J]. Transportation Research Part A： Policy and Practice， 2001，35（10）：913-928.
随便看

　

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。

　

Copyright © 2004-2023 puapp.net All Rights Reserved
更新时间：2024/12/22 23:28:45