考虑动车组周转和到发线运用的高速铁路列车运行图优化方法
第33卷，第2期中国铁道科学2012年3月C H I N A R A I LW A Y S C I E N C E
V O}．33N o．2 M a r c h，2012
文章编号：1001-4632(2012)02—0107—08
考虑动车组周转和到发线运用的高速铁路
列车运行图优化方法
史峰，魏堂建，周文梁，罗湘
赞美老师的诗句和名言(中南大学交通运输工程学院，湖南长沙410075)
摘要：以列车在车站的作业时间、动车组在终点站的接续时间和车站到发线数量为约束条件，以列车旅行时间和动车组接续时问最小化为目标函数，建立高速铁路列车运行图综合优化模型。模型求解算法主要采用了4种关键技术：以定序列车运行图优化方法化解列车作业时间冲突，以交换列车到发顺序化解到发线冲突，通过保持到发线运用紧张时段的列车到发顺序防止产生新的到发线冲突，运用匈牙利算法求解以动车组最小接续时间为目标的动车组周转方案。算例分析表明，运用给出的模型和算法能够达到整体优化高速铁路列车运行图的目的。
关键词：高速铁路；列车运行图；动车组周转；到发线运用．
中图分类号：U292．41文献标识码：A doi：10．3969／j．i s sn．1001—4632．2012．02．19
随着武广、郑西、京沪等高速铁路的陆续建成和投入运营，我国铁路客货运输能力均得到比较明显的提升，而高速铁路列车运行图也成为许多专家学者关注的重点。Szpi gel[1]首次以列车旅行时间最小为目标，以列车会让、越行间隔时间为约束建立运行图优化的线性规划模型。H i ggi ns等[2]以列车旅行时间最小为目标建立了单线区段列车运行图优化模型。周磊山等[3]设计了一种统一布点、按列车优先级分层、按各区间端点列车事件的状态，并行触发区间列车事件状态转移算法计算列车运行时刻表。史峰和周文梁等[4。5]通过铺画初始松弛列车运行图确定列车在各个车站的作业顺序，然后运用定序优化方法进行列车运行图优化。马建军等[6]构建了基于京沪高铁的网状线路双层表示法。谢美全等[7]在分析周期性运行图特点基础上，建立了基于定序的周期性运行图优化模型。Zhou等[8]考虑了列车启动和停车附加时分，提出多模式时空资源约束的运行图优化方法。
在列车运行过程中，每当列车进站停车时，都会伴随着一系列的车站作业，一些学者将车站作业与列车运行图综合考虑进行优化。C ar ey等[9‘10]研究了铁路路网上运行图编制与车站径路安排的综合优化问题。L e e等[11]设计了运行图与车站径路综合优化的启发式求解算法。Car ey等[12]研究了大型枢纽站列车作业时刻与到发线安排的综合优化问题。祝建平等[13]采用网络协作方式将运行图编制与车
站技术作业安排以及机车交路勾画问题有效结合起来。史峰等[14]在考虑列车运行图基础上建立了旅客列车过站径路优化的0—1规划模型。在动车周转方面，张才春和陈建华等[15]设计了以动车组数量最少和动车组总检修时间最小为目标函数的动车组运用计划优化模型。
百里挑一于淼
本文基于文献E4]的研究成果，结合动车组接续以及车站到发线运用情况，建立高速铁路列车运行图优化模型。设计的模型求解算法包括4种关键技术：基于定序列车运行图优化方法，化解列车作业时间冲突；通过交换列车作业顺序，逐步化解到发线冲突；通过保持到发线运用紧张时段周边的列车到发顺序，防止新的冲突产生；运用匈牙利算法求解动车组周转方案。采用设计的模型和算法，进行高速铁路列车运行图的优化，达到整体优化高速铁路列车运行图的目的。
收稿日期：2011—09—23；修订日期：2011—12—06
基金项目：国家自然科学基金资助项目(71171200，70901076)；中南大学自由探索计划项目(20l l Q N Z T063)作者简介：史峰(1956～)，男，湖南芷江人，教授，博士生导师。
108中国铁道科学，第33卷
1考虑动车组周转和到发线运用的列车运行图优化问题
高速铁路列车运行图由各次列车在每个车站的到达、出发和通过时刻所组成。它反映列车进入区间的
顺序，满足区间运行时间以及车站的到达、出发或通过作业之间的间隔时间，每组列车在一定时段内满足周期性，同时还满足列车过站径路的相容性。
列车过站径路由进站进路、到发线和出站进路组成。列车过站径路的相容性是指不同列车的过站径路在时空上不产生冲突，由于进、出站咽喉区具有足够多的平行进路，所以冲突主要体现在到发线的数量上。一般情况下，双向列车的到发线是分开使用的，分别铺设在正线的两侧，除非列车在中间站终到折返，才会从反向到发线接发列车，这时就会产生跨正线的接发列车作业。当然，设备故障时也会借用反向到发线。
列车在车站的到达、出发或通过作业之间需满足追踪间隔时间，在反向到发线接发列车时，由于跨越正线作业，故应与相向通过列车之间保持会车间隔；相向到达列车之问由于是平行径路，并且车速较慢，则可以同时进行作业。
在铺画高速铁路列车运行图的过程中，不论是列车停站时间、区间运行时问、追踪间隔时间、会车间隔时间得不到满足，还是车站到发线数量得不到满足，都需要调整列车的到发时刻、发车顺序，或者变更停站，以确保列车运行图的相容性。
2列车作业时间相关约束分析
记高速铁路的车站集为S一(S。，S。，…，s。)，从5，至s。为下行方向，下行方向区间集为E一{(&，5^+1)，忌一1，2，…，，2—1)，下行列车集为T一{t i，i一1，2，…，i r r／)，t。为下行列车；从S。至s，为上行方向，上行方向区间集为E一{(&，5^一1)，k一2，3，…，咒)，上行列车集为T一{t j，J一1，2，…，m)，t j为上行列车。
记列车运行图的铺画时间周期为P(铺全天运行图时取P一1440m i n，也可取P一2880r ain／2等其他单位或时间段)，作业之间的间隔时问通常借助差的模运算，即
ae b—f n—b+P、m odP(1)
设下行列车t i在车站St的到达、出发作业时间分别为z2和z￡；上行列车￡i在车站S。的到达、出发作业时问分别为强和y盖。在不引起混淆的情况下，也视z&和y盔为相应的到达作业，z&和y量为相应的出发作业。
对于下行列车t i，记其始发站和终到站的序号分别为O i和di，始发时间域为[月，六]，在区间(靠，S。+。)的启动附加时间、纯运行时间和停车附加时间分别为以‰，^+1)，礤蹦+”n‰t+1)，由此可得下行列车区间运行时间为
ai(k，k-F1)2＆aq(k，蚪1)+n‰，k-F1)+&(k-F1)ai t(^，h-k-1)
(2)式中：如为列车t。在车站S。的停站标志变量，若列车t i在5。停车，则&一1，否则乩一o。
对于车站St的下行列车作业，记发车追踪间隔时间为《，接车间隔时间为矗，先后占用同一条到发线的列车发玛间隔时间为r{d，下行列车t。的最小停站时间为r*。
，对于上行列车t j，记其始发站和终到站的序号分别为O j和dJ，始发时间域为[片，力]，在区间(跏5k-，)的启动附加时问、纯运行时问和停车附加时问分别为口‰卜¨口沁卜帅n池卜…由此可得上行列车区间运行时间为
aj(k，k--1)一颤口扎，k-1)+n炙女，k--1)+国(蚪1)qt(^，k--1)
(3)式中：蕞为列车t f在车站S。的停站标志变量，若列车t i在s。停车，则否垃一1，否则否琥一o。
对于车站St的上行列车作业，记发车追踪间隔时间为最，接车问隔时问为蠢，先后占用同一条到发线的列车发到间隔时间为甜，上行列车t j的最小停站时问为；请。
由此可得上下行列车作业时间约束条件如下。
(1)区间运行时间约束：
zd料1ez囊一ai(k，蚪1)
i一1，2，…，m；k一0i，…，di一1(4)强一1e如一aj(女，H)
J一1，2，…，仇；k—O j+1，…，d，(5)
(2)停站时间约束：
z￡e z&≥孙
i一1，2，…，m；k—O i+1，…，di一1(6)颤e壤≥瓢
J一1，2，…，m；志一O j+1，…，d，一1
(7)
(3)追踪间隔时间约束：
第2期考虑动车组周转和到发线运用的高速铁路列车运行图优化方法109
zk e z￡≥《
i，i7—1，2，…，m；
尼一m i n{oi，O i，)，…，m ax{di，矗，)一1(8)如G蟊≥云
歹，J’一1，2，…，m；
志一m ax{o,，O j，)，…，rai n{以，匆，}+1(9)
(4)到站间隔时间约束：
z六e z&≥矗
i，i7—1，2，…，m；
忌一m ax{oi，O L}，…，m i n{di，di，)(10)识e强≥趔
歹，J’一1，2，…，优；
尼一r ai n{oj，O j，)，…，m ax{dj，西，)(11)
现代植物小短诗(5)发车时间域约束：
0≤z：j e月≤六O月
i一1，2，…，m(12) 0≤正。o月≤力e力
歹一1，2，…，m(13)
(6)停站标识与到发作业时间的整数约束：&一{0量荔
i一1，2，…，优；忌一O i+1，…，di一1
(14)
瓦一彳；曼霎妻
歹一1，2，…，m；忌一o，+1，…，d，一1
(15)
z&，z砘f一0，1，…，P
i一1，2，…，m；是一O。，…，di(16)弭，吐一0，l，…，P
J一1，2，…，m；忌一oj，…，Z(17) 3动车组周转约束分析
从动车组接续的角度来看，始发列车需要由出库或终到列车提供，终到列车需要入库或者转为反向始发列车。假设相同运行区段的列车是成对的，则列车的终到站也是接续列车的始发站。对于线路的中间站，列车由终到变为始发时，到发线的选择可以同向到达、反向发车，也可以反向到达同向发车。列车在终到站的接续问题和在线路中间站终到折返的到发线选择问题，都使得双向运行图关联起来。设列车交路接续变量为U口，蚴，t i∈T，t j∈f，若上行列车t j接续下行列车t i，则U i一1，否
则u／j—o；若下行列车t。接续上行列车t J，则球一1，否则功i—o。这里扩展i和歹取值为0分别表示列车入库或出库。
由此可得动车组周转约束条件如下。
(1)列车接续变量取值约束：
ui j一0，1i，J一0，1，2，…，优(18)
嘞一0，1i，J一0，1，2，…，m(19)
(2)动车组交路接续约束：
∑蝴一1i一1，2，…，m(20)
j=o
∑％一1J一1，2，…，m(21)
i=0
∑功i一1i一1，2，…，m(22)
j=o
∑球一1J一1，2，…，仇(23)
(3)接续变量U#和％相应接续时间C#和云直约束：-
f珐，@z刍i t i到站后转为t j
c／j—J r7．t i人出
一<r吐人出
I；7n￡J出库
di—oj；忌一1，2，…，72(24)
fz：i e，t j到站后转为t i
c—j i—j≠7爿．t j入库
一<r砘人库
r7机t i出库
dj—O i；尼一1，2，…，行(25)式中：r7．和r7i．分别为下行列车从下行到发线至车库、车库至下行到发线的时间；；7F，和；7扣．分别为上行列车从上行到发线至车库、车库至上行到发线的时问。
(4)接续列车的到发时刻衔接约束：
鼢。一强，，∞；一站i
U o一1；i，歹一1，2，…，m(26)蟪一z：i，或一z：i
％一1；i，歹一1，2，…，m(27)
(5)入库的终到列车或出库的始发列车间的到发时刻衔接约束：
z‰e∞。一r7吐
U∞一1；i一1，2，…，m(28)也，o x。d。一r7。
矾i一1；i一1，2，…，m(29)如i e娼，一r-f砖
口，o一1；i一1，2，…，m(30)
110中国铁道科学第33卷
颤，e以，一；7“
U o；=1；J一1，2，…，m(31)
(6)下行列车终到后转为上行始发列车时，在车站最小停站时间约束：
吐，Gz趁≥／咄
％一1；i，歹一1，2，…，m(32)式中：／d．为下行列车终到后转为上行始发列车时的车站最小停站时间。
(7)上行列车终到后转为下行始发列车时，在车站最小停站时间约束：
z‰e娼，≥以，
％一l；i，歹一1，2，…，m(33)式中：／村．为上行列车终到后转为下行始发列车时的车站最小停站时间。
(8)列车交路不能在不同车站接续折返约束：
‰一0di≠O j；i，』一1，2，…，m(34)入党之后可以出国吗
％一0di≠O i；i，J一1，2，…，m(35)
(9)设上、下行列车终到时到发线选择变量分别为Pi和qj，若下行列车t i终到时选择下行到发线，则Pi一1，否则Pi—o；若上行列车t j终到时选择上行到发线，则qi一1，否则仍一0。即列车选择同向或反向到发线时的约束：
Pi一0，1i一1，2，…，优(36)
qj一0，1歹一1，2，…，m(37)
(10)终到列车跨正线接车和始发列车跨正线发车时，与反向的通过列车可能发生冲突，记跨正线接发车的会车间隔时间为砖，由此得下行列车与上行列车的跨正线会车约束：
I，o∞：I≥凌
i一珐；；Pi一0；i，歹一1，2，…，仇
(38)
I强，e z：i l≥磕
螺，一如i；％一1，qr一1；
i，歹，r一1，2，…，m(39) I鼢，e强，I≥曲，
z刍．一zb，；缈一0；i，歹一1，2，…，m
(40)
x。di O颤，I≥毫
z旬di=z毛．；U d一1；P，一1，
i，i，r一1，2，…，m(41) 4到发线运用相关约束分析
记车站&的下行到发线为N e。当下行列车t i 到达停站&时(z妻≠z￡)，则与那些在作业z&之前到达但仍未出发的停站列车t／同时占用到发线。由于列车t i，的停站时间为X i t,k ez敷，且被z&划分为2段，长度分别为zk@z2和z2o z乳，所以列车t i到站时占用下行到发线的其他列车的集合为瓦一{t L∈T：zk ez&一j ci f,k ez2+z2e z文，z生≠zk}(42)同样，记车站&的上行方向到发线数为N。。当列车t j到达停站s t时(强≠颤)，则与那些在作业颤之前到达但仍未出发的停站列车t，，同时占用到发线。由于列车t j，的停站时间为yk G yj d'k，且被强划分为2段，长度分别为如。螺和y嘉e谚，所以列车白到站时占用上行到发线的其他列车的集合为
瓦一{t j，∈亍：炽e谚一硝名。强+张e 娘，娘≠谚名)(43)列车在终点站折返时，作为终到列车与后续的始发列车是占用1条到发线，所以在上述占用到发线的列车集合中需扣除这些列车。因此式(42)和式(43)修正如下。
r瓦一{￡，∈瓦：口i，一1，
qJ一1，J≠0}k—oi T，最一_瓦一{￡，∈瓦：U办一1，
夕，一0)忌一di
I瓦k≠O i，di
(44)
r瓦一{巧，∈B：蝴，一1，
Pi一1，i≠0)k—oi L一叫瓦一{巧，∈露：v／i一1，
缈，一0)愚一面
【取k≠q，匆
(45)
根据上述分析，可得车站S。的上、下行到发线数约束：
T，砖l≤M
z袭≠z≤，i一1，2，…，m，k—O i，…，di
(46)
r碡l≤风
碾≠啵，歹一1，2，…，m，k—O j，…，西
(47)
占用同一条到发线的前后两列车发到间隔时间约束：
zk e z&≥毋
天气潮湿怎么办
第2期考虑动车组周转和到发线运用的高速铁路列车运行图优化方法111
T，谴I—N k一1；i，i7—1，2，…，m；
k—O i，…，di(48)旗e呶≥甜
l亍业I一瓢一1；J，J7—1，2，…，m；
k—O j，…，dj(49)
5考虑动车组周转与到发线运用的高速列车运行图优化模型
优化模型以列车旅行时间和动车组交路接续时间最小化为目标来构建。
下行列车旅行时间为
m di--1di--1
￡，一∑『_∑(z&+，ez￡)+∑(z￡ez&)] i21L k=oi k=oi+l J
(50)
上行列车旅行时间为
m01oj+l
￡：一∑『∑(诅一。e吐)+∑(珐e螺)] j21L‘+1^一哆一1J
(51)
上下行列车接续时间为
t。一∑∑白“口+∑∑西口直(52) i=0j=0i=0J=O
综上所述，建立模型如下：
m i nZ一(￡1+t2)+a t3(53) S．t．
式(4)一式(23)；式(26)一式(41)；式(44)一式(49)
式中：口为一个较大的正数，表示动车组衔接关系的优化优先于列车旅行时间的优化；拓展的接续时间coo，C～00均为0。
6模型的求解算法钢结构房多少钱一平米
对于上述建立的高速列车运行图优化模型，在文献[4]的运行图铺画方法基础上，设计模型的求解方法，具体求解思路如下。
首先，按照文献[4]的方法铺画初始松弛列车运行图；然后，在当前松弛运行图基础上，构造动车组交路，获得当前动车组的接续关系和接续时间；最后，采用交换作业顺序化解到发线冲突，采用文献[4]的方法逐个化解列车作业时间冲突，直至当前松弛运行图的所有冲突完全化解为止。
在化解列车作业时间冲突及更新松弛运行图的过程中，选择运行线平移时旅行时间最小的调整案，以保证目标函数中列车旅行时间处于当前最小水平；在交换作业顺序、调整运行线时，及时更新动车组交路方案，保持目标函数中动车组接续时间处于当前最小水平，以保证运行图的质量。
6．1构造动车组交路
构造最小接续时间的动车组交路，即求解以下2个模型。
(1)下行列车终到后转为上行始发列车时的动车组接续时间最小模型为
m i n∑∑勺“d(54) i=0J一0
S．t．
式(18)，式(20)，式(21)和式(34)
式中C i由式(24)确定。
(2)上行列车终到后转为下行始发列车时的动车组接续时问最小模型为
m i n∑∑西可丘(55) i=0J=O
S．t．式(19)，式(22)，式(23)和式(35)
式中f i由式(25)确定。
上述2个模型都是指派问题模型，可以运用指派问题匈牙利算法进行求解。
6．2到发线冲突化解
列车作业时间冲突化解基本完成后，在到发线运用紧张时段，只要保持周边列车到发顺序，便可防止这个时段内产生新的到发线冲突。这只要增加一些列车作业之间的弧，保证紧张时段内不再增加新的到发线需求即可，即对于I T，徒I—N k或r砖l—N；的列车t i或t，，其到达作业与紧前列车的出发作业之间构造发到弧。
对于到发线冲突的列车，即对于I r娩I>M 或|F地l>丙。的列车t i或t j，其到达作业与紧后列车的出发作业交换顺序。
随列车t i紧后出发的列车￡，的确定方法为
t f一{t l E T：m i n{xd—z1)，z二<z2)
(56)
其他紧前或紧后出发的列车可参照式(56)确定。
6．3列车运行图铺画算法
输入：高速铁路网络N一(S，E)，下行列车集T，上行列车集T；上下行列车的始发站O i和O j，终到站d。和dJ，始发时间域[月，月]和[力，力]，在车站St的最小停站时间r谴和≠业，发车追踪间隔时间《和r l，车站同向接车间隔时
中国铁道科学第33卷间卅和r2，先后占用同一条到发线的列车发到间
隔时间毋和r p，以及车站S+的下行方向到发线数N一和上行方向到发线数N。。
输出：列车在各个车站的作业时间z2，zl和y0，吐，列车接续方式‰，％，P，，吼以及总时间费用。
第0步铺画初始松弛列车运行图。在不考虑运行线之间冲突的情况下，根据式(2)、式(3)和列车最小停站时问，顺次铺画运行线。
第1步构造动车组交路。利用匈牙利算法求解出最小接续时问的动车组交路。
第2步化解车站作业时间冲突。若存在列车车站作业时间冲突，则调用基于定序优化的运行图优化方法【4o化解冲突，转第1步，否则转第3步。
第3步判断是否存在到发线冲突。若存在T7*『>N t或I r m I>N；，则转第4步，否则算法终止。
第4步构造列车发到弧，化解到发线冲突。对于』r*I—M或I丁7m I—N t的列车t。或r，，其到达作业与紧前列车的出发作业之间构造发到弧；对于I r*I>M或I r^j>M的列车t，或t，，其到达作业与紧后列车的出发作业交换顺序，转第1步。7算例与分析
以某高速铁路为例：共有17个车站，16个运行区间，开行300km h1(第1种)和250 km h1(第2种)共2种列车，上、下行列车的追踪时间矗和r；均为3m i n；到达间隔时间程和r2均为2m i n；列车占用同一条到发线的发到问隔时问r l d和r∥均为3m i n；列车终到站时，从到发线至车库的时问一“和r7“均为5m i n；始发列车从车库至到发线的时间r7。和；7。均为5r ai n；下行列车终到转为上行始发列车时在车站最小停站时间，以为6r ai n；上行列车终到转为下行始发列车时在车站最小停站时间以为6r ai n。假定列车终到后转为反向始发时，直接在原终到的到发线上跨越正线发车，即P。一1，吼一l；跨正线发车的会车间隔时间馥为2m i n。．F行方向到发线数N．和Ⅳ6为5，其余车站下行方向到发线数N。均为3；七行方向到发线数丙。和N．，为5，其余车站上行方向到发线数M均为3。根据本文的数学模型和求解算法，运用C#编写程序，通过运行程序获得的优化运行图如图1所示。
g姆：嚣量l!{i妊!￡!嚣j甲t nt_’膏嚣帚凳
蹦l 列车运行幽

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。