第3卷第1期2003年2月交通运输系统工程与信息JournalofTransportationSystemsEngineeringandInformationTechnologyVol13No11February2003

文章编号:100926744(2003)0120041204

基于遗传算法的公交车辆智能排班研究

李跃鹏,安　涛,黄继敏,范跃祖(北京航空航天大学自动化科学与电气工程学院,北京100083)

摘要:　运营车辆智能排班是公交车辆智能调度需要解决的典型问题之一Λ它可以描述为:通过某种智能化的算法,在有限的算法步骤内,找出所有满足约束条件的排班方案中的最优方案或接近最优的方案Λ作者针对公交排班的特点,对遗传算法的各个算子进行了专门化处理并进行了大量的试算Λ结果表明,遗传算法对解决公交车辆排班问题是有效的Λ关键词:　智能排班;遗传算法;公共交通;调度中图分类号:　U121;TP18

ResearchOnIntelligentScheduleofPublicTrafficVehiclesBasedOnGeneticAlgorithm

LEEYue2peng,ANTao,HUANGJi2min,FANYue2zu(SchoolofAutomation,BeingUniversityofAeronauticsandAstronautics,Beijing100083,China)

Abstract:　Intelligentscheduleoftrafficvehicleisatypicalproblemforpublictrafficvehicle’sintelligentdispatch.Itcanbedescribedasfindingthebestorclosetothebestalternativeamongalltheschedulemethodsthatcanmeettherestrictedconditionwithlimitedcalculationprocessesthroughacertainintelligentarithmetic.TheauthorhasspecialmanagementtoeachoperatoroftheGeneticAlgorithmandmadeagreatdealoftrialsaccordingtopublictrafficschedule’sfea2tures.ResultsshowthattheGeneticAlgorithmiseffectiveforsolvingtheproblemofpublictrafficvehicle’sschedule.Keywords:　intelligentschedule;geneticalgorithm;publictraffic;dispatchCLCnumber:　U121;TP18

收稿日期:2002210230

李跃鹏:北京航空航天大学自动化学院测控系硕士研究生,主要从事智能交通系统方面的研究.

1　遗传算法概述遗传算法(GeneticAlgorithms,简称GA)

是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法Λ它最早由美国密执安大学的Holland教授于20世纪60年代提出[1]Λ70年代DeJong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验[2]Λ在一系列研究工作的基础上,80

年代由Goldberg进行归纳总结,形成了遗传算法的基本框架[3]Λ对于一个求函数最大值的优化问题(求函数最小值也类同),一般可以描述为下列数学规划模型:maxf(X)(1)X∈R(2)RΑU(3)式中,X=[x1,x2,…,xn]T为决策变量,f(X)为目标函数,式(2),(3)为约束条件,U是基本空间,R是U的一个子集Ζ满足约束条件的解X称为可行解,集合R表示所有满足约束条件的解所组成的集合,称为可行解集合Ζ遗传算法的基本运算过程如下:1)初始化:设置进化代数计数器t=0,设置最大进化代数T,随机生成M个个体作为初始群体P(0)

Ζ

2)个体评价:计算群体P(t)

中各个个体的

适应度Ζ3)选择运算:将选择算子作用于群体Ζ4)交叉运算:将交叉算子作用于群体Ζ5)变异运算:将变异算子作用于群体Ζ群体P(t)经过选择、交叉、变异运算之后得到下一代

群体P(t+1)Ζ6)终止条件判断:若t≤T,则:t←t+1,转到第二步继续运算;若t>T,则以进化过程中所得到的具有最大适应度的个体作为最优解输出,终止计算Ζ2　公交排班问题遗传算法的设计与实现公交排班的目的是确定最优或近似最优的运营车辆的发车时间表,公交车队按照该时间表发车能够达到最高的运营效率和服务水平Ζ为了便于试验比较,作者选用北京市公交1路运营车队作为排班对象,不失一般性,只考虑下行线路,即要优化1路车始发站的发车时刻表Ζ设首班车发车时刻为早上6点整,末班车发车时刻为22点整,所有运营车都在整分钟时刻发车,一天之内的总班次为m,总时间为16小时,即960分钟Ζ我们用表示第辆运营车发车时刻距首发时刻的时间,以分钟为单位Ζ则决策变量可表示为:X=[x1,x2,…,xm]T,根据其物理意义可知,优化问题的约束条件如下:xi∈Z且xi≥0,其中i=1,2,…,mx1=0,xm=960x1体对应的表现型X就是智能排班过程要给出的最优排班结果Ζ再考虑车队的运营效率问题Ζ一般来讲,车队的运营效率可以用在保证服务水平的前提下,一天之内乘客运营需要总班次来表示,需要的班次越少,说明运营效率越高Ζ可以证明如下结论:设在总班次一定的情况下(设为m′),使得式(5)所示的目标函数值最小的X为Xmin,则在所有满足f(X)≤f(Xmin)的X中(即保证服务质量),Xmin一定是所需总班次最少的一个(即运营效率最高)Ζ以上结论的逆命题也成立(证明过程省略)Ζ由此可以看出,在保证运营效率的情况下寻求乘客总等待时间最少和在保证服务水平的前提下使车队运营效率最高其实是一个问题的两方面,其中任一策略都可以作为排班问题的寻优标准,不过从算法实现的角度来看,第一种寻优标准更易通过遗传算法实现Ζ所以作者采用式(5)作为目标函数是适宜且具有实际意义的Ζ这

样,排班问题就描述为在总班次一定的情况下,

使(5)式所示的目标函数值最小的寻优问题Ζ在实际运算中,总班次m=60Ζ数学描述如下:

minf(X)=6ni=16mj=16k=1(Tij-t

ijk

)

X∈Rm=60

(6)

遗传算法里用适应度这个概念来度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度[4]Ζ适应度较高的个体遗传到下一代的概率较大;而适应度较低的个体遗传到下一代的概率就相对小一些Ζ计算个体适应度的函数或过程称为适应度函数(Fit2

nessFunction),记为F(X)Ζ为了选择算子设计

的方便,适应度一般要求非负Ζ本文所述的排班问题属于求目标函数值最小的优化问题,作者拟定的转换规则见公式(7)ΖF(X)=Cmax-f(X)(7)式中,Cmax为同一代群体中所有目标函数值的最大值Ζ可见由(7)式求出的个体适应度必然大于

24交通运输系统工程与信息2003年2月等于0,且目标函数值越小,个体的适应度越大Ζ4　编码方案和群体初始化本文设计的遗传算法采用了“真实值编码方法”,在这种编码方法中,个体染色体的各个基因座上所填的就是决策变量的真实值Ζ则与X=[x1,x2,…,xm]相对应的染色体X即表示为码串x1,x2,…,xmΖ对于本文要解决的公交排班问题来说,真实值编码具有下面的优秀特性,即如果一个个体中性状优良的基因片断被遗传到下一代,那么该片断在新个体中仍然是优良的Ζ群体的初始化即群体P(0)的产生过程,应该随机产生Ζ针对公交排班的特点,作者在初始化过程中,特别设计了编码调整的步骤Ζ目的是使初始群体的个体当中包含更多的优秀基因片断Ζ显然,乘客在时间上的分布在很大程度上左右了排班的优化过程,而乘客的分布又很不均匀,比如一天内有若干高峰,这时单位时间内到达各个车站的乘客数量会激增,显然,这时发车间隔应该缩短,其他时候发车间隔应该加长Ζ可见,一个好的排班结果必然是某些时候的发车密度大,某些时候则要稀疏一些Ζ而由于随机函数产生的随机数是在区间(0,960)上均匀分布的,所以完全靠随机函数产生的群体中,很少有个体会出现上面的所说的性质Ζ为此,作者根据上述公交排班的特点,设计了称为局部收缩调整的编码调整算法Ζ调整的计算见公式(8):x′i=xk󰃖a󰃜i-k󰃜+xi󰃖(1-a󰃜i-k󰃜)(8)式中,x′i是基因xi经过调整后的值,易知x′k=xk,称基因xk为收缩中心Ζa∈(0,1),称之为收缩系数Ζ用(8)式作用于个体中的所有基因后,所有的基因值都向收缩中心xk靠拢,同时,距离xk越近的基因,靠拢得越厉害,当xi离xk较远时,a󰃜i-k󰃜很小,则xi调整得很小Ζ所以这种算法称为局部收缩调整算法Ζ该算法的结果是收缩中心附近的发车密度变大了Ζ初始化过程使用了局部收缩调整以后,个体中包含优秀基因片断的可能性增大了,从而使遗传算法的搜索性能得到了比较明显的改善,这一点将在后面给出试验结果Ζ5　遗传算子的设计遗传算子包括选择算子,交叉算子和变异算子,它们依次作用于群体P(t),从而产生新一代群体P(t+1)

Ζ

1)选择算子

一般的比例选择方法(ProportionalModel)

是一种回放式随机采样的方法Ζ基本思想[1]是:

各个个体被选中的概率与其适应度的大小成正比Ζ本文中对比例选择方法做了进一步改进,方法如下:先比较群体P(t)

中的各个个体,找出

P(t)中所有不同的个体,组成群体P′(t),显然

P′(t)ΑP(t),选择过程对P′(t)以比例选择方法

进行Ζ共选择M次,产生新一代群体P(t+1)

Ζ

作者称这种选择方法为分类比例选择Ζ可以看出,当P(t)

中的所有个体都不相同时,两种选择

算法是等价的Ζ但在遗传算法搜索的后期阶段,

群体中可能大部分个体都是相同的,这时,用分类比例选择时,新出现的优秀个体将以更大的概率复制到下一代Ζ可见比起比例选择方法,分类比例选择具有更强的局部搜索能力Ζ2)交叉算子

选择单点交叉(One2pointCrossover)[1,2]作为遗传算法的交叉运算Ζ需要指出的是,交叉点的选择必须保证新的个体符合约束条件Ζ如果随机选取的交叉点不能使新的个体满足约束条件,

即新产生的个体基因可能不完全是按升序排列的Ζ则将交叉点向某个方向移动,直到可以产生符合条件的新个体为止Ζ为了加快算法的收敛速度,作者采用了局部选择的策略,即将交叉产生的新个体和原个体进行比较,选择适应度最大的两个作为交叉运算的结果Ζ局部选择策略的效果将在后面给出Ζ3)变异算子