基于遗传算法的公交调度模糊最优解

武 斌

(中国石油大学胜利学院 基础科学学院,山东 东营 257061)

发展城市公共交通可以缓解交通拥堵,减少环境污染,方便人们出行,因此研究公共交通调度的数学模型及其求解方法有其现实意义。关于公交调度的研究内容,许多学者针对公交调度的满载率问题[1]、发车频率[2]、车型优化[2]、客流分布[3]以及指挥系统[4-5]等进行了研究。然而,以往的公交调度模型大多是确定性的模型,要求精确地确定目标函数值,这样可能无法完全发挥模型的作用,而且很多模型没有充分考虑乘客和公交公司利益的协调。鉴于此,笔者首先建立能够模拟公交车运行的确定性模型,然后在此之上建立公交优化调度的模糊多目标非线性规划模型,使用遗传算法对其进行求解,得出模糊最优解并进行实例分析。

1 公交调度模糊多目标规划模型建立

公交公司在运营过程中,若乘车票价一定,则总是希望加大发车间隔以减少其可变运营成本,但是发车间隔过大,乘客则会因为等车时间过长,车内过于拥挤而选择其他出行方案。因此确定合理的发车时刻表是至关重要的。公交车在行驶过程中外部环境多变、客流随机性大,因此为建立能够模拟公交运营的多目标规划模型,假设如下:

(1)公交车均按照规定路线行驶,不存在超车和等客现象;

(2)公交车辆始终是匀速行驶,并且不受道路突发情况的影响;

(3)公交车均采用同一车型,即额定的载客人数相同。

1.1 符号说明

建立模型所用到的变量如表1所示。

1.2 模型的目标函数

公交优化调度主要是要考虑如何协调公交公司和乘客之间的利益,既要让公交公司在固有运营条件下尽可能的获利,也要尽可能地降低车上拥挤程度,减少乘客等车时间。从极大化公交公司盈利和极小化乘客的等车费用、车内费用出发建立发车间隔优化模型[6]。该模型的目标函数有:

(1)乘客的等车费用。

(1)

表1 变量符号说明

(2)乘客在车内的费用。乘客的车内费用是乘客在车内的时间与转换系数U2的乘积,而乘客在车内的时间主要分为T1和T2两部分,其中T1为乘客从第i-1站到第i站的乘车时间,T2是公交车到达第i站时不下车的乘客需要在车上等待的时间,可以取在第k站时乘客上车时间与下车时间的平均值。

(2)

(3)

(3)公交公司的收益。在时间段T内,公交公司的发车数为60 T/h,则表示公交公司运营收益的目标函数为

(4)

1.3 模型的约束条件

(1)发车次数约束。

(5)

公交公司在一个时段内总的发车次数不应超过其固有条件下的最大发车次数Smax。

(2)发车间隔约束。

(6)

(3)满载率约束。

(7)

公交车的满载率应该低于公司设定的最大满载率ηmax,即车上不能过于拥挤。

1.4 模型处理

对于目标函数(1)、(3)、(4)可以分别引入如下的隶属函数。

乘客等车费用目标:

(8)

式中,Re、Ru分别表示等车费用目标的期望值和上限值。

乘客车内费用目标为

(9)

式中,Ie、Iu分别表示车内费用目标的期望值和上限值。

公交公司的运营收益目标为

(10)

式中,Qe,Ql分别为公交公司的可变运营费用目标的期望值和下限值。

由于隶属度函数的引入,模糊多目标规划模型的目标函数为

(11)

2 基于遗传算法的模糊最优解求解方法

由于模型的约束条件(5)～(7)是确定性的,则模糊多目标模型可以等价于如下形式的确定型非线性规划:

maxα

s.t.

α≤μk(zk(X)),k=1,2,3;

gi(X)≤Gi,i=1,2,3;

0≤λ≤1.

(12)

式中,gi(X)≤Gi,i=1,2,3表示原模型的约束条件,α是决策者对各个模糊目标的最小满意度。

α表示为

α=min{μk(x),k=1,2,3}.

(13)

在求解过程中,对于个体x,

μmin(x)=min{μ1(x),μ2(x),μ3(x)}.

(14)

使用的适应度函数为

(15)

式中,α0为事先确定的可以接受的满意度,0≤ε≤1。

使用遗传算法求解的步骤[8]如下:

(1)初始化。输入满意度α0=0.2,最大遗传代数max_gen=200,种群大小NP=200,考虑的准则依次取各个目标的隶属度最大值;

(2)在区间[Xl,Xu]内随机产生初始种群,然后按照式(15)计算个体的适应度函数值;

(3)初始迭代步数k=1;

(4)对于个体j(j=1,2,…,NP),计算个体的适应度函数F(j)以及选择概率P(j):

(16)

(17)

(18)

式中,r是区间[0,1]上任取的随机数,T为该算法设定的最大迭代步数,t为本次迭代次数,b是不一致参数。该函数能够随着迭代步数的增加,缩小搜索范围,也就是局部搜索;

(6)用式(15)计算个体j的隶属度函数值,从种群中选择最优隶属度函数值用于更新μmax,并依次更新各个准则的隶属度最大值,同时保存最优个体的信息;

(7)令k+1→k,若k≤T,则返回第2步,否则则输出最优的隶属度函数值μmax以及各准则对应的最优解。

3 实例分析

选取某一公交线路,使用上述分析的模型及算法进行求解,该公交线路的总长为7.3 km,共有15个站点,发车时间为6:00～19:00,公交车的票价为1元/人·次,公交车行驶速度为20(km/h),最大发车车次为20,公交车的额定载客数为40(人/车),最大发车间隔hmax=15 min,最小发车间隔hmin=2 min,每辆车的平均期望满载率τ0=0.5,每辆车的最高断面期望满载率τmax=0.7,乘客等车时间转换为运营成本的系数为0.3(元/(人·min)),乘客在车内时间转换为运营成本的系数为0.15(元/(人·min)),每位乘客的平均上下车时间为3(s/人),本文使用模糊聚类分析对发车时段进行了划分,并采用驻站调查法[9]对东营市某公交线路的单向断面通过量进行了统计,具体调查数据如表2所示:

表2 各时段的单向断面通过量

将各参数代入模型,使用遗传算法求解可得各时段的发车间隔如表3所示。

普通公交调度多目标非线性规划模型的过结果如表4所示。

表3 模糊最优解结果

表4 多目标非线性规划结果

设论域U={x1,x2},其中x1为模糊多目标非线性规划模型,x2为常规多目标规划模型,使用模糊综合评判对其进行优劣分析,可得x1为第一优越对象。可见使用模糊规划制定的发车间隔比较合理,兼顾了乘客和公交公司双方的利益。从表3和表4可以看出,模糊多目标规划降低了乘客的出行成本,但公交公司的运营收益有所降低,本文是客流量一定的前提下进行模型求解的,若乘客乘坐公交车的成本降低,客流量就会有所增加,公交公司的运营收益会有所提高,所以使用遗传算法求解的模型模糊最优解比一般多目标规划更为合理,符合实际应用。

4 结束语

建立以发车间隔为决策变量的公交调度模糊多目标规划模型,并给出了求解该模型的遗传算法,能够得出该模型的模糊最优解。模糊规方法采用隶属度函数来表示目标与期望值之间的接近程度,允许模型在一定范围内求解。因此使用模糊规划求解公交优化问题能够在一定范围内协调各个目标值,得到更好的优化结果,所以对于公交调度问题,建立模糊多目标规划模型并对其求解更合理。