一种基于改进遗传算法的公交车辆资源调度方法

摘要

本发明公开了一种基于改进遗传算法的公交车辆资源调度方法，属于城市轨道交通技术领域。在轨道和公交应急联动疏运的过程中，采用一种改进的遗传算法来给定公交车辆资源调度方法；第一步，定义染色体编码规则，随机产生初始种群；第二步，给定各公交派车点调派车辆的最大循环疏运次数；第三步，计算染色体的适应度函数值；第四步，判定是否满足收敛准则，不满足收敛，转到第五步，满足收敛，获得最优的公交车辆资源调度方法；第五步：执行改进变异算子，产生新染色体，转到第二步。根据遗传算法的随机搜索能力可以快速地得到一个总疏运时间最短的公交车辆资源调度方法，具有很好的收敛性和鲁棒性。

说明书

技术领域

本发明属于城市轨道交通技术领域，涉及一种基于改进遗传算法的公交车辆资源调度方法。

背景技术

随着城市轨道交通的日益发展，人们自身安全意识的提高，社会对轨道交通运营的要求也越来越高。但是，如果轨道交通一旦遭遇突发事件，导致正常运营受到影响或中断时，必将对于城市居民的正常出行产生影响。所以，对轨道交通发生较长时间运营中断事件的情况和对于轨道交通运营中突然出现大量的人员聚集而无法快速疏运事件的情况，应急处理问题的意识与应急处理程序是必不可少的，有助于降低轨道交通突发事件所带来的负面影响，制定、更新相应的应对措施与应急预案，已是迫在眉睫的任务。

轨道交通网络内突发事件的发生具有完全随机性，轨道交通运营企业会针对各类具体突发事件制订应急预案。当轨道交通线网内发生较长时间运营中断事件(如中断运营30min以上事件)，或者轨道交通运营中某个站点突然出现大量人员聚集而无法快速疏运事件，通常需要启动轨道公交联动运营的方法，相应地采取“大小交路(轨道正常运营区段)+公交短驳(轨道中需要疏运人员区段)”的运输组织方式以维持城市公共交通系统的基本服务水平。

发明内容

本发明针对轨道运营发生长时间的中断事件或者轨道交通运营中某个站点突然出现大量人员聚集而无法快速疏运事件，提出了一种轨道和公交应急联动疏运的方法，该方法采用一种改进的遗传算法来给定公交车辆资源调度方法，根据遗传算法的随机搜索能力可以快速地得到一个总疏运时间最短的公交车辆资源调度方法，具有很好的收敛性和鲁棒性。

一种基于改进遗传算法的公交车辆资源调度方法，在轨道和公交应急联动疏运的过程中，采用一种改进的遗传算法来给定公交车辆资源调度方法；第一步，定义染色体编码规则，随机产生初始种群；第二步，给定各公交派车点调派车辆的最大循环疏运次数；第三步，计算染色体的适应度函数值；第四步，判定是否满足收敛准则，不满足收敛，转到第五步，满足收敛，获得最优的公交车辆资源调度方法；第五步：执行改进变异算子，产生新染色体，转到第二步。

所述变异算子，策略如下：

a:当公交派车点还有可调用车辆且从派车点往需要疏运人员的车站|L|的行驶时间小于需要疏运人员的车站|L|到指定疏运目的地车站的行驶时间时，则从公交派车点往需要疏运人员的车站|L|增派1辆车，公交车辆资源调度方案的车队规模增加1辆；

b:当所有公交派车点都没有可调用车辆且需要疏运人员的车站|S|至少派有2辆车时，从需要疏运人员的车站|S|往需要疏运人员的车站|L|调派1辆车，公交车辆资源调度方法的车队规模不变；

其中：|L|、|S|分别为当前公交车辆资源调度方法中的行驶时间最长、最短的需要疏运人员的车站。

所述收敛准则为计算当前染色体的适应度函数值和上一次染色体的适应度函数值的变化率，如果变化率不为0，则为不满足收敛准则，迭代优化；反之则为满足收敛准则，停止迭代。

所述染色体编码规则，定义如下：A代表任一个随机的公交车辆资源调度方法，X_j为各公交派车点调派车辆总数，X_ij为各公交派车点往各需要疏运人员的车站调派车辆数，公交应急联动疏运系统中有m个公交派车点、n个需要疏运人员的车站，则A的表达式为

$\left(\begin{array}{c}A=(X_1,...,X_j,...,X_m;x_{11},...,x_{i1},...,x_{n1};...;x_{1j},...,x_{ij},...,x_{nj};...;x_{1m},...,x_{im},...,x_{nm})\\ =\left(\right|{\alpha }_1{D}_1|,...,|{\alpha }_j{D}_j|,...,|{\alpha }_m{D}_m|;|{\beta }_1{X}_1|,...,|{\alpha }_1{D}_1|-\underset{i=1}{\overset{n-1}{\Sigma }}|{\beta }_i{X}_1|;...;|{\beta }_n{X}_1|,...,|{\alpha }_m{D}_m|-\underset{i=1}{\overset{n-1}{\Sigma }}|{\beta }_i{X}_m\left|\right)\end{array}\right)$

其中β_i和α_j均是[0，1]区间内的随机值，||表示取整。

有益效果

本发明采用遗传算法的染色体编码规则来给定一个可行的公交车辆资源调度方法，通过设计的改进变异算子来快速获得一个各需要疏运人员的车站中乘客疏运的最短时间所对应的公交车辆资源调度方法，使得运营企业能够及时地应急处理轨道运营中发生的长时间中断事件，及时地应急处理轨道交通运营中某个站点突然出现大量人员聚集而无法快速疏运事件，减少因轨道交通运营中断事件和其他的突发事件给出行者和社会带来的负面影响，尽量减少因轨道交通运营中断事件和其他的突发事件而造成的财产损失，人员伤亡及营运时间的影响。

附图说明

图1为本发明的改进遗传算法流程图；

图2为本发明的具体实施例背景示意图。

其中，附图2中表示正常营运车站，指定疏运目的地车站，需要疏运人员的车站。

具体实施方式

下面结合具体实施例和附图，进一步阐述本发明。

本发明的改进遗传算法流程图，如图1所示，第一步，定义染色体编码规则，随机产生初始种群；染色体编码规则，定义如下：A代表任一个随机的公交车辆资源调度方法，X_j为各公交派车点调派车辆总数，X_ij为各公交派车点往各中断车站调派车辆数，公交应急联动疏运系统中有m个公交派车点、n个中断车站，则A的表达式为

$\left(\begin{array}{c}A=(X_1,...,X_j,...,X_m;x_{11},...,x_{i1},...,x_{n1};...;x_{1j},...,x_{ij},...,x_{nj};...;x_{1m},...,x_{im},...,x_{nm})\\ =\left(\right|{\alpha }_1{D}_1|,...,|{\alpha }_j{D}_j|,...,|{\alpha }_m{D}_m|;|{\beta }_1{X}_1|,...,|{\alpha }_1{D}_1|-\underset{i=1}{\overset{n-1}{\Sigma }}|{\beta }_i{X}_1|;...;|{\beta }_n{X}_1|,...,|{\alpha }_m{D}_m|-\underset{i=1}{\overset{n-1}{\Sigma }}|{\beta }_i{X}_m\left|\right)\end{array}\right)$

其中β_i和α_j均是[0，1]区间内的随机值，||表示取整。

第二步，给定各公交派车点调派车辆的最大循环疏运次数。

第三步，计算染色体的适应度函数值，即完成所有待疏运车站全部乘客疏运所需的总时间。

第四步，判定是否满足收敛准则；计算当前染色体的适应度函数值和上一次染色体的适应度函数值的变化率，如果变化率不为0，则转到第五步；反之，算法收敛，获得最优的公交车辆资源调度方法，即完成所有待疏运车站全部乘客疏运的最短时间所对应的公交车辆资源调度方法。

第五步：执行改进变异算子，产生新染色体，转到第二步；改进变异算子，策略如下：

a:当公交派车点还有可调用车辆且从派车点往需要疏运人员的车站|L|的行驶时间小于需要疏运人员的车站|L|到指定疏运目的地车站的行驶时间时，则从公交派车点往需要疏运人员的车站|L|增派1辆车，公交车辆资源调度方案的车队规模增加1辆；

b:当所有公交派车点都没有可调用车辆且需要疏运人员的车站|S|至少派有2辆车时，从需要疏运人员的车站|S|往需要疏运人员的车站|L|调派1辆车，公交车辆资源调度方法的车队规模不变；

其中：|L|、|S|分别为当前公交车辆资源调度方法中的行驶时间最长、最短的需要疏运人员的车站。

本发明的具体实施例如图2所示，由于列车延误导致上海轨道交通9号线市郊段松江大学城站和洞泾站存在大量乘客滞留，对轨道交通的正常运营计划和乘客安全造成了一定的影响，为了减少影响，松江区抽调公交车辆对受影响乘客实施轨道和公交应急联动疏运的方法，疏运目的地为佘山站和松江新城站。

轨道和公交应急联动疏运的方法中，采用遗传算法的编码规则给定一个可行的公交车辆资源调度方法，公交派车点1的可调用最大车辆数为10，公交派车点2的可调用最大车辆数为6，公交派车点3的可调用最大车辆为9，公交派车点m＝3,需要疏运人员的车站n＝2,在α₁＝0.2，α₂＝0.1，α₃＝0.6，β₁＝0.5的情况下，公交车辆资源调度方法的表达式为(2,0,5；1,1；0,0；2,3)，给定公交车辆的最大循环疏运次数为2，计算染色体的适应度函数值，当前松江大学城站和洞泾站完成乘客疏运总时间分别需要2小时和1.2小时，因此完成两个车站乘客疏运总时间为2小时，执行改进变异算子，由于公交派车点1还有可调用车辆，且公交派车点1往松江大学城站的行驶时间小于松江大学城站到指定疏运目的地车站的行驶时间，则从公交派车点1往松江大学城站增派1辆车，公交车辆资源调度方法的表达式为(3,0,5；2,1；0,0；2,3),在改进变异算子下，得到的新公交车辆资源调度方法中松江大学城站和洞泾站完成乘客疏运总时间变化为1.6小时和1.2小时，因此完成两个车站乘客疏运的总时间缩短为1.6小时。依次循环迭代优化，直到两个车站的乘客总疏运时间不能够再缩短，获得完成两个待疏运车站全部乘客疏运的最短时间所对应的公交车辆资源调度方法。