城轨列车运行调整问题的模糊优化设计研究

魏 倩,陈永刚

(兰州交通大学自动化与电气工程学院,兰州 730070)

城轨列车运行调整问题的模糊优化设计研究

魏 倩,陈永刚

(兰州交通大学自动化与电气工程学院,兰州 730070)

城市轨道交通中列车运行的实时调整能保证系统的运营效率,因此对该问题进行研究很有必要。考虑到优化目标函数与约束条件的模糊性,建立了列车运行调整的模糊优化设计数学模型。在模型求解过程中,首先基于Zimmermann对称模型求解思想的容差法,将模糊优化模型转化为一系列确定性优化模型,然后运用MATLAB中遗传算法相关函数对模型进行求解。最后选取苏州轨道交通1号线运营数据进行算法验证,结果表明列车运行调整模糊优化模型较之普通优化模型的合理性和有效性。

城市轨道交通;运行调整;模糊优化;遗传算法

当前我国城市轨道交通正处于快速发展阶段,其客流量的增加和列车运行密度的增大对列车运行调整的质量和效率提出了更高的要求,如何恰当地描述问题和设计相应的算法是城轨行车指挥调度自动化的关键。

列车运行调整属于高维数、非线性混合整数目标优化问题[1],国内外许多学者对此问题提出了多种数学模型及优化方法,奠定了列车运行调整问题进一步研究的基础[2,3],目前线性规划、非线性规划、分枝定界法、遗传算法[4]、专家系统[5]、粒子群算法[6]等各种优化方法在列车运行调整问题上已进行了一定的应用研究,但是在城轨列车运行调整方面使用的方法很少。列车在实际运行过程中,易受到包括来自环境、列车设备、线路条件等各种不确定因素的干扰,使得列车运行过程的多种约束参数具有模糊不确定性。传统方法更多考虑的是确定变量环境下的优化问题[7],无法适应受不确定性因素影响的城轨实际运营环境。

为此,本文建立了列车运行调整模糊模型,使优化模型更接近实际情况,并运用遗传算法对该模型进行求解,可望得到更加合理的优化解,从而为解决城轨列车运行调整问题提供一种新思路。

1 模糊优化设计模型及其解法

1.1 模糊优化设计模型

模糊环境下,多约束的非线性规划模型可表示为

式中,x表示优化模型的设计变量序列;z为综合优化目标函数;A∈Rm×n,b∈Rm,c∈Rn分别代表资源约束矩阵、资源拥有向量和系数向量。

1.2 基于Zimmermann对称模型的容差法

定义第i个资源约束的最大容差为pi,资源约束的隶属度为μ1,μ2,μ3,…,μm,考虑到求解方便,本文采用线性分布的隶属函数

其隶属函数示意如图1所示。

图1 约束条件隶属函数示意

资源约束的水平截集λ可定义为

应用Zimmermann对称模型可以将式(1)转化为带有容差的形式[8]

式中,z0、z1分别表示约束条件伸缩到最大范围和未伸缩时的解。这样原模型就转化为含有m+1个约束的确定性优化模型,求解模型得到的设计方案Xλ可称为“具有λ约束水平的优化设计”。λ取不同的值,即可得到不同的最优点,但最优方案只有1个。

2 城轨列车运行调整的模糊优化设计

2.1 符号定义和基本假设

定义:设区段内车站数为m,上线列车数为n;集合S={si|i=1,2,…m}为设计区段内车站集;Q={qi| i=1,2,…m-1}为区间集;L={lk|k=1,2,…n}为计划期内待调整的列车集;d*i,k、f*i,k分别为列车lk在车站si的计划到、发时分;di,k、fi,k分别为列车lk在车站si的实际到、发时分;Ri,k为列车lk在区间[si,si+1]的最小运行时分;Ti,k为列车lk在车站si的最小停站时间;Tz为追踪运行的最小行车间隔时间;定义sgn(a,b)函数如下

本文只考虑城轨客运列车的运营情况,假设列车等级为同一等级;鉴于城市轨道交通的车站技术设备及线路条件特性,约束条件仅考虑区间运行时间、停站时间、行车间隔存在模糊性,微观层面不进行模糊松弛处理。其中约束条件中的区间运行时间按列车平均运行速度计算,设定列车在各车站的停站时间相等。

2.2 列车运行调整的确定优化设计模型

由上述分析可知,模糊优化设计模型可通过基于Zimmermann对称模型的容差法转化为确定性优化模型,因此,关键在于确定性优化模型的构建与求解。

城轨列车运行调整问题通常使用的优化准则有最小列车总晚点时间、最少总晚点列车数等[9]。这两个优化目标的数学描述可表示如下。

列车总晚点时间

总晚点列车数

本文将该双目标的规划模型转为单目标规划模型,以列车总晚点时间及总晚点列车数加权和最小作为优化目标[10],对二者赋予权重ω(0＜ω≤1),ω体现了列车运行调整时的偏重度。建立的列车运行调整的确定优化设计模型如下

2.3 列车运行调整模糊优化设计

对上述确定优化模型的约束条件进行模糊化处理,给约束条件一个松弛条件,分别为模糊约束条件中的区间运行时分、列车停站时分及列车追踪间隔时间设置容差值CR、CT、CTz,则约束松弛到最大限时的模型为

各模糊约束的取值从完全许用到完全不许用的中间过渡过程用线性隶属函数来描述。限于篇幅,仅给出区间运行时分的模糊隶属度函数,公式表示为

其隶属度函数的示意如图2所示。

图2 列车区间运行时间模糊约束隶属度函数示意

基于上述约束条件和参数的模糊性,需要对优化的目标也进行模糊处理,可用公式表示为

将目标函数及约束函数的隶属函数表达式代入公式(4)中,即得

采用遗传算法求此模型的最优解(x*,λ*)为最大隶属度λ*的模糊决策x*。求得的x*表示调整后的最优列车到、发站时分,该最优解既能降低列车晚点的影响,使列车运行尽快从无序到有序,又较好地保证了列车运行的安全性。

3 遗传算法求解模糊优化模型

本文使用遗传算法作为优化引擎求解上述模糊优化模型。根据模型的特点,定义适应度函数时,对约束条件采用无参数的罚函数方式进行处理。列车运行调整问题实质是重新确定列车时刻表的过程,因此采用整数编码方式,用从午夜零点到某个时刻所经过的秒数来代表某个时刻[11],例如:30656代表上午08∶ 30∶56。遗传编码时将水平截集因子λ与设计变量一起编码形成染色体串,相当于范围在0～1之间的新增设计变量附加在染色体串的末尾[12],则染色体编码长度为2mn+1。编码时为使λ的数量级与设计变量统一,在λ前乘一个放缩系数a=105,具体的编码格式如图3所示。

图3 遗传编码方式示意

上述列车运行调整问题的模糊优化设计求解步骤如图4所示。

图4 模糊优化求解步骤示意

4 应用算例

本算例来源于苏州轨道交通1号线运营数据[13]。选择2012年5月18日8时30分至9时30分文化博览中心至钟南街区段的实际运营数据,按上述算法步骤进行仿真。设计区段内有6个车站,其中钟南街站为折返站,列车折返时间为180 s。根据既定运行计划,该时间段内上线列车有8列。假设区段内车次号为24100503的列车在8时39分56秒到达时代广场站后因自身设备故障导致晚点120 s,需进行相应的运行调整。优化时设定权重ω=0.5,遗传算法求解时种群规模N=100,交叉概率Pc=0.7,变异概率Pm= 0.001。求解步骤如下。

(1)根据确定优化模型式(8),设定列车平均运行速度35 km/h,行车间隔560 s,停站时间40 s,应用遗传算法求得约束条件不进行松弛时的目标函数值z1= 1 387,遗传算法的运行结果如图5(a)所示。

(2)将约束条件松弛到最大,设定列车平均运行速度39.3 km/h,行车间隔540 s,停站时间30 s,使用遗传算法对模型式(9)求解得目标函数值z0=1 107,遗传算法的运行结果如图5(b)所示。

(3)将优化结果z1、z0代入模糊优化设计模型式(12)中,经遗传算法求得目标函数Z=100 000λ的值为79 640,即最优约束水平λ*=0.796 4,即在列车平均运行速度为36.8 km/h,列车停站时间为37 s,行车间隔时间为549 s时为最优调整结果。遗传算法的运行结果如图6所示。

图5 确定约束条件下经50代后解的收敛情况

图6 模糊约束条件下经100代后解的收敛情况

经表1的优化结果对比可发现,虽然约束条件松弛到最大的时候总晚点时间最小,调整结果最优,但是此时的列车平均运行速度、行车间隔、停站时间均处于极限值,实际运行过程中会存在极大风险。而在考虑约束条件的模糊性后,虽然比最高平均运行速度运行时的优化结果要差一些,但是比约束无松弛情况下的总晚点时间少,优化结果好。这样以微弱放松约束条件值,减少了系统损耗度,并使列车运行安全性得到了一定保证,达到了理想的结果。

表1 设计变量及优化结果对比

5 结语

针对传统城轨列车运行调整优化设计的局限性,建立了该类问题的模糊优化设计模型,并采用基于Zimmermann对称模型的容差法和遗传算法进行求解,先通过确定模型求取到一个可行的范围,之后再通过模糊优化模型寻求一个较优的调整策略,得到的优化结果既考虑了列车的晚点情况,又可保证列车运行的安全性及减小设备损耗值,即更贴近实际的最优调整策略。

[1] 陈雍君,周磊山.基于序优化方法的列车运行调整算法研究[J].铁道学报,2010,32(3):1-8.

[2] Cordeau J F,Toth P,Vigo D.A survey of optimization models for train routing and scheduling[J].Transportation Science,1998,32(4): 988-1005.

[3] Andrea D'Ariano,Dario Pacciarelli,Macro Pranzo.A branch and bound algorithm for scheduling trains in a railway network[J]. European Journal of Operational Research,2007,183(2):643-657.

[4] 章优仕,金炜东.基于遗传算法的单线列车运行调整体系[J].西南交通大学学报,2005,40(2):147-152.

[5] 程宇,秦作睿.列车运行调整专家系统的研究[J].铁道学报, 1992,14(2):42-50.

[6] 陈世明,赖毅平,江冀海.面向列车运行调整问题的粒子群算法研究[J].计算机应用研究,2010,27(12):4460-4463.

[7] 谢金鑫.基于模糊优化方法的高速列车运行调整问题研究[D].北京交通大学,2011.

[8] 程利军.Fuzzy资源约束非线性规划的一个有效解法[J].曲阜师范大学学报,2000,26(3):32.

[9] 李晓艳.基于Petri网模型的城市轨道交通列车运行调整方法研究[D].北京:北京交通大学,2009.

[10]张亦南.基于GA的列车自动调整算法在CBTC系统中的应用研究[D].北京:北京交通大学,2008.

[11]王宏刚,张琦,王建英,等.基于遗传算法的高速铁路行车调整模型[J].中国铁道科学,2006,27(3):96-100.

[12]张智畯,于建华,邱清水.基于自适应并行遗传算法的结构模糊动力优化[J].四川大学学报,2009,41(1):68-73.

Study on Fuzzy Optimization Design for Train Operation Adjustment in Urban Rail Transit

WEI Qian,CHEN Yong-gang
(School of Automation and Electrical Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China)

Real time adjusting on the train's running in urban rail transit can assure the operation efficiency of the whole system,so the research on this problem is very important.A fuzzy optimization model was established for train operation adjustment,considering the fuzzy characteristics of object function and restriction conditions.During the process of model solving,firstly,the tolerance method was adopted to transfer the fuzzy optimization model to a series of determined optimization model,which is based on Zimmermann symmetric model solution idea.Then the correlation functions of genetic algorithm in MATLAB were used to solve the model.Finally,the practical calculation example of the Suzhou Urban Rail Transit Line 1 was used to prove that the fuzzy optimization model for train operation adjustment is more practicable and more efficient than the normal optimization model.

urban rail transit;operation adjustment;fuzzy optimization;genetic algorithms

U231+.6

A

1004-2954(2013)03-0125-04

20120731;

20120810

国家自然科学基金地区项目(61164010)

魏 倩(1987—),女,硕士研究生,E-mail:weiqianok@ qq.com。