专业化分工粒子群优化算法在地铁列车运行调整中的应用

刘小玲，孙 波，薛 亮，2

（1.辽宁省交通高等专科学校 轨道交通工程系，辽宁 沈阳110122；2.大连理工大学 交通运输学院，辽宁 大连116024）

运输调度工作是地铁运营企业日常运输组织的中枢，它是地铁能够正常开展行车组织工作任务的决定因素。当运营过程中列车运行偏离了计划运行图时，就必须进行列车运行调整。地铁系统是一个庞大而复杂的系统，要解决该系统的列车运行调整问题，使之尽快恢复运行图行车，有很多影响因素值得分析。目前，最优化方法和智能计算方法是解决这类问题的主要方法。采用最优化方法时必须先对列车运行调整问题复杂的模型进行简化，多项式计算量极其庞大，同时，导致最后结果与现实出现一定偏差。智能计算方法中最主要的是遗传算法（GA）和粒子群优化（PSO）算法。遗传算法在智能优化方法中应用极为广泛，它以生物进化为原型，具有很好的收敛性，在计算精度要求时，计算时间少、鲁棒性高，但在解决大规模计算量问题时，它很容易陷入“早熟”。粒子群优化由于其算法简单、无需梯度信息、参数少、易于实现等特点，在解决多目标优化、约束优化、动态优化问题上表现出良好的性能特征。然而，基本粒子群优化算法在解决列车运行调整问题时，因为该问题具有多个约束条件和庞大的搜索空间，因此基本PSO算法也因在其求解时易陷入死循环而很难得到最优解。基于专业化分工策略的粒子群优化算法（Division of Specialization PSO，DSPSO）是在PSO算法的基础上，将基于专业化分工的策略引入PSO算法中，使算法的性能得到提高，能较好地适应复杂的实际环境。本文针对地铁列车运行调整问题提出一种基于专业化分工的粒子群算法，从而达到快速寻优、提高求解质量和收敛速度的目的。

1 算法描述

1.1 基本粒子群优化算法

算法的基本原理描述如下:

一个群体由m个粒子组成，它以一定的速度在n维搜索空间中飞行，搜索时，每个粒子在考虑到了自己和群内（或领域内）其他粒子搜索到的历史最好点的基础上，进行了位置（状态，也就是解）的变化。

第i个粒子的位置表示为:Xi＝ （xi1，xi2，…，xin），（i＝1，2，…，m）。

第i个粒子的速度表示为:Vi＝ （vi1，vi2，…，vin），（i＝1，2，…，m）。

第i个粒子经历过的历史最好点（最好适应值）表示为:Pi＝ （pi1，pi2，…，pin），（i＝1，2，…，m）。

在给最小化问题求解时，需要对应较小的目标函数值，才能得到较好的适应值。因此，将目标函数设为f（x），i粒子所经过的当前最好点表示为下式

群体中所有粒子经历过的最好点由Pg（t）表示，即为种群全局最好位置。则

有了上述定义，Kennedy和Eberhart两人提出了基本粒子群算法的位置和速度进化方程，可表示如下

式中:1≤i≤m，1≤j≤n，t为循环迭代次数；c1为“认知”加速常数；c2为“社会”加速常数；r1，r2为（0，1）间相互独立的随机数。

1.2 基于专业化分工策略的粒子群优化算法

基于专业化分工策略的粒子群优化算法（DSPSO）的群体是基于“开采者”和“搜索者”的不同专业化分工而划分的。DSPSO是在基本粒子群优化算法的基础上将粒子群的群体优势充分发挥，并加以利用，使之在复杂的环境中能更好地适应。

基于专业化分工的粒子群优化算法具体描述如下:

将m个粒子组成的群体分成子群体S1（开采者1）、S2（开采者2）、S3（搜索者），各子群体包含的粒子数分别为m1，m2，m3，m＝m1＋m2＋m3。每一个子群体对应一个进化方程，S1子群体的进化方程收敛速度较快，作用是使局部寻优能力得到提升；S2子群体的进化方程是c1＝0时的“社会模型”；S3子群体的进化方程作用是全局搜索。具体的进化方程如下

子群体S1:

子群体S2:

子群体S3:

1.3 基于专业化分工策略的粒子群优化算法优势分析

文献［4］中对几种改进的粒子群优化算法进行对比分析，一是基于专业化分工策略的PSO（DSPSO）、基于线性递减权策略的PSO（LDWPSO）和经典PSO（CPSO）三种算法对经典函数Sphere和Griewank的寻优性能进行测试，试验结果表明，基于专业化分工策略的粒子群优化算法在寻优精度和搜索快速上都优于其余两种方法；二是DSPSO、保持粒子活性的改进PSO（IPSO）和具有局部参数的PSO（LPSO）三种算法对经典函数Sphere和Griewank的性能进行测试，试验结果表明，DSPSO较其余两种算法在全局和局部寻优能力上均有较为优异的表现，同时兼具较小计算量、勿须判断比较、固定参数、易于实现的优势。

2 建立模型

列车运行调整的意思是在某个区段和时间内，列车运行秩序发生混乱，列车实际运行偏离了运行图计划时，通过调整的方式使列车运行尽快恢复至计划运行图。在城市轨道交通系统中，一般来说，列车等级相同，各站的上、下行停站时间固定，运行过程中没有会让和越行，因此，在建立列车运行调整模型前，相关定义表示如下:

设某线路上有一包括M个车站的区段，该区段内有N列（N1表示上行列车的数量，N2表示下行列车的数量，N1＋N2＝N）车运行，D实际ij、F实际ij分别表 示 第i（i∈ ｛1，2，…，N｝）列 车 在 第j（j∈｛1，2，…，M｝）个 车 站 的 实 际 到 达、出 发 时 刻，D计划ij、F计划ij分别表示第i（i∈｛1，2，…，N｝）列车在第j（j∈｛1，2，…，M）｝）个车站的计划到达、出发时刻。

设运算函数为kji（即列车晚点的标志函数），如下式表示

在最短的时间内将晚点列车的数量和晚点时间影响降到最小是列车运行调整问题最根本的目标，达到此目标就能使列车尽快的恢复运行图行车。故而，将该问题数学模型的两个优化目标表示如下

目标1（即F1）:最小的晚点列车总时间

目标2（即F2）:最小的晚点列车总数目

本文以上述两个目标最小为优化目标，建立模型，其目标函数表示如下

式中:q1为晚点时间的加权因子；q2为晚点列车数量的加权因子。

列车运行调整旨在使偏离计划运行图的列车尽快恢复计划运行图运行，与目标函数F表示的意义一致，即使多目标优化问题的加权和最小。应用DSPSO算法来求解列车运行调整这个多目标优化问题时，若其适应度函数的适应值越小，则体现出来的是其列车晚点总数量和总时间也就越少，从而晚点列车的实际到达、出发时刻也就越接近计划运行图的到达、出发时刻，故本文将适应度函数fitness（f）定为F，表示如下

鉴于实际地铁列车运行的独特性质，故将其约束条件表示如下:

约束1:区间运行时间

式中:Qi，j＋1为第i站至第j间最小区间运行时分。

约束2:发车时间

约束3:列车追踪间隔时间

式中:ΔT为列车追踪间隔时间。

约束4:最小站停时间

式中:MTij为列车i在j站的最小站停时间。

3 基于专业化分工策略的粒子群优化算法求解列车运行调整问题

本文采用基于专业化分工的粒子群优化算法对列车运行调整问题模型进行求解，详细的算法步骤描述如下:

第1步:在初始化范围内，对粒子群进行随机初始化，包括各粒子的随机速度和位置、粒子群群体的规模和数目；

第2步:计算各粒子的适应值，对于各粒子，设定其个体最优值Pi，同时得到种群全局最优值Pg；

第3步:相关参数的设置，即系数q1，q2，各子群体具有的粒子数m1，m2，m3，最大迭代次数T；

第4步:分别按照式（5）、（6）、（7）及（4）更新各子群体的粒子位置和速度，通过进化（即迭代）得到粒子群群体新个体；

第5步:按照式（12）对各粒子适应值进行评价，比较其适应值与初始的个体最优值Pi，若更好，则将其作为当前最优值Pi；

第6步:将得到的所有最优值Pi和Pg进行比较后，对Pg进行更新；

第7步:如没有达到终止条件，则转到第3步；如达到终止条件，则搜索结束，将得到全局历史最好结果输出；

第8步:将最优值所对应的列车到达和出发时刻输出，从而得到列车运行调整的最终方案。

4 实 例

本文采用 Visual Basic 2012作为编程工具，选取数据为沈阳地铁2号线某工作日三台子站至白塔河路站这一区段为例，该区段内车站数目M＝18，列车数目N＝26，上行列车数N1＝13，下行列车数N2＝13。粒子数目设定为m＝30，各子群数m1＝6，m2＝9，m3＝15，迭代次数终止值为T＝300，q1＝0.8，q2＝0.2。现考虑上行方向，该区段内列车运行时间从6:00～9:00，计划运行图如图1所示，以208次在岐山路站上行站台出发时晚点130s为例，运用DSPSO计算后的调整结果在时刻表编辑软件Hustas上仿真模拟，得到调整后的列车运行图如图2所示，208次的计划时刻表和调整后时刻表如图3、图4所示。

图1 计划运行

图2 调整后运行

图3 计划时刻

图4 调整后时间

由图3和图4分析208次列车在各站的到达、出发时刻，可以看出当其运行到岐山路站上行站台时，其实际出发时间比计划晚了130s，即由7:07:42～7:09:52。此时经基于专业化分工的粒子群优化算法计算，并根据其结果调整后，列车在满足各项约束条件的前提下，在运行过程中就逐步缩小了晚点时间，直至其在奥体中心站上行站台发车时晚点0s，已正点运行，即恢复计划运行图运行。由此可见，DSPSO算法在求解列车运行调整问题时能较快地解决晚点现象，且收敛速度快，求解质量高，避免了延迟传播。

5 结束语

由于地铁列车运行调整问题约束多，搜索空间大，可行解范围小，因而总是难以获得最优解。因为列车运行调整问题有如此特性，故本文为了求解该问题提出了DSPSO算法，即将粒子群体划分为几个子群体，充分利用子群体的优势，将子群体进行专业化分工，他们之间通过信息交换来协调工作，各个子群体通过不同的进化方程，各司其职，使得收敛速度得到提高，从而获得更具可行性的结果。

［1］ 汪定伟，王俊伟，王洪峰，等.智能优化方法［M］.北京:高等教育出版社，2007.

［2］ Lars Junghans，Nicholas Darde.Hybrid single objective genetic algorithm coupled with the simulated annealing optimization method for building optimization［J］.Energy and Buildings，2015，1（86）:651－662.

［3］ 王瑞峰，孔维珍，詹生正.杂交粒子群算法在列车运行调整中的应用研究［J］.计算机应用研究，2013（6）:1721－1723.

［4］ 李洪亮，侯朝桢，周邵生.一种高效的改进粒子群优化算法［J］.计算机工程与应用，2008，44（1）:14－16.

［5］ 高立群，任苹，李楠.基于混沌粒子群算法的高速旅客列车优化调度［J］.东北大学学报:自然科学版，2007（2）:176－192.

［6］ 杨东，江雨星，宋岩.城市轨道交通列车开行方案优化模型研究［J］.交通科技与经济，2014，16（5）:38－42.