客运专线列车运行图编制模型及计算方法的研究_许红.pdf

《客运专线列车运行图编制模型及计算方法的研究_许红.pdf》由会员分享，可在线阅读，更多相关《客运专线列车运行图编制模型及计算方法的研究_许红.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 29卷第 2期铁 道 学 报Vol.29 No.22 0 0 7 年 4 月JOURNAL OF THE CHINA RAILWAY SOCIETYApril2007文章编号:1001-8360(2007)02-0001-07客运专线列车运行图编制模型及计算方法的研究许 红1,马建军2,龙建成1(1.北京交通大学 交通运输学院,北京 100044;2.铁道部 铁路信息化领导小组办公室,北京 100844)摘 要:列车运行图是铁路行车组织工作的基础,其编制问题属于超大规模的多目标优化问题,求解难度较大。既有线列车运行图较为成熟的编制理论和计算方法对客运专线列车运行图的编制具有重要的借鉴作用。

2、在既定客运专线运输组织模式的基础上,提出基于客运专线 A 类本线、B 类跨线和本线城际列车运行图铺划的分层叠加数学模型,研究客运专线不同种类列车的布点模型和求解方法,设计了基于改进型遗传算法的客运专线列车运行图优化策略和算法。算例表明,该算法能有效地求解客运专线列车运行图编制方案,并达到快速准确的良好效果,为编图人员提供优选方案。关键词:客运专线;列车运行图;数学模型;遗传算法中图分类号:U292.41 文献标志码:AResearch on the Model and Algorithm of the Train Working Diagramof Dedicated Passenger Li

3、neXU Hong1,MA Jian-jun2,LONG Jian-cheng1(1.School of Traffic and Transportation,Beijing Jiaotong University,Beijing 100044,China;2.Administration Office of Information T echnology of MOR,Beijing 100844,China)Abstract:T he train working diagram is the base of railway train operation organization.Work

4、ing-out the trainworking diagram is an exceptionally large-scale mult-i objects optimizing problem,and it is hard to solve withthe mathematical method.T he matured model and algorithm of train working diagram of existing railway haveimportant reference value to working-out of train working diagram o

5、f dedicated passenger line(DPL).On thebasis of the existing transport organization mode of dedicated passenger lines,this paper puts forward the layer&accumulation mathematical model of train working diagrams in consideration of own-line class A,cross-lineclass B and inter city trains of DPL,studies

6、 the trains distribution model and calculating methods of varioustypes of trains,designs the optimizing strategy and algorithm of train working diagrams of DPL based on theimproved genetic algorithm.The computational example indicates that the proposed algorithm is able to workout train working diag

7、ram schemes rapidly and accurately,thus providing optimum alternatives for the workingstaff.Key words:Dedicated Passenger Line(DPL);train working diagram;model;genetic algorithm /十一五0期间我国将建设 7 000km 铁路客运专线,其中,武(汉)广(州)、郑(州)西(安)等多条客运专线重点项目的开工建设预示着大规模客运专线建设已全面展开。列车运行图是所有与铁路行车组织有关部门工作的综合性技术文件,是铁路行车组织工作的

8、基收稿日期:2006-08-24;修回日期:2006-12-25基金项目:铁道部科技研究开发计划项目(2003X041-B)作者简介:许红(1967),女,辽宁大连人,讲师,在职博士研究生。E-mail:xuhong 础。经过三十多年的发展,国内外学者对既有铁路单线、双线、枢纽地区、网状线路及京沪高速铁路的列车运行图编制做了大量卓有成效的工作,建立了较为丰富和完善的数学理论和计算方法 1 4,所有这些对编制客运专线列车运行图具有重要的借鉴意义。根据武广、郑西等客运专线初步设计及确定的客运专线运营组织管理体制,客运专线拟采用本线列车及跨线列车共线运行、维修/天窗0为每日矩形垂直开设方式的运输组织

9、模式,设计年度运行 3 种列车,即采用 300 km/h 350 km/h 动车组的中长程本线列车(A 类本线列车)、采用时速为 200 km/h 动车组的既有提速跨线列车(B 类跨线列车)及本线城际列车。现以武广客运专线运输组织模式为基础,建立客运专线不同种类列车运行图编制的数学模型及计算方法。模型及算法的设计力求具有较强的通用性,以适应其它客运专线列车运行图的编制。1 客运专线列车运行图数学描述设客运专线 L 由车站集合S 和区间集合E 构成L=(S,E),K 为线路 L 开行方案确定的所有列车构成的集合,A K、BK 分别表示 A 类本线和 B 类跨线列车集合,ZCK 为中长程 A 类本

10、线和 B 类跨线列车集合,DCK 为本线城际列车集合,有 K=ZCK G DCK。列车 k I K 经由车站集合为SkAS,约定 i-、i+分别表示列车 k 运行轨迹中经由车站 i 的后方相邻车站和前方相邻车站,由车站 i 出发(通过)的列车构成集合 KiI K。对 Pk I K,Pe(i,j)I E 且 i,j I Sk,已知常量tcyik为列车k 在区间 e(i,j)的纯运行时分;tqik、ttjk分别表示列车k 在车站i、j 的起车、停车附加时分。tsik为列车k 在车站 i 的停站时分,Dik为 0-1 变量,若列车k 在车站 i 停站,则 Dik=1;否则 Dik=0。tsminik

11、、tsmaxik分别表示列车在车站 i 停留的最短和最长时间,tf-k,tf+k 为列车 k 的始发时间限制域。未知变量 tfik、tdjk分别为列车 k 在车站 i、j 的出发、到达时刻。对给定列车 k I K,设其始发(上线)、终到(下线)车站分别为i1、i2,定义列车运行线 Rk=(tfi1k,tfi-2k,tdi+1k,tdi2k)T,及运行线跨度$R=tdi2k-tfi1k。定义 1 对于同向列车 k1、k2,在车站 i I Sk1GSk2满足 tfik1 tfik2,若不存在同向列车 k3,使得 tfik1 tfik3 tfik2,则称 k1和 k2为车站 i 的紧行列车,k1为

12、k2的紧前行列车,k2为k1的紧后行列车,记作 k1ik2,否则,称 k1和 k2为非紧行列车。若 k1不是 k2的紧前行列车,记作 k1|ik2。定义 2 对于同向列车 k1、k2,在其运行方向上共同经由的第一个站 i0I Sk1G Sk2,满足条件 tfi0k1tfi0k2,则称 k1是 k2的先行列车,记作 k1k2,对于Pk1k2I A K,sf jk1k2为列车 k1和 k2的最小发车间隔时间。2 客运专线列车运行图分层叠加铺划模型及算法2.1 列车运行线映射关系按照客运专线 L 已定的停站方案设计,由列车运行标尺、起停车附加时分、停站时分等已知参数及列车始发(上线)时间,按列车经由

13、站可以顺序推算列车在各站的到、发时刻。对于任意列车 k I K,有如下关系tdik=tfi-k+tcyi-k+Di-ktqi-k+Dikttiktfik=tdik+tsik(1)Pk I K,i=i+1,i2 依据递推关系,代入列车始发时刻 tfi1k,即可推算出列车在各站的到发时刻tdik=tfi1k-tsik+6ij=i+1k(tcyj-k+Dj-ktqj-k+Djkttjk+tsjk)tfik=tfi1k+6ij=i+1k(tcyj-k+Dj-ktqj-k+Djkttjk+tsjk Pk I K,i I Sk(2)由式(2)可以建立起列车运行线映射 Rk=Rk(tfi1k)。2.2 A

14、类本线列车的布点模型A 类本线列车之间不存在越行关系,对于 A 类本线列车 k1k2I AK,在途经车站 i I Sk1HSk2,需满足一定的车站间隔时间,有如下关系式tdik2-tdik1Idk1k2itfik2-tfik1Ifk1k2i(3)式中,Idk1k2i、Ifk1k2i分别为列车 k1、k2在车站 i 的到达、发车间隔时间,取值主要由列车 k1、k2在车站 i 是否停站确定,概括起来包括 A 类本线列车的不同时通过车站间隔时间、同向到达间隔时间、到通间隔时间等 4。联立式(2)、式(3)可得到列车 k1与k2在车站 i的最小始发间隔时间 sf jik1,k2,由此可计算 A 类本线

15、列车 k1与 k2的最小始发间隔时间sf jk1,k2=max sf jik1,k2|i I Sk1H Sk2(4)采用随机布点方法确定 A 类本线列车运行顺序,并通过对始发时间进行调整,使列车满足最小发车间隔时间,利用式(2)顺序推点方法铺划 A 类本线列车的运行线。列车始发时间随机布点方法为,对于任意的 A 类本线列车 k I A K H ZCK,依其始发时间限制域 tf-k,tf+k 均匀分布生成始发时间 tfk。若列车的随机布点不满足最小发车间隔时间约束,需进行适当调整。设列车 k 始发时间调整量为$tfk,以调整后的A 类本线列车的布点调整量变化最小为目标构建调整模型2 铁 道 学

16、报第 29 卷 P min 6k I ZCK HAK($tfk)2(5)s.t.tfi1k2-tfi1k1 sf jk1k2Pk1 k2I AK H ZCK(6)tfi1k=tfk+$tfk Pk I AK H ZCK(7)tf-k tfi1k tf+k Pk IAKH ZCK(8)式中,目标函数式(5)表示列车始发时间调整量最小,约束式(6)为所有 A 类本线列车满足最小发车间隔时间要求,约束式(7)表示调整前后列车始发时间的关系,约束式(8)表示列车始发时间需满足始发时间域的要求。该模型是一个二次规划模型,可采用约束集方法进行求解 5。模型 PI 可能小概率存在无解的情况,若出现这种情形应

17、重新进行列车出发时间布点后再求解。2.3 B 类跨线列车的机会布线模型设 m I BK 为待铺划的 B 类跨线列车,KPm为已经铺划好运行线的列车集合,车站 i I Sm出发(上线、通过)且与列车 m 同向运行的列车集合为K Pim,列车m 的运行线 Rm取决于最早可始发时间 tfm及列车集KPm,故 Rm与tfm、K Pm存在映射关系 Rm=Rm(tfm,KPm),由此映射关系可以确定运行线跨度$Rm=$Rm(tfm,K Pm)。列车 m 运行线 Rm在区间 e(i,i+)的机会布线模型 P min tdi+m(9)s.t.tfim-tfik1Ifk1mi (10)tdi+k2-tdi+mI

18、dm k2i+m(11)tdi+m=tfim+tcyim+Ditqim+Di+mtti+m(12)式中,约束式(10)为列车 m 与紧前行列车 k1需要满足发车间隔时间要求;约束式(11)为列车 m 与紧后行列车k2需要满足到达间隔时间要求;约束式(12)表示列车 m 在区间运行的时间关系。该模型为线性规划模型,可采用单纯形法求解 5。映射关系 Rm=Rm(tfm,K Pm)的求解算法如下Step1 初始化 置站 i B=i1,tfimB=tfm,tsimB=tsminim。Step2 在 K Pim中确定紧行列车 k1ik2,使得tfik1 tfim tfik2,利用模型(P)计算 tdi+

19、m。Step3 若 tdi+mI ,转 Step4;否则,转 Step5。Step4 若 tsim=0,则置 Dim=1,i B=i-;否则tfim=tfik2+Ifk2mi,tsim=tfim-tdim,转 Step2。Step5 置 i B=i+,若 i=i2,转 Step6;否则 tfim=tdim+tsim,转 Step2。Step6 得到运行线 Rm=(tfi1m,tfi-2m,tdi+1m,tdi2m)T。在给定最早可始发时间 tfmI tf-m,tf+m 条件下,可通过如下模型 P计算 B 类跨线列车最优始发时刻tf*m,进而确定运行线 Rm(tf*m,K Pm)P min$Rm

20、(tfm,KPm)(13)s.t.tf-m tfm tf+m (14)tfim-tdim tsmaxim i=i+1,i-2(15)式中,约束式(14)用于限制发车时间,约束式(15)用于避免 B 类列车在站不被过多 A 类列车越行。求解上述模型最简单的方法为穷举法,但为加速求解速度,可扣除列车在始发站不满足车站间隔时间的时间点,剔除若干显然不利方案。2.4 本线城际列车运行图模型铺划本线城际列车运行线是在中长程 A 类本线及 B 类跨线列车运行线铺划完成之后进行。列车 l IDCK 在车站i I Sl的可发车时间域由两个因素决定:列车 l 在 i 站的可到达时间域;由列车运行顺序确定的可出发

21、时间域。这里用 Dil、Fil分别表示城际列车l 在车站 i 的可到达、可出发时间域,F1il、F2il分别为列车l 在车站i 由因素确定的可出发时间域和由因素确定的可出发时间域。如图 1 所示,由紧行列车 k1和 k2确定列车 l 在车站i 的可出发时间域 Fk1k2il=tfk1k2il,tfk2k1il,及在下一个站 i+的可到达时间域Dk1k2i+l=tdk1k2i-l,tdk2k1i+l。Fk1k2il与Dk1k2i+l由如下模型确定 P max z=tfk2k1il-tfk1k2il(16)s.t.tfk1k2il-tfik1Ifk1li (17)tfik2-tfk2k1il If

22、lk2i(18)tdk1k2i+l-tdi+k1Idk1li+l(19)tdi+k2-tdk2k1i+lIdlk2i+l(20)tdk1k2i+l-tfk1k2il=tcyil+Ditqil+Di+ltti+l(21)tdk2k1i+l-tfk2k1il=tcyil+Ditqil+Di+ltti+l(22)tfk2k1il-tfk1k2il0(23)式中,目标函数式(16)用于保证得到列车 l 在车站 i所有的可行时间域,约束条件式(17)式(20)为各种车站间隔时间约束,约束条件式(21)式(22)为列车运行时间关系约束,约束式(23)用于保证列车可行时3第 2 期客运专线列车运行图编制模型

23、及计算方法的研究 间域的存在。对于 Pk1ik2I K Pil,可通过模型(P)确定出发、到达时间域 Fk1k2il、Dk1k2i+l。若 k1|ik2I K Pil,则Fk1k2il=Dk1k2il=。有计算关系 F1il=tdx+tsil|PtdxI Dil,F2il=GPk1,k2I KPilFk1k2il,Fil=F1ilH F2il。由 i 站的可发车时间域可确定 i+站的可到达时间域 Di+l=tf x+tcyil|Ptf x I Fil,利用递推关系计算出列车 l在终点站的可到达时间域 Di2l,由此可计算列车 l 的最终可始发时间域F*i1l=tdx-6i Xi1(tcyi-l

24、+Di-ltqi-l+Dilttil+tsil)|Ptdx I Di2l(24)综合上述分析、计算,设计城际列车可行始发时间域的搜索算法如下Step1 初始化。置站 i B=i1,取 Dil=tf-l,tf+l。Step2 由列车 l 在车站 i 的可到达时间域 Dil确定时间域F1il=tdx+tsil|Ptdx I Dil。Step3 利 用 模 型(P)计 算时 间 域 F2il=GP k1,k2I KPilFk1k2il,得到列车 l 在车站 i 的可出发时间域Fil=F1ilHF2il。Step4 计算列车 l 在车站 i+的可到达时间域Di+l=tf x+tcyil|Ptf x I

25、 Fil,若 i=i-2,则转Step5;否则置 i B=i+,转 Step2。Step5 依据式(24)计算列车 l 的可始发时间域F*i1l,并选取合适的始发时间 tfi1lI F*i1l。2.5 列车运行图分层叠加铺划算法根据既定客运专线的铺划顺序及上面描述的各类列车的铺划计算方法,设计客运专线列车运行图的分层叠加铺划算法。Step1 初始化。列车进行分类,生成列车集合AK、BK、ZCK、DCK。Step2 A 类本线列车布点。Step2.1 对任意 A 类本线列车 k I A K HZCK,均匀分布在时间域 tf-k,tf+k 上,生成始发时间 tfk。Step2.2 利用 A 类本线

26、列车布点模型(P),计算列车始发时间 tfi1k,如果模型(P)无解,转 Step2.1。Step2.3 采用式(2)顺序推点计算 A 类本线列车运行线Rk|k I A K HZCK,置 KP=A K HZCK。Step3 铺划 B 类跨线列车运行线。Step3.1 置 K Pm=K P,若 BK HZCK=,转Step4;否则,选取列车 m I BK HZCK。Step3.2 采用模型(P)计算列车 m 的运行线R*m。Step3.3 更改列车集合 BK=BK-m,K P=KP+m,转 Step3.1。Step4 铺划本线城际列车运行线。Step4.1 置 K P1=K P,若 DCK I

27、,转 Step5;否则顺序选取 DCK 中列车l I DCK。Step4.2 利用列车可行的始发时间域的算法计算 F*i1l,若 l I BK,则转 Step4.3;否则,转 Step4.4。Step4.3 若 F*i1l=,则采用模型(P)计算 l 的运行线 Rl;否则,选取列车 l 合适的始发时间 tfi1lIF*i1l。Step4.4 更改列车集合 DCK=DCK-l,K P=K P+l,转 Step4.1。Step5 输出列车运行图 Rk|k I K。3 客运专线列车运行图优化计算方法客运专线列车运行图的分层叠加铺划算法是列车运行图可行解的生成算法,可行解的生成过程具有较强的随机性,所

28、求得的列车运行图铺划方案一般不是最优方案。按照分层叠加算法思想,A 类本线列车的铺划基本上确定了列车运行图的主框架,故列车运行图编制方案的优化可通过调整 A 类本线列车运行线的分布来实现。本文在尝试应用传统的分支定界或者逐步寻优方法进行优化方案时,求解效果及收敛速度都无法令人满意,甚至很难找到最优或者次优可行解。随着近代数学的发展,各种启发式方法逐渐应用到这个领域,考虑到列车运行图问题是一个规模庞大的非线性模型,0-1 规划的变量类似二进制编码,故选用遗传算法求解模型,并针对列车运行图的特殊性和具体要求,设计了改进型遗传操作策略以优化客运专线列车运行图计算方法。3.1 列车运行图的优化策略列车

29、运行图的评价指标主要包括运行图基本评价指标、旅客服务质量指标、运行图均衡性指标、可调整性指标、经济评价指标和运行图后评价指标 4。选取其中可量化的列车总运行时间、运行图均衡性和可调整性 3 种指标来评价客运专线列车运行图编制方案的优劣。客运专线列车运行图的优化目标函数可从 B类跨线列车总旅行时间最少、列车运行图均衡度高、列车运行图可调整性强等 3 个指标考虑。(1)B 类跨线列车总旅行时间最少目标函数由客运专线列车运行图的分层叠加铺划算法,B类跨线列车是在 A 类本线列车运行线基本确定的基础上开始铺划,不可避免被 A 类本线列车越行,由此4 铁 道 学 报第 29 卷B 类跨线列车途经站的停站

30、时间为不确定因素。客运专线列车运行图铺划应以提高 B 类跨线列车旅行速度、缩短旅客总旅行时间来达到提高旅客出行服务质量的目的,其目标函数为min z1=6kI BK6i2i=i+1(tcyi-k+Di-ktqi-k+Dikttik+tsik)(25)(2)列车运行图的均衡性指标函数从优化 A 类本线列车及 B 类跨线列车运行秩序出发,需分时间段对客运专线列车运行图的均衡性进行评价。设车站 i I S 的一个列车运行铺划时间周期为Ti(其值由 1440 min 与客运专线施工/天窗0时间段相减),由旅客出行规律可将 Ti分成 hi时间段,即Ti=T1iG T2iG,G Thi。设列车运行图在车站

31、 i 第 h时段列车发车间隔时间分布为 Xih=(x1ih,x2ih,xgih)T,令 Eih、Dih分别表示发车间隔时间分布期望值和方差。定义相间间隔方差 Rih为两相邻列车间隔时间与均值 2Eih的偏差程度 3,记作Rih=1gih6gih-1g=1(xgih+xg+1ih)2-Eih2(26)定义均衡性指标 Cih=Dih+H Rih(H0)。其中,H为均衡性系数,通常取 H=1。设 Kih为车站i 第h 个时段的权重系数,运行图均衡性目标函数为min C=6n-1i=16hih=1KihCih(27)(3)列车运行图可调整性指标函数可调整性指标是用来评价列车运行图消除各种随机扰动影响的

32、能力,列车缓冲时间 6是评价列车运行图可调整程度的重要指标之一。这里定义客运专线列车平均缓冲时间是 A 类本线、B 类跨线列车间隔时间与最小列车间隔时间之差。对于任意车站 i I S,列车平均缓冲时间可表示为r-i=6l I K6mI KXl mi(tdi m-tdil)-Il mi/(Ni-2)(28)式中,Xl mi为 0-1变量,当 lim 时 Xl mi=1,否则 Xl mi=0;Il mi为列车 l I AK、m I BK 在区间e(l-,i)的最小追踪间隔时间;Ni为车站 i 到达列车数量。由于列车途经的车站属性不同,给定各站一个权重系数 Ai,得到运行图可调整性目标函数max R

33、=6iI S6l I K6m I KAiXl mi(tdi m-tdil)-Il mi/(Ni-2)(29)(4)列车运行图优化的总体目标对多目标的处理方法有约束转化法、线性加权法等 4。本文采用线性加权法,赋予列车运行图优化目标函数不同的权重系数 L1、L2、L3,通过调节权重实现运行图铺划方案的优化控制,形成总体评价目标函数max z=L1/z1+L2/C+L3R(30)3.2 遗传策略首先定义遗传参数变量:种群大小 PS,最大遗传代数 T,变异概率 pm,交叉概率 pc。(1)解的编码个体编码采用实数向量编码。把 A 类本线列车按照一定顺序排列起来,取其始发时间作为求解变量进行编码 p=

34、(x1,x2,xa)T。文中的运行图分层叠加算法能够自动调节 A 类列车的始发时间,从而保证了初始个体以及个体通过遗传操作以后的有效性。(2)初始群体的产生初始群体 P(0)的个数 PS 一般取 30 50 个,也可通过试算确定。初始群体 P(0)的 PS 个体利用 A类本线列车布点模型随机产生。(3)适应度函数对每个个体采用运行图的分层叠加铺划算法求解其对应的运行图问题,并计算适应度函数F(pi)=L1/z1+L2/C+L3Ri=1,2,PS确定个体选择概率为qi=F(pi)/6iF(pi)(4)遗传操作 复制从当前代 P(t)及其子辈 Pc(t)中选取优良个体遗传到下一代,为了保持个体的多

35、样性,不允许同代具有相同的个体,取 Pd(t)=P(t)G Pc(t),设计如下复制算法。Step1 从 Pd(t)中选取适应度最高的个体 p,转Step3。Step2 计算 Pd(t)中每个个体的选择概率qi=F(pi)/6iF(pi)采用轮盘赌方法选取个体 p。Step3 更新种群 Pd(t)=Pd(t)-p,P(t+1)=P(t+1)+p。Step4 若 P(t+1)中有 PS 个体,算法终止;否则转 Step2。交叉对两个配对染色体随机选择交叉点,然后交换交叉点后的部分,从而产生两个新个体。交叉办法是:产生一个长度为 PS 的伪随机数序列,用该序列依据交叉概率 pc匹配当前群体p(k)

36、,期望选出 pc PS 个体5第 2 期客运专线列车运行图编制模型及计算方法的研究 进行交叉。把挑选出来的个体两两配对进行交叉。设配对的个体分别为 p1和 p2,则交叉操作如下Pc1=J p1+(1-J)p2Pc2=(1-J)p1+J p2(31)式中,JI(0,1)的随机数,Pc1、Pc2分别为 p1和 p2交叉产生的子辈个体。变异从群体 P(t)中依据变异概率选取部分基因进行变异。设个体 p I P(t)的第 j 基因位被选中,则可进行如下变异操作xcj=xj+$(t,xUj-xj)(32)或xcj=xk+$(t,xj-xLj)(33)式中,xUj和xLj分别为xj的上界和下界,函数$(k

37、,y)随着 k 的增加趋于 0。取$(k,y)为$(t,y)=y#r#1-tTb(34)式中,r I 0,1 的随机数;b 为确定非均匀度的参数。(5)终止操作算法的终止操作可以通过遗传代数控制,这是遗传算法通用的终止规则。遗传代数需要视问题的规模而定,另外,还可以通过计算群体的平均适应性来确定。当群体的平均适应性变化微小时,可认为遗传算法找到满意解。这里认为连续代个体的平均优良性没有太大的变化,遗传算法收敛。定义收敛精度 R,确定收敛条件6tk=t-s6PSi=1(F(pki)-F(pk-1i)s,且满足式(35)的收敛条件,转 Step8。Step4 交叉操作。依据交叉概率 pc从 P(t

38、)中选择个体配对进行交叉,把交叉得到的子辈添加到子辈集合 Pc(t)中。Step5 变异操作。依据变异概率 pm,对 P(t)中个体的基因位进行变异,变异得到的子辈添加到子辈Pc(t)中。Step6 产生下代。利用复制算法得到下一代群体 P(t+1)。Step7 若 t T,t B=t+1,转 Step3;否则,转Step8。Step8 输出最优个体对应的列车运行图 Rk|k IK,算法终止。4 算例为检验算法效果,以武广客运专线为例进行验证。该客运专线正线长度 874.4 km,共设 23 站,其中包括15 个中间站和 6 个越行站 7。根据列车开行方案等已知条件,利用计算机和人工各在列车运

39、行图上铺划126 对列车,其中客运专线本线 A 类及城际列车 101对,B 类跨线列车 25 对。A 类列车最高速度 300 km/h,B 类列车最高速度 200 km/h,最小追踪间隔时间 3min,施工/天窗0时间为 0 B00 6 B00。遗传算法参数设置为种群数量 S=30,交叉概率 pc=0.4,变异概率pm=0.05,最大遗传代数 K=50,非均匀度参数 b=0.5。式(30)中列车运行图优化目标函数系数取值为L1=10 000,L2=2 000,L3=0.05。在主频为 P2.8GHz 处理器、内存为 512 M、操作系统为 Windows XP的微型计算机上,用 Visual

40、C.net 开发平台编程实现了计算机自动编制客运专线列车运行图。用文中提出的列车运行图分层叠加铺划算法编制列车运行图平均耗时 13 s,采用改进型遗传算法对列车运行图进行优化耗时在 12 h 以内。计算机及人工编制列车运行图的指标比较结果见表 1。表 1 客运专线列车运行图指标对照指标类别指标属性遗传算法铺图随机铺图人工铺图A 类列车计划停站时间/min430430430实际停站时间/min430430430总旅行时间/min17 85517 85517 855总运行时间/min17 42517 42517 425B 类列车计划停站时间/min1 6731 6731 673实际停站时间/min

41、2 6332 7812 799总旅行时间/min10 61210 86410 950总运行时间/min7 9798 0838 1515 结论客运专线列车运行图编制问题是一项受多工种、6 铁 道 学 报第 29 卷多因素影响的重要而复杂课题。文章从客运专线运营实际出发,提出了客运专线列车运行图分层叠加铺划模型及改进型遗传优化算法。算例表明,在客运专线列车运行图分层叠加铺划模型基础上,遗传算法优化求解客运专线列车运行图问题能够达到快速准确的效果,为编图人员提供可行的优选方案。需要说明的是,文中提出的武广、郑西、京沪等多条客运专线建成后与衔接的既有提速线路将形成规模庞大的客运路网,如何将单一客运专线

42、的列车运行图模型及算法拓展到大规模客运专线路网,是今后需要深入考虑和研究的问题。参考文献:1 郑时德.铁路行车组织M.北京:中国铁道出版社,1995.2 彭其渊,朱松年.网络列车运行图的数学模型及算法研究 J.铁道学报,2001,23(1):1-8.PENG Q-i yuan,ZHU Song-nian.Study on a General Opt-imization Model and its Solution for Railway Network TrainDiagram J.Journal of the China Railway Society,2001,23(1):1-8.3 孙焰

43、.单线列车运行图优化理论及计算机编制方法 D.长沙:长沙铁道学院,1997.4 马建军.基于网状线路的京沪高速铁路列车运行图编制理论的研究 D.北京:北方交通大学,2002.5 陈宝林.最优化理论与算法M.北京:清华大学出版社,2003.6 胡思继.列车运行组织及通过能力理论M.北京:中国铁道出版社.1993.7 铁道第四勘察设计院.武汉至广州客运专线乌龙泉至花都段初步设计 R.武汉:铁道第四勘察设计院,2004.(责任编辑 李淑萍 刘梅林)下 期 要 目#高速动车组合理下线范围的决策模型及算法研究#客运专线旅客出行选择行为分析#旅客列车乘车方案优化模型研究#抗蛇行减振器对磁流变耦合轮对车辆的临界速度和 高速曲线通过性能的影响#一种基于 DAVIC 模型音视频传感器网络的体系结构#轨道结构动力分析的傅立叶变换法#预应力 CFRP 筋高性能混凝土 T 型梁试验研究与 非线性分析#大跨度公轨两用桥轨道横梁与整体节点连接疲 劳试验研究7第 2 期客运专线列车运行图编制模型及计算方法的研究