一种基于混合启发式算法的智能公交调度方法   0    0

本发明公开了一种基于混合启发式算法的智能公交调度方法。本发明将模拟退火算法和遗传算法结合在一起，并且加入精英保留策略和适应度拉伸函数。将每一代种群中适应度最大的个体直接保留到下一代，避免它被交叉和变异操作破坏。适应度拉伸函数在算法的初期阶段，削减个体之间的差异，从而增加种群的多样性，避免遗传算法陷入局部最优解；在算法的后期阶段，增大个体间的差异，从而增加优秀个体被选择的概率，加快收敛速度。本发明运算速度快，能在较短时间内在给定发车时间频率条件下，得到优化后的调度计划，使乘客的等待时间大幅度减少；能动态调整发车频率，使发车频率符合客流总量的变化规律；能动态调整发车间隔，大幅度减少乘客的等待时间。

1.一种基于混合启发式算法的智能公交调度方法，其特征在于包括如下步骤：
步骤(1)读取乘客的刷卡记录，统计每天乘车总人数和每个时间段I内的人数，获取每天的历史天气状况和节假日情况；使用层次聚类方法，对获取的历史数据进行聚类分析；即将一天当中的乘车总人数、不同时间段内的乘车人数、天气情况和节假日情况组合成一个向量，然后对该向量进行归一化操作，使用系统聚类算法中的Ward法进行聚类操作，根据聚类的结果提取每个类别的特征；
所述的刷卡记录包括上车刷卡时间、上车站点、下车刷卡时间和下车站点；
所述的获取的历史数据包括乘客的刷卡记录、历史天气状况和节假日情况；
步骤(2)根据第二天的天气预报信息和节假日情况，从步骤1的聚类结果中匹配到一个类，并从该类中抽取一个向量作为预测值；
步骤(3)根据预测值，结合公交企业期望的满载率，两者相除，得到第二天的总发车班次；
步骤(4)随机生成N个向量，向量的维度与总发车班次相等；每个分量代表对应班次的发车时间，发车时间以分钟为单位，设定第一个分量等于0，最后一个分量等于末班车发车时间与首班车发车时间之间的分钟数；向量中的分量按从小到大的顺序排列，这N个向量组成初始解的集合P0，并设定迭代次数g为0；其中N为偶数；
步骤(5)建立公交调度的数学模型，以乘客的等待时间最短为目标设定适应度函数，计算每个初始解的适应度，然后通过混合启发式算法进行求解；
5-
1.使用适应度拉伸函数进行适应度拉伸操作，用拉伸后的值替换掉原来的适应度；
5-
2.按照轮盘赌选择策略从集合Pg中选择任意两个解，按照设定的交叉概率进行交叉操作，即随机选择一个交叉位置，交换两个解交叉点后的部分，得到两个交叉后的解；然后对两个交叉后解进行模拟退火操作：计算交叉后的解的适应度，如果适应度增大，接受新的解，否则以当前的接受概率接受新的解；从而获取两个新的解；
5-
3.按照设定的变异概率，对步骤5-2中获取的两个新解的每一个分量进行变异操作，即随机生成一个大小位于前后两个分量之间的自然数，替换掉原来的值，得到两个变异后的解；然后进行模拟退火操作：计算变异后的解的适应度，如果适应度增大，接受新的解，否则以当前的接受概率接受新的解；从而获取两个新的解，并将获取的两个新的解放入解集Pg+1；
5-
4.判断解集Pg+1中解的个数是否与N相等；如果相等，则实施精英保留策略，即当Pg+1中的最优解的适应度比Pg中的最优解的适应度小时使用解集Pg中适应度最大的解替换掉Pg+1中适应度最小的解；否则，重复步骤5-2和5-3，直至解集Pg+1中解的个数与N相等；
步骤(6)更新迭代次数g＝g+1，若已经达到最大的迭代次数Gmax，则输出解集Pg中适应度最高的解，即为优化后的发车时刻表；否则，转到步骤5-1；
所述的迭代次数Gmax为正整数。

2.如权利要求1所述的一种基于混合启发式算法的智能公交调度方法，其特征在于步骤5所述的公交调度数学模型的建立具体如下：
(1)所述的公交调度数学模型有以下前提条件：
BRT车辆停站后，等待乘客全部上车，不存在滞留现象；
BRT全线采用车外收费的方式，不存在投币或刷卡对车辆行驶时间的影响；
BRT全线采用相同的车辆型号，座位数量和最大载客数量相同；
不考虑线路的配车，认为车辆足够多；
BRT车辆按调度时间表发车；
BRT车辆在道路上顺序和发车顺序一致，不存在超车现象；
以分钟作为调度的最小单位；
(2)所述的公交调度数学模型中使用的变量及其含义如下：
m为整个调度周期内的发车次数；
n为线路指定方向上总的站点数量；
ti为一个调度周期中第i次车的发车时间，以分钟为单位，i＝1,2,...,m；
rj为线路指定方向上第j个站点随时间变化的到达率，单位为人/分钟，j＝1,2,...,n；
T为调度周期内乘客的总等待时间；
则
公交运营的成本分为不变成本和可变成本，公交调度和不变成本之间不存在直接的关系；设一个调度周期内公交运营收益为R，P为人均乘车费用，单位为元，L为指定方向线路总长度，单位为km，C为公交车辆的可变成本，单位为元/km，则公交公司的收益为总收入减去总的可变成本，具体如下：
设μ为乘客等待时间权系数，ν为公交公司收益权系数；根据二次惩罚法，公交调度优化模型的目标函数为：
minz＝μ×T-ν×R
设Nmax为最大车容量，ρ为期望满载率，则有约束条件Ⅰ：
为了保证规律到达乘客和随机到达乘客都能在较短的时间内等到所候车辆，设Hmin和Hmax分别为公交公司要求的最小和最大发车间隔，则发车间隔应满足下面的约束条件Ⅱ：
Hmin≤ti-ti-1≤Hmax i＝2,3,...,m
同时为避免造成发车的不连续现象，设τ为公交公司允许的最大发车间隔差值，则约束条件Ⅲ：
|(ti+1-ti)-(ti-ti-1)|≤τ i＝2,3,...,m-1
通过罚函数法来保证产生的解不违反调度问题的约束条件；基于以上的描述，调度问题的目标函数min f(X)形式如下：
其中min f(X)为加入罚函数后的目标函数值，ω1、ω2、ω3、ω4分别为约束条件Ⅰ、约束条件Ⅱ最小发车间隔、约束条件Ⅱ最大发车间隔、约束条件Ⅲ对应的惩罚系数；调度问题的解X是长度为m的向量，每个分量xi代表调度周期内第i次车距首班车的发车时间，以分钟为单位；
为了保证每个个体的适应度均大于0，同时也为了方便运用轮盘赌选择策略，对目标函数进行变换得到适应度函数的最终形式为：

3.如权利要求1所述的一种基于混合启发式算法的智能公交调度方法，其特征在于所述的模拟退火算法能够加强遗传算法的局部搜索能力，在遗传算法中每次完成交叉操作和变异操作以后，比较前后两个个体的适应度，进行模拟退火操作；模拟退火算法中需要设定初始温度T0，当前温度的计算公式为：
T*＝T0×σg-1
其中σ表示温度降低的速度，其取值为0＜σ＜1，其值越大，温度降低的越慢，值越小，温度降低的越快；g为算法当前迭代的次数；当新产生的个体的适应度减小时，接受新个体的概率为：
其中F(Xnew)、F(Xold)分别为新个体和原个体的适应度；
同时为了保证每个种群中最有优秀的个体能顺利进入下一代产生新的个体，在模拟退火和遗传算法的融合算法中，加入精英保留策略；每产生新的一代种群后，比较新一代种群和上一代种群中最佳个体的适应度值；如果新一代种群的最佳个体的适应度小于上一代的最佳个体，则用上一代的最佳个体替换新一代中适应度最小的个体；否则直接进入下一次迭代。

4.如权利要求1所述的一种基于混合启发式算法的智能公交调度方法，其特征在于步骤5-1中所述的拉伸函数的形式为：
其中F(Xi)代表个体Xi的适应度，F(Xi)'是拉伸后的适应度，T*指模拟退火算法中当前的温度，N代表种群中个体的数量，λ代表拉伸系数；
为了能够进行适应度拉伸，要在拉伸前对种群中所有的个体进行适应度标准化，令其中fitness指个体的适应度，fitness'指标准化后的适应度，maxfitness指当前种群中最佳个体的适应度。

5.如权利要求1所述的一种基于混合启发式算法的智能公交调度方法，其特征在于步骤5中所述的混合启发式算法的基本步骤如下：
1).设定如下参数的值：种群大小N，染色体长度Lc，交叉概率Pc，变异概率Pm，最大进化代数Gmax，初始温度T0，退火速度σ，拉伸系数λ；
2).初始化种群P0，即随机产生N个可行解构成初始化种群P0；计算初始种群中个体的适应度，进行标准化，对适应度进行拉伸操作；设定迭代次数g为0；
3).按照拉伸后的适应度进行轮盘赌选择，从种群Pg中随机选取两个个体；
4).交叉和模拟退火操作；采用单点交叉策略，将被选择的两个个体p1、p2按概率Pc进行交叉操作产生两个新的个体c1、c2；如果F(ci)＞F(pi)，则接受个体c1，否则以概率exp((F(ci)-F(pi))/T*)接受新个体；
5).变异和模拟退火操作；对新产生的个体c1、c2逐位进行变异操作，如果变异后的个体c1'适应度增大，则接受变异，否则以概率exp((F(ci')-F(ci))/T*)接受新个体；
6).把新产生的两个个体加入新种群Pg+1中，如果Pg+1中个体数量小于N，则转到步骤3)，否则进行下一步；
7).计算新种群中每个个体的适应度，并进行标准化操作；
8).对新种群中的个体进行适应度拉伸；
9).实施精英保留策略，用新种群替换原种群；
10).降温操作；
11).更新迭代次数g＝g+1，如果达到最大迭代次数Gmax，则输出种群Pg中的最优解，否则转到步骤3)。