基于QPSO算法的智能公交调度优化研究

温馨，曾培勇，张全

（沈阳工业大学信息科学与工程学院，沈阳　110870）

基于QPSO算法的智能公交调度优化研究

温馨，曾培勇，张全

（沈阳工业大学信息科学与工程学院，沈阳110870）

针对城市智能公交调度优化问题，在充分考虑公交企业运营成本和乘客候车成本的基础上，引入乘客抱怨度这一指标建立一个三目标的公交调度优化模型，并通过线性加权法，将三个目标函数合并为一个目标函数。由于粒子群算法易陷入局部最优的缺点，特引入量子特征，利用量子粒子群算法具有判断早熟现象和能够跳出局部最优的特点，获得公交发车时间间隔的最优解。

0　引言

近年来，随着国民经济的飞快发展，居民拥有机动车的数量逐渐增多，交通压力已经过度饱和，这不仅影响了居民的正常生活，也制约了我国经济的发展。因此，具有大客运量，人均占用道路少的城市公交被认为是解决城市交通问题的最佳策略［1］。在日常生活中，由于每天各时段的客流量是随机的，而传统的公交调度却采用固定发车间隔的策略，因而会导致公交车载客量不均、乘车舒适度低的情况。所以，如何改善公交调度手段、提高公交运营效率，是当前公交系统面临的主要问题。

针对上述的不足，本文建立以发车间隔为变量，公交企业、乘客利益以及乘客抱怨度为目标的模型，采用了量子粒子群算法进行智能调度，以便于同时兼顾乘客和公交企业的利益。

1　智能公交调度模型

1.1模型假设

数学模型是对实际问题的抽象、概括，因此不可能考虑到所有的复杂因素，必须对外部条件做相应的限制［2］。本文对公交线路静态调度问题中做出假设：

①本文针对城市公交系统中的一条公交线路，且只考虑单程车运行；②同一线路中所有车辆的型号、容量、乘客乘车费用相同；③一天被分为不同的时段，且同一时段内，相邻两车的发车间隔相同；④乘客到达车站服从均匀分布；⑤乘客按秩序上车，公交车达到最大满载率则停止上客；⑥公交车运营过程中，忽略交通拥堵或事故等客观因素。

1.2模型建立

公交线路静态调度优化模型旨在确定兼顾乘客和企业利益的最优发车间隔，是一个多目标优化。本文主要以乘客候车利益、公交企业利益，以及乘客抱怨度三者为目标建立模型。

（1）符号说明

i：公交站点的数量，i=｛1，2，…，m｝；j：一天内不同时段的个数，j=｛1，2，…，n｝；tj：第j时段的发车间隔；Tj：第j时段总的时间长度；nj：第j时段的发车次数，nj=Tj/tj；C1：乘车费用；C2：公交车运营一次的费用；puij：第j时段第i车站乘客的平均到达率；pp：一天内总的乘客数，pp=乘客等车时间的容忍上限；lr：公交车最低满载率；hr：公交车最高满载率；np：公交车额载；tr：乘客容忍的公交车满载上限；mtj：第j时段最大发车间隔；pi1：公交车在第i站的上车人数；pi2：公交车在第i站的下车人数；pij：公交车在到达第j时段第i车站时车上已有的人数，pij=p（i-1）j+pi1-pi2；bp：乘客的等车时间抱怨度（超过乘客的等车时间上限）即：如果tj＞htj，则bp存在，否则bp=0；bl：乘客的拥挤程度抱怨度（超过乘客所能容忍的满载上限）即：如果pij＞nj×np×tr，则bl存在，否则bl=0；δ：乘客每分钟候车时间的费用。

（2）目标函数

本文综合考虑乘客和公交企业利益，选取企业利益最大、乘客候车利益和抱怨度 （等车时间和拥挤程度）最小3个目标。为了量纲的统一，将其均化为费用的函数，即：

公交企业利益：

乘客候车等待利益：

乘客的抱怨度：

c=bp+bl

等车时间抱怨度：

拥挤程度抱怨度：

通过分析，该模型包括三个目标：maxa、minb、minc。由于三者间的矛盾性，特引入具有修正主体利益的加权系数，将其转化为单目标函数［3-5］。因此，该模型的目标函数为：

（3）约束条件

为了获得更加合理，更好满足人们出行要求的公交车发车时刻表，本文对车辆的满载率以及发车间隔进行了约束。即：公交车的满载率以及各时段的发车间隔均具有上下限约束［6］。

①满载率约束：

②时间间隔约束：

由于两个约束都是与时间间隔有关的不等式，因此可整理成下式：

2　模型求解

2.1基于粒子群算法的智能公交调度

粒子群优化是由Kennedy和Eberhart［7-8］于1995年提出的一种优化算法，是将群体中的个体看作是在N维搜索空间中没有质量和体积的粒子，且每个粒子在解空间中运动，并由速度决定它的运动方向和距离，同时通过追随自身的个体最好位置pbest与群体的全局最好位置gbest来实现对候选解的进化［9］。

首先初始化一群随机粒子，通过多次迭代找到最优解。在迭代过程中，每个粒子通过两个极值（个体极值pbest和全局极值gbest）来不断更新自己的方向和位置。迭代时，初始化的每个粒子所在的位置即为个体极值，粒子种群最好的位置即为全局极值。当完成一次迭代操作后，对每个粒子迭代前后的位置进行比较，如果比之前的个体极值好则进行更新；再对种群中所有粒子的个体极值进行比较，得到所有个体极值中的最优解，如果他比之前的全局极值好，则将他更新为全局极值。经过多次迭代后，最终得到的全局极值即为所求的最优解。在找到这两个最优值时，粒子根据下面公式来更新自己的速度和位置［10］：

其中，ω为权重，vi，d表示第i粒子经过j次迭代后的速度；xi，d表示第i粒子经过j次迭代后的位置；pbest 和gbest分别表示第i粒子经过j次迭代后得到的个体极值和全局极值；c1c2为学习因子；r1r2为［0，1］区间的随机数。

2.2基于量子粒子群算法的智能公交调度

量子粒子群算法是在PSO的思想上引入量子行为，即在进化过程中，粒子以一定概率取加或减，更新每个粒子的位置，从而生成新的粒子群体，同时计算个体和全局最好值，并将与上一代比较，好坏更替。以此循环，直到找出符合条件的最优解。更新位置公式如下：

其中，b为收缩扩张系数，α，u为0到1之间的随机数，如果产生的u大于0.5，则取加，反之取减。

3　仿真结果分析

假设公交线路运营长度6.4公里，共设8站，一天内的运营时间被分为5个时段：6：00-8：30，8：30-12：00，12：00-16：00，16：00-19：00，19：00-21：00，其中6：00-8：30和16：00-19：00是高峰期，19：00-21：00是低峰期，8：30-12：00，12：00-16：00是平峰期。表1和表2分别给出该线路一天各时段统计乘客的上、下车数量。主要参数C1=1，C2=36，δ=0.2，lr=0.5，hr=1.2，tr=0.9，np=45，mtj=［12，16，16，12，22］，htj=［9，13，13，10，18］，λ1= 0.5，λ2=0.3，λ3=0.2。粒子群规模为200，最大迭代次数为200。

表1　该线路一天内各时段的上车乘客数

表2　该线路一天内各时段的下车乘客数

对比结果：

①粒子群算法

②量子粒子群算法

由上述两种算法结果对比可以看出，量子粒子群算法求出的结果更优。符合高峰时期车辆发车间隔小，低峰时期车辆发车间隔大。

4　结语

本文在充分考虑公交企业和乘客利益的基础上，引进乘客的抱怨度，建立了三目标函数，并运用两种算法对其进行求解，最后发现量子粒子群算法求出的结果更优，更符合实际。它不仅减少了乘客的等车时间以及抱怨度，也减少了公交企业的运营成本。解决了传统公交固定发车间隔的缺陷，从而改善了公交服务质量，增强了公交车吸引力，使人们更愿意乘坐公交车出行。

［1］周晓云，吴兆根.RFID在公共交通领域的应用［J］.中国无线电，2005（5）：49-50.

［2］陈茜.城市常规公交线路车辆调度优化研究［D］.东南大学，2003

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

［4］李治廷.基于粒子群与蚁群混合算法的公交调度研究［D］.大连理工大学，2013，6.

［5］童刚.公交调度模型及算法.青岛科技大学学报［J］，2004，25（3）：253-257.

［6］张晓培.基于遗传—牛顿算法的公交优化调度［D］.长沙理工大学，2011.

［7］Eberhart，R，Kennedy，J.A new optimizer using particle swarm theory［C］.Proc.6 Int.Symposium on Micro Machine and Human Science，1995：39-43.

［8］Kennedy，J，Eberhart，R.Particle swarm optimization［C］.IEEE International Conference on Neural Networks（Perth，Australia），IEEE Service Center，Piscataway，NJ，1995，IV：1942-1948.

［9］孙俊.量子行为粒子群优化：原理及其应用.清华大学出版社.2011，8.

［10］尹相勇.基于实时专家系统的公共交通区域调度优化模型及实用方法研究［D］.北京交通大学，2004.

Intelligent Bus Scheduling；Comfort of Passengers；Linear Weighted；Quantum Particle Swarm Optimization；Departure Interval

Research on the Optimization of Intelligent Bus Scheduling Based on QPSO Algorithm

WEN Xin，ZENG Pei-yong，ZHANG Quan
（School of Information Engineering，Shenyang University of Technology，Shenyang 110870）

1007-1423（2015）26-0007-04

10.3969/j.issn.1007-1423.2015.26.002

2015-09-01

2015-09-10

智能公交调度；乘客抱怨度；线性加权法；量子粒子群算法；发车时间间隔

In view of the city intelligent bus scheduling optimization problem，based on the full consideration of the bus company operating costs and the passengers waiting costs，establishes a bus scheduling optimization model with three goals by introducing an additional factor，i.e.，the comfort of passengers.By means of the linear weighted method，integrates three objective functions.Since the particle swarm optimization algorithm is easy to fall into local optimum，uses the QPSO to achieve the optimal solution of bus departure interval by its capacity of judging precocious phenomena and jumping out of local optimum.