基于约束规划的铁路大型客运股道分配问题研究

基于约束规划的铁路大型客运股道分配问题研究

车站是铁路运输网络的一个重要节点。随着客运专业线路的建设和运营，将建立连接客运专业线路、主线和城际铁路的大型客运线路，并连接到具有运营和交通功能的区域和停车场。这类车站的平面图规模较大,列车作业复杂。在列车运行计划的编制过程中,该类车站出现在多条所衔接线路的列车运行图中,为了检验列车运行图的可行性以及制订车站作业计划,就要为列车分配无冲突的进路和站台,同时满足车站作业的安全要求及相应的运输组织方案,这就是大型客运站的股道分配问题(TrackAllocationProblem,TAP)。文献对我国铁路列车运行计划的一体化编制方法进行了研究,并讨论股道分配问题在列车运行计划中的层次关系。关于客运站的TAP问题,国内外学者进行了广泛的研究。国外的研究可以分为3类:文献将该问题转化为一个WNPP模型(WeightedNodePackingProblem),利用线性规划对问题进行求解;文献根据图的着色模型,利用整数规划软件来求解;文献根据手工操作过程中的经验,利用启发式算法对问题进行分析。国内学者主要从制订车站作业计划以及在线决策两方面进行研究:文献以既有线客运站为对象,采用多目标规划理论和分枝定界法进行求解。文献探讨在线决策问题。提出最大平行进路和最大概率进路的排列方法。另外,文献分别利用遗传算法和模拟退火等并行算法对问题进行探讨。上述文献的研究内容与TAP问题具有一定的相似性,但直接用来求解本文的TAP问题仍有一定的困难。首先,文献未考虑咽喉区的进路疏解;文献虽然考虑了进路疏解,但需要事先计算出所有列车之间的约束集,算法的复杂度随着问题规模的增大急剧增加;文献需要列车到、发时间的概率分布函数,是一种后验方法;文献主要关注在线决策。另外,列车速度等级以及走行进路的不同会造成列车占用咽喉区的时间差异,这使得分析列车作业之间的缓冲时间成为可能,也可以为方案评价及在线决策提供数据支持。因此,对大型客运站TAP问题提出了更强的约束条件。约束规划(ConstraintProgramming,CP)是人工智能领域内的一种研究范式,在资源分配与调度问题中得到广泛应用。文献利用CP对列车运行调整问题进行探讨。本文利用CP方法对TAP问题进行建模,将约束条件分为硬约束与软约束,同时采用约束识别、值排序以及Backtracking搜索对问题进行求解。最后,以某客运站为例对模型和算法进行验证,结果表明该方法可以有效地求解TAP问题。研究结果可以为股道分配方案的评价以及局部优化等后续工作提供数据支持。1roritt、at规则符号设定如下:T为列车的集合;K为股道的集合;R为进路的集合;Ri为接车进路的集合,Ri⊂R;Ro为发车进路的集合,Ro⊂R;Ritit为列车t∈T可用接车进路的集合,Ritit⊆Ri;Rotot为列车t∈T可用发车进路的集合,Rotot⊆Ro;Kt为列车t可用股道的集合,Kt⊆K;at为列车t∈T的图定到达时刻;dt为列车t∈T的图定出发时刻。1.1tap问题的求解用CP模型描述TAP问题,首先要确定问题中的变量、值域以及约束条件。列车在车站的行车作业通常包括接车、停留以及发车3部分,分别用it、wt和ot来表示列车t的3项作业,完成该作业所需要的空间资源分别为接车进路、股道和发车进路,尽管通过列车没有停站作业,但仍然要利用这3项资源。TAP问题的目标就是为这些列车安排无冲突的空间资源,因此可以为列车t∈T生成3个变量:x(wt)x(wt)表示列车t的作业股道;x(it)x(it)和x(ot)x(ot)分别表示列车t的接车进路和发车进路;D(x(wt))D(x(wt))表示变量x(wt)x(wt)的值域,即列车t可用股道的集合Kt;D(x(it))D(x(it))和D(x(ot))D(x(ot))分别表示变量x(it)x(it)和x(ot)的值域,即列车t可用接车进路的集合Rit和可用发车进路的集合Rot。因此,TAP问题可以表示为以下的三元组ΤAΡ=(Ζ,D,C)(1)式中,Z为所有变量的集合;D为变量值域的集合;C为所有约束条件的集合。c(x),x∈Ζ表示一元约束,即变量x的取值v(x)应在值域D(x)内;二元约束c(xi,xj)表示变量xi,xj∈Z所对应事件之间的约束条件,例如两个列车不能同时占用同一个股道或者不能同时选择某两条进路进行作业等,k元约束c(k∪i=1xi),∀xi∈Ζ表示k个变量x1,…,xk应同时满足的约束条件,例如同时在咽喉区进行作业的列车之间不能有进路冲突。CP模型的求解就是为每一个变量从其值域中选择一个值,同时满足给定的约束条件。模型中的约束条件可以分为硬约束和软约束两类。硬约束表示不可违反的约束条件,否则列车作业之间就会产生冲突;软约束则表示选择偏好,例如某些列车通常固定使用某几条股道。1.2列车进出站时间列车运行图规定列车在车站的到达和出发时间:对于停站列车,到达时间是指列车停稳在股道上的时间,出发时间是指列车从股道上再次起动的时间;通过列车的到达时间和出发时间相同。对于TAP问题,由于要考虑列车在咽喉区的冲突问题,因此不能忽略列车的进出站过程,而且还要考虑列车长度、重量、牵引制动性能以及走行进路等因素对列车接发车作业时间的影响。由于要考虑列车进出站时在咽喉区的作业时间,因此TAP中产生以下两类硬约束。(1)接车进路约束对于占用同一股道k∈K进行作业的前后两个列车t和t+1,只有当前行列车t的尾部离开股道k,并释放相应的轨道电路区段以后,才具备为后行列车t+1开始准备接车进路的条件,而后行列车t+1的到达时间at+1表示后行列车利用该进路完成接车作业后的时间,因此at+1与前行列车t的出发时间dt之间应满足最小作业间隔时间约束at+1-dt>δ(t,t+1)t,t+1∈Τ(2)式中,δ为前行列车t出发至尾部释放股道k的时间与后行列车t+1的接车作业时间之和,它既与两列车的参数有关,还与它们的作业进路有关,详细的计算方法见文献。(2)股道接车进路如果两项作业使用一对敌对进路,则需要确保这两项作业在临界轨道电路区段上的作业没有冲突。如图1的车站平面图,其中有6个股道、8个道岔和10个轨道电路区段。以采用分段解锁方式为例,这里用轨道电路区段的队列表示一个进路,列车t1在股道1的发车进路r1=〈g2,g1,g3〉表示进路r1依次由g2,g1和g3等3个轨道电路区段组成;列车t2到股道3的接车进路r2=〈g1,g2,g6〉表示进路r2依次由g1,g2和g6等3个轨道电路区段组成。这两项作业有冲突的轨道电路区段为{g2,g1}。假设t1的发车作业早于t2的接车作业,那么只有当t1解锁轨道电路区段g1之后,才可以为t2开始准备接车进路r2,因此g1是这两项作业的临界轨道电路区段。如果用e(t1,g1)表示t1释放g1的时间,用b(t2,g1)表示t2开始占用g1的时间,那么两列车的进路冲突约束就可以表示为b(t2,g1)-e(t1,g1)>0(3)这两个时间的计算方法见文献。利用该约束可以判断列车作业在咽喉区的冲突,从而为进路选择提供依据。1.3不同列车使用的偏好在车站作业过程中,考虑到作业的方便性以及列车等级的差异,不同列车对股道和站台的使用有一定的偏好。这里用软约束表示这一类偏好。TAP问题主要有4类软约束:(1)股道和进路之间的约束安排对于接车作业来讲,一般为通过列车分配正线以及基本通过进路,为停站列车分配与运行方向同侧的股道和进路;对于折返列车,有顺接反发和反接顺发两种形式,通常根据车站平面图和列车运行图进行灵活安排;对于出入动车段或停车场的列车,要为列车分配与动车段或停车场有直接通路的股道和进路,否则就会产生转线调车作业。(2)列车等级限制对于某些高等级列车,为方便旅客乘降等,在某些车站要求尽量安排基本站台,这类约束具有较大的灵活性,也反映了分配方案的实施效果。(3)分配股道以方便旅客换乘列车的接续关系是在列车运行图中规定的。对于具有紧接续关系的一对列车,要尽量为两列车分配靠近同一站台的股道,从而方便旅客换乘。文献讨论了紧接续方式在欧洲铁路系统中的应用。(4)结合到不同的问题中去考虑p问题的研究方法对于由同一个机车或动车组担当运输任务的两个列车,在TAP问题中要将它们结合起来考虑。如图1,如果列车t2和t3由同一个机车或动车组担当,那么为t2安排接车进路时就要考虑到t3的发车方向,从而减少站内转线的调车作业量。2求解冲突对比TAP问题是一个典型的约束满意问题,本文利用冲突识别、值排序以及Backtracking(BT)搜索3个步骤对问题进行求解,取得较好效果。2.1作业间的时间冲突列车能否接入某个可用股道,要判断股道间隔时间约束,而一个列车在咽喉区的作业则受到其他不止一项作业的影响。如果该作业与另外一项作业没有时间冲突,则它们之间不存在约束条件,否则就存在约束条件。因此对于不同列车在咽喉区的作业,要判断变量之间的约束关系。TAP问题中包含时间和空间两类冲突。时间冲突是由列车运行图产生的,求解TAP问题就是为这些时间冲突的作业分配无冲突的空间资源。为判断列车作业之间可能的时间冲突,可以事先计算出每个列车采用所有可行进路进行作业的最大时间,来表示该作业的持续时间。这样所有作业之间可能的时间冲突都不会被忽略。约束识别就是判断列车的作业时间是否重叠,它可以通过以下方法来实现。如图2,左边图形中的每个矩形表示一个事件的作业时间,水平方向的长度表示持续时间。右边图形中的顶点表示相应的事件。如果两个事件的作业时间窗有重叠,就将它们对应的顶点连接起来,表示两个事件所对应的变量之间存在约束。约束识别会产生一个无向图,称为时间窗冲突图,相关描述见文献。2.2股道排序规则由于不同方向及等级的列车对股道和进路的选择有一定偏好,因此对∀x∈Z,应对D(x)中的元素进行排序,作为选择股道和进路的优先顺序。由于软约束表示选择偏好,因此1.3节中的4类软约束可以作为股道排序的规则。当选定股道以后,就要为列车安排接发车进路,通常情况下进路的排序规则是首先选择基本进路,然后是变更进路。2.3优化求解tap的算法根据时间窗冲突图以及值排序,利用BT搜索可以对列车之间的冲突进行疏解,从而寻找无冲突的分配方案。用G=(V,E)表示2.1节得到的时间窗冲突图,对于G的一个子图S⊂V,如果满足对∀i,j∈S,都有(i,j)∈E,那么S就表示一簇互相冲突的作业,簇的搜索方法见文献。求解TAP问题就是在满足股道作业间隔时间约束的条件下,对这些簇进行冲突疏解。对于同一簇中的变量,可以按照变量所对应作业的开始时间进行排序,这种排序方法确保了作业之间的约束传播。如图2的列车作业包含3个簇,按时间顺序排列为{A,B,D}、{A,C,D}和{C,E}。对簇{A,B,D},变量排序为B→A→D或B→D→A;对簇{A,C,D},由于{A,D}已经在前一个簇{A,B,D}中得到处理,因此只需要处理{C};同样对簇{C,E},只需要处理{E},因此变量的排序为{B,A,D,C,E}。BT搜索的流程如图3,其中主要包括变量排序、值排序、硬约束检验以及Backtracking4项内容。从中可以看出,每次只对一个变量进行赋值,当不能为一个变量赋值时,就返回到最后赋值的一个变量;当所有变量都已成功赋值后,计算完成,否则问题无解。3不同列车的tap算法图4为某大型客运站的平面示意图,图中的短竖线表示绝缘节,由绝缘节包围的区域为轨道电路区段。该车站衔接7个方向,分别用A到G表示,车站平面图中包括28条股道、15个站台、126副道岔以及106个轨道区段,从图中可知该车站包含AB、C、DE和FG共4个咽喉区。以AB和FG端咽喉区为例,表1为持续时间约70min的列车运行图,其中包含30列列车,表中列出列车的接、发车方向以及到发时刻。这些列车的可用股道有20条,股道编号见图4。利用C++语言,在一台3.2GHz、1GBRAM的Pentium4处理器上进行编程实现,对TAP问题进行求解。将从B到A的列车以顺接反发作为软约束排序规则,即上行方向2、4、6、8等股道的优先级高于下行方向的1、3、5、7等股道;对从F到B的列车,下行方向股道的优先级高于上行方向。为简单起见,这里列出15列列车的股道和接发车进路,如表2所示。表2中的接车进路和发车进路用咽喉区轨道电路区段的队列来表示,省略了股道的轨道区段编号,如列车1到股道2的接车进路在咽喉区的轨道电路区段队列为〈58,60,22,23〉。另外,如果将反接顺发作为从B到A列车的软约束排序规则,同样可以得到问题的另外一个解。这意味着CP可以对问题的软约束做出灵活反应,从而反映方案的可行性。4b搜索优化模型大型客运站的股道分配问题存在股道作业间隔时间、进路冲突两类硬约束及表示选择偏好的软约束。本文将该问题描述成一个约束满意问题,首先利用软约束确定股道排序,然后利用BT搜索对问题进行求解。案例分