Matlab 遗传算法解决公交车辆发车间隔优化问题
1.模型介绍
1.1公交公司运营成本分析
本设计中公交公司运营成本主要考虑的是公交车在线路上的运营时间成本。考虑到模型的简便性以及求解的简便性,所以本设计不考虑公交公司车辆的的固定费用。
1.2乘客出行成本分析
本设计中乘客出行成本主要考虑乘客的候车时间最短。当一天内乘客的平均候车时间最短即认为乘客的出行本最小。
一天内乘客的候车时间除以乘客数即为一天内乘客的平均候车时间:
1.3目标函数及约束条件的确定
将两个函数整合得出该系统的总成本,使总成本最小,即为目标函数最小:
在该模型的约束条件中式(3-4)代表优化后公交公司的运营车辆的发车间隔要在最大间隔和最小间隔之间;式(3-5)代表优化后公交公司运营车辆的发车时间要在现有发车最早和最晚发车时间之间;式(3-6)表示任意时刻公交车上的乘客数不得超过公交车的最大承载人数。
2.模型求解
针对本设计模型的求解,算法的设计如下:
(1)编码
根据公交调度的解为某一天的发车时刻表这一实际情况,本设计将采用[0,1]形式的编码方式。本论文设最大发车间隔为30分钟,最小发车间隔为5分钟,取发车时刻为5到30之间的整数(包括5与30)。在本优化模型中,变量是发车间隔。对该问题进行编码,0表示该时刻不发车,1表示该时刻发车。
(2)初始化种群
…
(3)适应度函数
…
(4)操作算子
…
1)选择
本设计采用轮盘赌的选择方法。其原理是个体的适应度的值越大,则选中该个体的概率就越高。个体被选中的概率:
其中,为个体的适应度。
2)交叉
交叉操作的频率被交叉概率的选取决定,频率越高,收敛到接近最优解的区域越快,但是为了防止过早的收敛,一般取值0.4—0.9,本设计遗传交叉概率取。
3)变异
因为遗传中变异不是普遍存在的,所以本设计采用较小的变异概率。
(5)终止条件
给定最大迭代次数MAXGEN,当算法迭代次数到达MAXGEN所规定的次数时,算法终止,本设计取MAXGEN=500。
本设计的算法求解步骤:
STEP1:程序初始化,将该模型的各个参数初始化;
STEP2:根据规则,随机产生STO个染色体,使种群初始化,并设置迭代次数计数器g;
STEP3:计算第g代各个个体的总成本,并确定其适应度;
STEP4:判断是否满足g<MAXGEN,若满足转到STEP5,否则停止计算,选择适应度最优的个体作为结果输出。
STEP5:采用轮盘赌的方法选择(1-GGAP)个个体作为xia一代的父代并重新插入GGAP个个体共同进行下一代的遗传;采用单点交叉进行交叉操作;按照每个个体变异率进行变异操作。令g=g+1。转向STEP3。
种群规模STO
100
交叉概率Pc
0.8
变异概率Pm
0.05
迭代次数MAXGEN
500
代沟GGAP
0.8
公交车单位时间运营费用
0.8
乘客单位等车成本
0.4
现有首班车发车时间To
5:50
现有末班车发车时间Te
21:30
公交权重
0.3
乘客权重
0.4
最小间隔
5min
最大间隔
30min
3.算法实现
感兴趣的朋友可以私信我,一起研讨相关问题。