关键词：
⛄ 一、 遗传算法简介
1 引言
公交排班问题是城市公交调度的核心内容,是公交调度人员、司乘人员进行工作以及公交车辆正常运行的基本依据。行车时刻表是按照线路的当前客流量情况,确定发车频率,提供线路车辆的首、末车时间。它是公交企业对社会的承诺,决定着为乘客服务的水平,发车间隔越小,服务水平越高,但是公交企业投入的成本越高。行车时刻表的编制应是在满足客流需求的前提下,尽量减少不必要的投入,这是个多目标优化问题。目前,遗传算法是解决公交排班问题的有效方法之一。但在引入遗传算法的时候,普遍存在几个问题:①遗传算法过于简单,导致结果不准确,计算效率低;②模型太复杂不利于求解;③以一个统计时间段(如1小时)为模型的基本对象,得出该时间段内的均匀发车间隔,这忽略了整个时间段内的数据变化。基于以上的考虑,提出了综合改进的遗传算法应用于智能公交排班,模型同时考虑了乘客和公交公司的双重利益,最大和最小发车间隔、两个相邻的发车间隔之差以及满载率等约束条件,得出非均匀的发车时刻表,利用综合改进的遗传算法提高计算效率。
2 公交排班问题描述及数学模型的建立
公交排班的目的是确定最优或者近似最优的运营车辆的发车时刻表。公交车队按照该时刻表发车能够达到最高的运营效率和服务水平。本项目选用厦门市公交总公司思明分公交的30路运营车队作为排班对象,不失一般性,只考虑上行线路,即要优化30路车始发站的发车时刻表。线路上行方向有26个站,首班车发车时间为早上6点整,末班车发车时间为22:05分,所有运营车都在整分钟时刻发车,以距离首发时刻的时间间隔为发车时刻,选择发车时刻为决策变量,单位为分钟,在这里定义首发时刻为0分钟发车即对应早上6点发车。 一天之内的总班次为m,总时间为965分钟,最后一辆车的发车时间为第965分钟发车对应晚上22:05分发车。
由于受到数目众多的排班规则的影响,以及要达到多项指标的均衡,公交车辆排班问题变得极其复杂,在这里建立数学模型,把实际的问题抽象为数学问题。
为了更好的进行排班算法的研究,有必要对公交排班问题进行简化和假设:
1)各公交车为同一车辆类型;
2)公交车按调度时间表准时进站和出站,车速恒定,保持匀速行驶,途中没有堵车和意外事故;
3)各时段以内乘客到站服从均匀分布;
4)以分钟作为最小的时间单位;
5)实行统一票价。
2.1 建立目标函数
本文以乘客的等车时间成本最小和公交公司的运营收益最大为目标建立模型。
1)一天内乘客总的等车时间成本
总的等车时间WT’ij为:
总的等车时间成本
调查的厦门市目前平均工资水平为32343元/年.人,按照双休日休息及法定的放假时间,现在一年大概有115天的休息时间,即有250天在工作,平均每天按工作8小时计算。
平均每分钟的工资为:
则总的等车时间成本为:
式(1)- (2)中,m表示在整个调度周期内发车车次总数;n表示线路的车站总数;t表示在整个调度周期内的连续时间;ti表示第i车次的始发站发车时间(min)(i=1,2,…,m);rj表示第j站在调度周期内随时间变化的乘客到达率(j=1,2,…,n); WT’ij表示所有乘客总的等车时间(min);w’表示总的等车时间成本(元)。
2)公交公司的运营收益
公交公司的运营收益为整个收入减去整个运营成本。
分别给乘客等车时间成本和公交公司的运营收益以不同的权系数,把以上两个目标函数转化为单目标函数,使得公交优化排班问题成为一个单目标优化问题。合并后的目标函数为:
Minz=α×w′-β×R′ (4)
即
式(3)-(5)中,R’为运营收益;C为车辆运营的单位可变成本(元/车.公里);L为线路总的长度(公里);P表示统一的票价(元/人.次);α表示乘客等车时间成本权系数;β表示公交公司运营收益权系数。
2.2 模型约束条件
1)平均满载率的约束
其中:Q车容量表示车辆满载时的容量(人/车);θ表示每车平均期望满载率(0<θ<100%)。
2)最大最小发车时间间隔约束
任意相邻两车之间的发车间隔要满足最大最小发车时间间隔约束,即:
Tmin≤ti-ti-1≤Tmax (i=2,3,…,m) (7)
其中:Tmax表示相邻两车之间的最大发车间隔(min);Tmin表示相邻两车之间的最小发车间隔(min)。
3)两个相邻的发车间隔之差的约束
为保证发车时刻的连续性,任意两个相邻的发车间隔之差不宜太大,即
其中:ε表示两相邻发车间隔之差的限值。
2.3 发车时刻模型
综合以上的模型的目标函数和约束条件,最终得出公交发车时刻模型如下:
其中:
3公交排班问题的遗传算法设计
整个遗传算法的基本流程图如图1,根据公交排班的特点,对遗传算法进行了一定的改进,按如下方法进行遗传算法设计。
图1 遗传算法的基本流程图
3.1 决策变量的真实值
结合公交排班的特点,采用真实值编码方法。在这种编码方法中,个体染色体的各个基因座上的值就是决策变量的真实值。与X=[x1,x2,…,xm]T相对应的染色体X即表示为码串[x1,x2,…,xm]。采用真实值编码后,每个编码位置(基因座)的值就表示该时刻距离首发时刻的时间,单位为分钟,在这里定义首发时间为0分钟。如长度为m的编码串:(0, 3, 6,…, 965), 0表示首发时间,3表示第二趟车距首发3分钟发车,6表示第二趟车距首发6分钟发车,…,965表示第m趟车距首发965分钟发车。
针对解决公交排班问题,采用真实值编码作为染色体的基因有以下优点[6][7]:①适合于表示范围较大的数和较大空间的遗传搜索;②改善计算的复杂性,减少了编码和解码过程,提高运算效率;③便于处理复杂的决策变量约束条件。真实值编码的基因,如果一个个体中性状优良的基因片断被遗传到下一代,那么该片断在新个体中仍然是优良的。可见这种编码性质保证了遗传算法充分发挥其代代进化的特点。而用其他编码方法,一个好的基因片断复制到下一代就不一定还是好的。
3.2 约束条件的处理
数学上处理约束最优化问题时,有一类算法是通过把约束问题转换成序列化的无约束问题来进行求解。其中比较著名的有罚函数法,也称二次惩罚法[8]。作为一种有约束非线性最优化方法,其基本思想是通过建立一个新的函数把约束问题化为一系列无约束问题来处理,根据选择的惩罚项的函数形式不同又分为内点法和外点法。内点法的特点就是首先在可行域内求得一个可行的初始点,在求解过程中探索点必须保持在可行域内部。本文中运行内点法建立惩罚项。最终得到的目标函数为:
其中,z为原目标函数,f(x)是利用惩罚函数后的目标函数值,λ1、λ2、λ3、λ4>0,分别为惩罚函数作用于约束条件的系数(即惩罚系数)
3.3 适应度函数
适应度函数的设定在整个遗传算法的操作过程中占了很重要的地位。根据建立起来的目标函数来设定适应度函数。公交排班模型的目标函数是最小化问题,为了保证染色体的适应度取值为非负数,采用如下适应度函数:
F(X)=Cmax-f(X)
其中f(X)为个体的目标函数,Cmax为同一代群体中所有目标函数的最大值。
3.4 初始群体
针对公交排班的特点,采用结合先验知识产生初始群体的方法。由于乘客在时间上的分布很大程序上左右了排班的优化过程,而乘客的分布在一天内又很不均匀,一天内有几个高峰期,高峰期单位时间内到达各个车站的乘客数量会增多,这时的发车间隔应该缩短,而其他非高峰期的发车间隔应该增长。所以完全靠随机产生初始群体不能满足实际问题的需要,故应该对初始群体进行编码调整,其计算公式如下:
其中x′i是基因xi经过调整后的值,易知基因xk为收缩中心,a为(0,1)内的数,称为收缩系数。
3.5 遗传算子
3.5.1 选择算子
采用进行了修改的比较选择方法和最优保留策略。方法如下:
先比较群体P(t)中的各个个体,找出P(t)中所有不同的个体,组成中间群体,选择过程对中间群体进行选择同样选择M次可以产生新一代群体P(t+ 1)。该方法主要是作用于在遗传算法搜索的后期阶段,群体中可能有很多个体都是相同的这种情况。这时,用改进方法,新出现的优秀个体将以更大的概率复制到下一代。在公交排班的遗传算法中采用最优保存策略,该策略可保证最优个体不被交又、变异等遗传运算所破坏,直接进入下一代。可见改进的方法具有更强的局部搜索能力。
3.5.2 交叉算子
选择单点交叉[9]作为遗传算法的交叉运算,其基本过程如下: 对于按照交叉概率PC从种群中选出的某条染色体,随机地在染色体上选择一个断点,交换双亲上断点的右端,生成新的后代。
3.5.3 变异算子
采用均匀变异操作。其基本过程如下:依次指定染色体当中的基因座为变异点,对每个变异点以很小的变异概率从对应基因的取值范围内取一个均匀分布的随机数来代替原来的基因。由于求的是非均匀发车时刻,且以每一时刻作为染色体的基因,故染色体中任一基因xk的取值范围是(xk-1,xk+1),则变异后的新基因值x′k为:
x′k=xk-1+r×(xk+1-xk-1)
式中,r为(0,1 )内均匀分布的一个随机数。
⛄ 二、部分源代码
clear;clc;close all
%% 载入模型参数
LoadData();
%% 参数设置
PopSize = 50;
MaxGen = 100;
plt = 1; % 运行过程是否实时画迭代优化图，默认关闭(可极大提高运行速度)
%% 初始化
Population = Init(PopSize);
ConvergenceObj = zeros(2,PopSize);
ConvergenceCon = zeros(2,PopSize);
% return
%% 开始优化求解
h = figure();
for gen = 1:MaxGen
MatingPool = randperm(PopSize,PopSize); %父代挑选
Offspring = GA(Population(MatingPool)); %进行交叉变异操作
Population = EnviornmentalSelection(Population,Offspring,gen/MaxGen); %挑选子代
RecordInfo(); % 记录迭代优化信息
end
BestSol = BestInd(end);
disp([‘发车时间间隔：’ num2str(BestSol.decs)])
disp([‘时段发车数量：’ num2str(floor(60./BestSol.decs))])
disp([‘乘客总时间成本:’ num2str(BestSol.Q) ‘, 公交公司运行费用:’ num2str(BestSol.G)])
disp([‘总体载客率：’ num2str(100*BestSol.zaikelv) ‘%’])
figure
yyaxis right
plot(BestSol.decs,‘-s’,‘linewidth’,2)
ylabel(‘发车时间间隔/分钟’)
hold on
yyaxis left
plot(bus.C,‘-d’,‘linewidth’,2)
ylabel(‘客流量’)
xlabel(‘时段’)
⛄ 三、运行结果
⛄ 四、 matlab版本及参考文献
1 matlab版本
2014a
2 参考文献
[1]王庆荣,朱昌盛,梁剑波,冯文熠.基于遗传算法的公交智能排班系统应用研究[J].计算机仿真. 2011,28(03)
3 备注
简介此部分摘自互联网，仅供参考，若侵权，联系删除
优化调度基于matlab遗传和模拟退火算法求解码头泊位分配调度优化问题含matlab源码247期
一、遗传算法简介1引言2遗传算法理论2.1遗传算法的生物学基础2.2遗传算法的理论基础 查看详情
优化调度基于matlab遗传算法求解孤岛型微电网（成本最低）调度优化问题含matlab源码1163期(代码片段)
...2遗传算法的特点和应用遗传算法是一类可用于复杂系统优化的具有鲁棒性 查看详情
优化调度基于matlab遗传算法求解工件的并行调度组合优化问题含matlab源码2234期
⛄一、遗传算法简介1问题描述假定一个加工系统有m台机器和n件工件，每个工件包含一道或多道工序,工件的加工顺序是确定的,但每个工件可能有几条可行的加工路线,即每道工序可在多台不同的机床上加工,工序的加工时间和... 查看详情
优化调度基于matlab改进的遗传算法求解风电场优化调度问题含matlab源码1245期(代码片段)
...规模MaxGen=1000;%遗传代数ChromLen=10;%编码长度N=16;%优化变量个数LLimits=0;%优化变量的下限HLimits=0.33;%优化变量的上限Chrom=round(rand(PopSize,N*ChromLen));%随机产生初始种群的染色体fork=1:MaxGenfors=1:PopSize%种群产生m=... 查看详情
优化调度基于matlab非支配排序遗传算法求解车辆充电调度优化问题含matlab源码2000期(代码片段)
一、遗传算法简介由于国内外人民的生活方式和电动汽车主要购买人群的不同，国内外关于车辆充电调度问题研究的侧重点也不尽相同。我国地大物博，人口众多，交通复杂。主要从以下方面研究：1、通过经济手... 查看详情
matlab基于多层编码遗传算法的车间调度算法matlab优化算法十九(代码片段)
...遗传算法具有较强的问题求解能力，能够解决非线性优化问题。遗传算法中的每个染色体表示问题中的一个潜在最优解，对于简单的问题来说，染色体可以方便地表达问题的潜在解，然而，对于较为复杂的优... 查看详情
matlab基于多层编码遗传算法的车间调度算法matlab优化算法十九(代码片段)
...遗传算法具有较强的问题求解能力，能够解决非线性优化问题。遗传算法中的每个染色体表示问题中的一个潜在最优解，对于简单的问题来说，染色体可以方便地表达问题的潜在解，然而，对于较为复杂的优... 查看详情
中文翻译成英文（数学方面的）
...下就放上来：遗传算法作为一种有效的随机搜索方法，在优化方法中具有独特的优越性，有着非常重要的意义和广泛的应用领域。本文从遗传算法算法的基本概念、特点、基本原理、主要步骤以及应用关键等方面系统的介绍了遗... 查看详情
车间调度基于matlab遗传算法求解车间调度问题含matlab源码1396期(代码片段)
一、车间调度简介1车间调度定义车间调度是指根据产品制造的合理需求分配加工车间顺序，从而达到合理利用产品制造资源、提高企业经济效益的目的。车间调度问题从数学上可以描述为有n个待加工的零件要在m台机器上加... 查看详情
指派问题基于matlab遗传算法求解指派优化问题含matlab源码2292期
⛄一、遗传算法求解指派优化问题简介1遗传算法1.1遗传算法简介遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法,它是一种多学科融合交叉的产物。遗传算法通过合理的编码机制和... 查看详情
指派问题基于matlab遗传算法求解指派优化问题含matlab源码2292期
⛄一、遗传算法求解指派优化问题简介1遗传算法1.1遗传算法简介遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法,它是一种多学科融合交叉的产物。遗传算法通过合理的编码机制和... 查看详情
车间调度基于matlab遗传算法求解车间调度问题（含甘特图）含matlab源码2216期(代码片段)
⛄一、车间调度简介1车间调度定义车间调度是指根据产品制造的合理需求分配加工车间顺序，从而达到合理利用产品制造资源、提高企业经济效益的目的。车间调度问题从数学上可以描述为有n个待加工的零件要在m台机器上... 查看详情
作业调度基于matlabgui遗传算法求解车间作业调度问题（获益最大）含matlab源码2025期
一、车间调度简介1车间调度定义车间调度是指根据产品制造的合理需求分配加工车间顺序，从而达到合理利用产品制造资源、提高企业经济效益的目的。车间调度问题从数学上可以描述为有n个待加工的零件要在m台机器上加工。... 查看详情
车间调度基于matlab改进的遗传算法求解车间调度问题含matlab源码h002期(代码片段)
一、车间调度简介1车间调度定义车间调度是指根据产品制造的合理需求分配加工车间顺序，从而达到合理利用产品制造资源、提高企业经济效益的目的。车间调度问题从数学上可以描述为有n个待加工的零件要在m台机器上加... 查看详情
路径规划基于matlab遗传算法公交排班系统分析含matlab源码220期(代码片段)
...举措就是其中一个比较好的方法，通过限号操作，步行坐公交车的人数增多，那么怎么解决公交 查看详情
优化调度基于matlab粒子群算法求解经济调度优化问题含matlab源码1489期
一、粒子群算法简介1引言自然界中的鸟群和鱼群的群体行为一直是科学家的研究兴趣所在。生物学家CraigReynolds在1987年提出了一个非常有影响的鸟群聚集模型，在他的仿真中，每一个个体都遵循：避免与邻域个体相撞：匹配邻域... 查看详情
优化调度基于matlab帝国企鹅算法求解航空调度优化问题含matlab源码yxs001期
一、帝企鹅算法简介目前，关于帝企鹅算法在国内外研究较少，在中对该算法进行了分析，并且与常见的粒子群算法、萤火虫算法进行了对比分析.帝企鹅从事各种活动，如狩猎、群体觅食，是群居性动物.每当... 查看详情
优化调度基于matlab帝国企鹅算法求解航空调度优化问题含matlab源码yxs001期
一、帝企鹅算法简介目前，关于帝企鹅算法在国内外研究较少，在中对该算法进行了分析，并且与常见的粒子群算法、萤火虫算法进行了对比分析.帝企鹅从事各种活动，如狩猎、群体觅食，是群居性动物.每当... 查看详情