基于TPr/T_系统的编组站配流研究

张正坤，朱昌锋

兰州交通大学 交通运输学院，兰州 730070

基于TPr/T_系统的编组站配流研究

张正坤，朱昌锋

兰州交通大学 交通运输学院，兰州 730070

通过考虑分析编组站作业流程，根据Petri网理论，将Pr/T_系统扩展为基于时延性的TPr/T_系统，在此基础上，逐步建立编组站TPr/T_系统模型。在模型中，以列车（车列）为元组，解决配流对资源的约束；通过谓词容量限制，解决配流在空间上的约束；通过变迁限制，解决配流对时间的约束。系统以满轴、尽量不晚点为优化目标，根据反向推理思想设计算法，以求得较为合理的配流方案。最后，通过实例，验证提出理论的合理性。

编组站；配流；Petri网；TPr/T_系统

1 引言

配流的主要目的是确定出发列车的车流来源和编组内容，合理的配流方案对指导编组站作业、提高编组站运输效率具有重要意义。为此，有相关学者对编组站配流问题开展了大量研究。

王慈光[1]首次提出静态配流和动态配流概念；彭其渊等[2]认为广义配流应包括列车解体方案、配流和列车编组方案。根据研究视角不同，赵军等[3]将编组站配流问题转化为指派问题；马亮等[4]将配流问题等价为作业排程问题；黎浩东等[5]用整数规划对配流问题进行了研究。根据研究内容不同，薛峰[6]、赵军[7]、黎浩东[8]等分别从车流来源、调机运用及不确定性方面对配流展开了研究。上述文献从不同角度对编组站配流进行了研究，对进一步研究该问题具有一定的参考价值。

但是，配流受车流、作业及时间等因素影响，既有文献在研究过程中对车流所处状态、技术作业的并行性及时间接续方面分析不足，而Pr/T_系统对解决这些缺陷具有一定优势。基于此，本文通过分析配流的影响因素，利用Pr/T_系统理论建立编组站系统模型，并以满轴、尽量不晚点为优化目标，对编组站配流展开研究。

2 TPr/T_系统的基本理论

Pr/T_系统侧重研究个体的状态变化过程，是高级Petri网系统之一。由于该系统未引入时间参数，考虑到配流过程中，车流在时间上的接续关系，本文依据文献[9]，将Pr/T_系统扩展为与时间有关的TPr/T_系统。

定义1 Σ=(P，T，F；D，V，AP，AT，AF，τF， )

M0构成TPr/T_系统的条件是：

（1）( )

P,T,F 为有向网，称为Σ的基网。

（2）D为非空有限集，为Σ的个体集，也为系统的论域，D上有给定的运算符集Ω。

（3）V是D上的变量集。

（4）AP：P→π，其中π是D上的可变谓词集。对于 p∈P，若 AP(p)为n元谓词，就说 p为n元谓词。

（5）AT：T→fD，其中 fD是D的公式集，对t∈T，AT(t)只含静态谓词和Ω中的运算符。

（6）AF：F→fS，其中 fS是D的符号和集。对n元谓词 p∈P，若(p ,t)∈F或(t , p)∈F，则 AF(t , p)或AF(p ,t)为n元符号和。对于t∈T，公式AT(t)中的自由变量（即不受量词∀和∃约束的变量）必须是以t为一端的有向弧上的自由变量。

（7）τF：T→R，R为非负实数集。对于t∈T，τF()t表示与变迁有关的时间参数。

（8）M0：P→fS，对n元谓词 p∈P，M0(p)是n元符号和。

根据定义1，TPr/T_系统模型如图1所示。

图1 TPr/T_系统模型

图1 中，＜＞及+组合在一起构成符号和；变迁t1中，x可替换a或b，分别记为(x ←a)和(x ←b)，称其为t1的可行替换，该替换适合于其他变迁。

定义2D中的元素和D上的变量均称为D的项（term），以 D的项为分量的 n元向量 ＜v1,v2,…,vn＞（n≥1）称为D的n元组。

3 编组站TPr/T_系统模型建立

3.1 配流及作业分析

配流是编组站将到达列车中符合接续时间的车列解体，并按去向编入规定的出发列车中，这涉及到以下几个主要研究内容。

就车流而言，车流是配流涉及的主体，贯穿于编组站整个作业过程，构成了配流的资源上约束。

就作业而言，技术作业是有关计划的具体实施，车流状态依赖作业变化，具有严格的流程性约束。

就时间而言，技术作业时间是确定车流搭配的重要因素之一，进而构成了配流问题在时间上的约束。

编组站主要作用是解体和编组货物列车，列车在编组站的主要作业有到达技术作业、解体作业、编组作业及发车前的技术作业等。编组站作业组织如图2所示。

图2可以看出，在编组站的不同环节，车流所处的状态有所不同，在整个过程中，车流状态依赖作业而变化，这为利用TPr/T_系统研究编组站提供了依据。此外，由于配流得出的方案最终要通过具体作业而实现，因此，配流方案的不能脱离车站实际作业而盲目编制。

图2 编组站作业组织

3.2 有关假设

编组站是一个复杂的车流加工系统，其设备、作业及车流比较复杂，为方便研究且不失一般性，本文作如下假设。

（1）站型假设，以单向纵列式编组站为背景，驼峰和峰尾各有一台调机进行调车作业。

（2）车流假设，车流信息与列车确报一致，对禁溜车、超限车等特殊作业车不予考虑。

（3）时间假设，依据《技规》规定，编组站作业时间由《站细》规定给出，且无意外发生。

3.3 模型建立

编组站是由到解子系统和编发子系统组成的车流加工系统。到解子系统主要办理有关接车、到达技术作业及推峰解体作业，基于假设，根据Petri网及TPr/T_系统有关理论，结合车流状态变化过程，给出到解子系统的TPr/T_系统模型。到解子系统模型如图3所示。

图3 到解子系统模型

图3 中，P={ p0,p1,…,p11}为库所集合，表示车场或股道，则AP(p)表示车流所处状态（谓词），T={t0,t1,…,t8}为变迁集合，表示作业过程。到解子系统中符号表示含义见表1。

表1 到解子系统符号表示含义

编发子系统主要办理有关编组、转场及出发前的技术作业等，同样地，给出到编发子系统的TPr/T_系统模型，该模型如图4所示。结合图4所示，编发子系统符号表示含义见表2。

图4 编发子系统模型

表2 编发子系统符号表示含义

图3、图4分别表示了到解子系统模型和编发子系统模型。其中，AP(p0)和AP(p ′0)均表示列车在区间的运行状态，AP(p4)和AP(p ′4)均为本务机处于整备的状态，两个系统中均含有AP(p7)，都表示车列处于集结状态。鉴于到解子系统和编发子系统中有表示同一状态的谓词，因此，根据文献[10]提出的Petri网共享合成理论将两个子系统进行合并。

定义3设Petri网PNi=(Pi,Ti;Fi,M0i)(i =1,2)，令PN=(P ,T;F,M0)使得

（1）P=P1⋃P2，P1⋂P2≠∅

（2）T=T1⋃T2，T1⋂T2=∅

（3）F=F1⋃F2

则称 PN是 PN1与 PN2的共享合成网，记作 PN=PN1OPPN2。

根据定义3，现将到解子系统和编发子系统合成为编组站的TPr/T_系统模型，合成的编组站TPr/T_系统模型如图5所示。

（4）

图5 编组站TPr/T_系统模型

图5 中，AP(p0)表示到达或出发列车在区间的运行状态，其余谓词表示含义均不变，该模型详细反映了车流在编组站的主要作业过程及其所处状态。

3.4 系统模型说明

3.4.1 模型中车流的表示

编组站主要作用是解体和编组列车，车组（或车辆）及机车（本务机和调机）是作业中的最小单位，因此，本文将它们作为系统中D的项，记为vij。其中，v∈N表示车组中所含车辆的数量，i表示到达场的股道号，当i=0时表示列车在区间运行，j为《站细》中规定的车流组号，特别定义

定义元组Vi表示列车或车列，则列车可表示为Vi=＜00i,vij1,vij2,…,vijn＞，车列可表示为Vi=＜vij1,vij2,…,vijn＞其中，jl∈{1 ,2,…,j} ，l=1,2,…,n 。

定义4给定一个特殊运算符Φ，用以表示v与vij的对应关系，使得：

3.4.2 模型中谓词容量的约束

根据谓词中存放元组的数量来划分，系统中的谓词可分为A、B两大类。其中，A={AP(p0)，AP(p3)，AP(p5)，AP(p8)}为单元谓词，即谓词中只允许存放一个元组。需要说明的是，对于编组站而言，列车是以单列的形式到达或出发，因此，本文将AP(p0)视为单元谓词以方便研究。B={AP(p1)，AP(p2)，AP(p4)，AP(p6),AP(p7)，AP(p9)，AP(p10) }为多元谓词，即可以存放多个元组，且有：

式（1）～（3）分别为到达场、编组场及出发场的空间容量约束，即股道数限制；式（4）中的 Ki为元组Vi=＜vij1,中个体项（车组）的个数，其数值依赖于解体车列，为动态值，图5中，k=Ki。

以AP(p6)、AP(p7)为例，现给出车组在谓词中的存放形式如下：

其中，i或il′为到达场的股道号，m≤FN为车流组号对应的编组场的股道号。

3.4.3 模型中变迁时间的约束

定义5[11]设M 为Pr/T_系统的一个标识，则变迁t∈T在M具有发生权的充分必要条件是：存在M下的可行替换 t(z1← d1，z2← d2，…，zl←dl) ，其中，{z1，z2，…，zl}为与t有关的符号和及公式中的自由变量。M和t的这种发生权记作：

定义5是基于Pr/T_系统定义的变迁发生权，在该定义的基础上，依照本文所建立的编组站TPr/T_系统模型，根据变迁对时间要求的不同，也将变迁分为A、B两大类。其中，A={AT(t1)，AT(t8) }中的变迁需符合到达计划或发车计划所规定的时间，变迁过程需一定的时间，其中，τF(t1)=DT表示到达列车从区间进入到达场的时间，τF(t8)=FT表示出发列车从出发场到区间的时间。B={AT(t2)，AT(t3)，AT(t4)，AT(t5)，AT(t6)，AT(t7)}中的变迁则与计划无关，只需满足变迁条件即可。其中，τF(t2)=DJT表示到达技术作业时间，τF(t3)=GT为挂车时间，τF(t4)=TT为峰调推峰时间，τF(t5)=LT为k次循环变迁的总时间，表示溜放时间，τF(t6)=BT为尾调编组及转场时间，τF(t7)=FJT为出发技术作业所需的时间。另外，因不同类型的出发列车对编组作业时间要求不同，τF(t6)=BT应满足如下规定：

根据变迁的前集谓词中可参与替换的元组数量不同，将B进一步分为B′、B″两大类。其中，B′={AT(t4)，AT(t5) }，这类变迁对前集谓词中参与变迁的元组无选择性。 B″={AT(t2)，AT(t3)，AT(t5)，AT(t6)，AT(t7) }，这类变迁对其前集谓词中参与可行替换的元组具有选择性。

对于AT(t7)，应最先选择满足列车运行图规定的出发列车的元组参与变迁。对于AT(t6)，除了和 AT(t7)的选择要求一样外，还应满足以下约束：

式（5）中，QTm表示阶段内m次列车最迟发车时间，由发车计划规定；Ti6表示元组vi参与t6变迁的起始时间；QYj表示 j方向上的最大牵引数，为硬约束。

对于AT(t3)，在前集谓词中选择元组参与变迁时，应遵循“先到先解、解体照顾编组”原则，即在AP(p2)中选择含最先出发列车急需车流的元组vj参与变迁，还应满足以下约束：

式（5）和式（7）共同构成了配流在接续时间上的约束，其中，T3j表示元组vj参与t3变迁的起始时间。

4 算法设计

为了提高求解效率，减少系统模型的变迁次数，Dijkstra算法[12]、启发式算法[13]、推理算法[14-15]等，已被引入到该领域。但由于在优化配流方案时，需遵循“先到先解、解体照顾编组”原则，而该原则也是基于一种反向推理的过程。基于此，本文在既有变迁约束的基础上，借鉴文献[14]中的反向推理设计算法，同时考虑到系统模型时间的全局性，在谓词及变迁约束的基础上，给出如下算法步骤。

步骤1有关参数录入。

步骤2置n为系统变迁起始时间（n为全局时间控制变量，以分钟计）。

步骤3结合反向推理思想，依照系统模型中各变迁规则，依次选取符合参与t8,t7,…,t1变迁的元组。

步骤4记录变迁内容，更新系统标识，n++。

步骤5判断n是否溢出系统的变迁时间范围。如果是，系统变迁结束，进入下一步；否则，返回步骤3。

步骤6记录变迁内容，更新系统标识。

步骤7有关记录输出，算法结束。

在已有说明的基础上，根据配流问题核心，给出配流的示意如图6所示。

图6 配流示意图

结合图6，通过该算法步骤，便可确定车流的解体时间、编组时间以及车流间如何搭配。

5 算例验证

以某编组站2∶00～6∶00阶段为例，对本文提出的理论进行验证。剔除该阶段内无关车流及设备，各车场容量及作业时间分别见表3、表4。

表3 车场容量

表4 作业时间

根据该站车流在不同去向上的牵引定数及出发列车类型，可获取调车场股道的运用方案。调车场股道运用见表5。

表5 调车场股道运用

按照列车确报及列车运行图的要求，在2：00～6：00内，该站列车到达计划及发车计划分别见表6、7所示。

表6 列车到达计划

表7 列车发车计划

本阶段开始，有关谓词中的元组存放情况如下所示：

将有关参数输入模型中，根据算法，经VC++6.0语言编程，便可得到配流方案。根据t3和t6每次变迁时间及前集谓词中元组参与变迁的次序，最终得到的解体顺序表、编组顺序表分别见表8、表9。

表8 解体顺序表

从表6～9可以看出，因受接续时间及满轴约束，45005次列车晚点发车2 min，并影响后续24040次列车晚点发车1 min，其余出发列车均正点发车，该阶段内，正点发车率为77.8%。另外，考虑到调机在该阶段内的应用情况，根据t3和t6变迁，调机累计作业时间如图7所示。

表9 编组顺序表

图7 调机累计作业时间

图7 可以看出，该阶段内，t3累计变迁112 min，t6累计变迁168 min，分别反应了峰调和尾调的累计工作时间，各占总时间的46.7%和70.0%，这主要是因为系统在变迁过程中，推峰解体时间小于编组作业时间，这也反映出该站编组能力较为紧张。截止本阶段末，在各车场的结存情况如下：

可以看出，谓词及元组可以直观地反应出本阶段末车流结存情况。经分析车流可以发现，为了确保28010次列车按时发车，阶段开始时AP(p2)中的元组＜82a,242c,42d＞首先参与了变迁，这主要是因为算法中的变迁约束所致。可见，该算法对于系统变迁过程中参与变迁元组的选择具有一定的优势，进而减少了系统变迁的次数。在算例求解过程中，系统变迁共计约为120次。

针对配流问题，文献[16]认为动态规划无法求得最优解，故用Greedy算法对其模型进行求解。基于此，本文以系统模型为基础，利用Greedy算法思想对算例求解，结果发现，系统变迁约106次，45005次列车正点发车，但同时导致了32007次列车停运。可见，与Greedy算法相比，本文设计的反向推理算法虽然在系统变迁效率方面略显不足，但是在软约束方面具有一定的优势，更具实用性。

最后，根据算法中的变迁过程，给出4∶40～5∶56时间段内系统变迁的一个进程，该进程如图8所示。

图8 系统变迁的一个进程

从图8中可以看出，系统各变迁是同时进行的，即系统具有异步、并发的特性，从而也说明了编组站作业系统是一个集顺序和并发于一体的车流加工系统。

6 结语

配流是编制阶段计划的核心，对提高编组站作业效率具有重要作用。本文以单向纵列式编组站为背景，结合编组站作业流程，通过建立TPr/T_系统对编组站作业的流程再造，并行性分析，进而得出配流过程中的瓶颈所在，以达到研究编组站配流的目的，这也是利用TPr/T系统研究配流的优势所在。此外，系统模型的求解效率以及如何寻求更加有效的求解算法将是本论文下一步所研究的重点。

[1]王慈光.编组站动态配流模型与算法研究[J].铁道学报，2004，26（1）：1-6.

[2]彭其渊，赵军，韩雪松.技术站广义配流问题模型与算法[J].中国铁道科学，2010，31（2）：108-114.

[3]赵军，彭其渊.双向编组站配流问题整数规划模型及算法[J].铁道学报，2014，36（9）：10-19.

[4]马亮，郭进，陈光伟，等.铁路编组站动态配流的约束传播和多点构建性搜索的混合算法[J].信息与控制，2015，44（2）：230-237.

[5]黎浩东，何世伟，景云，等.考虑不同满轴约束的编组站阶段计划配流优化[J].铁道学报，2012，34（7）：10-17.

[6]薛锋，王慈光.编组站配流相关问题分析[J].交通运输工程与信息学报，2008，6（4）：29-39.

[7]赵军，彭其渊.单向编组站配流与调机运用综合问题[J].铁道学报，2012，34（11）：1-9.

[8]黎浩东，宋瑞，何世伟，等.基于列车解编作业时间估算的编组站阶段计划配流优化[J].中南大学校报，2014，45（1）：317-327.

[9]李望，倪少权.基于TPr/T-S的客专车站通用模型及仿真[J].西南交通大学学报，2013，48（5）：934-941.

[10]王琦，韩江洪，王青山.Petri网合成理论及应用综述[J].计算机仿真，2008，25（12）：8-11.

[11]袁崇义.Petri网原理与应用[M].北京：电子工业出版社，2005.

[12]周强，司丰炜，修言彬.Petri网结合Dijkstra算法的并行测试任务调度方法[J].电子测量与仪器学报，2015，29（6）：920-927.

[13]李斌.基于Petri网和启发式搜索的调度算法研究[D].杭州：浙江大学，2015.

[14]周剑峰，彭磊.基于反向模糊Petri网的应急响应条件下事故的质因分析[J].灾害学，2015，30（3）：124-126.

[15]王慧英，乐晓波，周恺卿.一种基于模糊Petri网的双向并行推理算法[J].计算机工程，2014，40（40）：208-212.

[16]郭瑞，郭进，苏跃斌，等.基于Greedy方法的动态配流模型与近似算法[J].西南交通大学学报，2014，49（4）：712-719.

ZHANG Zhengkun,ZHU Changfeng

School of Traffic and Transportation,Lanzhou Jiaotong University,Lanzhou 730070,China

Research on wagon-flow allocation for marshalling yard based on TPr/T_system.Computer Engineering and Applications,2017,53（21）：219-224.

The model of TPr/T_system about marshalling yard is built,by extending Pr/T_system to TPr/T_system,according to Petri net theory and the marshalling yard operation procedure.In the model,regarding train or car row as a tuple to restrain the resource condition to wagon-flow allocation.By restraining the predicate capacity to settle the space constrain,besides,the time constraint is settled by restraining transition.In order to obtain a reasonable scheme about wagon-flow allocation,the full axis departure,as far as possible with the punctual departure,is regarded as the optimization goal in the model.The optimization goal can be realized by using the algorithm based on the backward reasoning thought.Finally,an example is used to verify the rationality of the theory presented by the paper.

marshalling yard;wagon-flow allocation;Petri net;TPr/T_system

A

U292.4

10.3778/j.issn.1002-8331.1605-0027

国家自然科学基金（No.61364028）；教育部人文社科规划基金项目（No.15XJAZH002）；兰州市科技局研政产合作支撑计划项目（No.2011-1-111）。

张正坤（1989—），男，硕士研究生，主要研究方向为交通运输优化理论与方法，E-mail：zzknlxy@163.com；朱昌锋（1972—），男，教授，主要研究方向为交通运输优化理论与方法。

2016-05-05

2016-07-05

1002-8331（2017）21-0219-06

CNKI网络优先出版：2016-08-01,http://www.cnki.net/kcms/detail/11.2127.TP.20160801.1017.002.html