编组站静态配流的约束传播和启发式回溯算法

马 亮， 郭 进， 陈光伟

（1.西南交通大学信息科学与技术学院，四川成都610031；2.铁道部信息技术中心，北京100860）

编组站静态配流的约束传播和启发式回溯算法

马 亮1， 郭 进1， 陈光伟2

（1.西南交通大学信息科学与技术学院，四川成都610031；2.铁道部信息技术中心，北京100860）

为了提高阶段计划的编制效率，针对编组站静态配流字典序多目标累积调度模型，设计了迭代、约束传播和启发式回溯的混合算法.该算法根据多目标的字典序将模型分为3层：第1层为配流成功的出发列车优先级总和最大化，第2层为出发列车车流来源总数最少化，第3层为车辆平均停留时间最短化.每层先通过约束传播算法化简模型、缩小解空间，再通过启发式回溯算法和约束传播技术联合快速求解.上一层的最优解作为下一层的初始解，并动态增加避免上一层目标退化的约束，迭代求解每层的最优解.通过某编组站实际数据验证表明，本算法耗时小于20 s，满足现场对阶段计划编制的实时性要求，且求得的配流方案优于其他算法.

编组站；静态配流；约束传播；启发式回溯；约束满足问题

在铁路编组站三层调度指挥体系中，阶段计划是一个班各阶段工作的具体安排，是完成路局班计划任务和指标的保证，也是编制调车作业计划的主要依据，统筹分配和排程车站一个阶段时间（3～4 h）内的各种资源和作业.主要包括配流、资源分配和作业排程等相互关联的3个子计划，其中配流是核心，分为静态配流和动态配流［1-2］，静态配流主要研究在解编顺序确定的情况下优化的配流方案.

针对静态配流问题，文献［1］使用表上作业法求解静态配流运输模型；文献［2］用最小费用最大流算法求解静态配流网络模型；文献［3］设计了静态配流网络模型的学习算法；文献［4］用禁忌搜索策略和配流网络相结合的算法求解静态配流的双层多目标整数规划模型；文献［5］用有偏随机键遗传算法求解单向编组站配流的混合整数线性规划模型；文献［6］针对配流问题NPC特点，设计了先到先服务的启发式算法.以往研究都是设计智能算法求解静态配流数学规划（mathematical programming，MP）模型，这些算法缺乏约束推理技术，导致求解时间较长；此外，算法通用性不好，问题的一个微小变化就可能导致算法不再适用.本文基于约束程序（constraint programming，CP）［7］理论，针对编组站静态配流字典序多目标累积调度（lexicographic multi-objective cumulative scheduling，LMCuS）模型，设计了带初始解的迭代［8-10］、约束传播［11-12］和启发式回溯［12］的混合算法.经过某编组站现场数据试验表明该算法的实用性和计算的高效性.

1 编组站静态配流LMCuS模型

编组站静态配流是多目标车流资源受限项目调度问题（resource constrained project scheduling problem，RCPSP）［7，13］，到达车流容量大于1，可以同时为多个出发列车提供车流，所以也是资源累积调度问题（cumulativeschedulingproblem，CuSP）［11］.以往的MP模型都是将约束写成算术表达式，针对复杂问题需要增加额外的变量和约束；而且MP只提供了约束的全局处理，针对包含多种约束的混合问题建模困难.此外，在部分研究中使用线性加权和法将多目标变成单目标，这种方法需要针对不同的数据环境确定不同权值.本文基于CP的约束谓词［7］建模方法、字典序多目标优化（lexicographic multi-objective optimization，LMO）［8-10］和CuSP理论建立了编组站静态配流LMCuS模型.为了便于建模，不妨将编组场现车、到达场待解车列、计划到达列车和交换场、货场、车辆段、专用线等地点待取车组统称为“到达列车”.

1.1 字典序目标

编组站静态配流LMCuS模型基于LMO理论，按照现场到发车流不均衡等实际情况和现场车站调度员的决策偏好建立具有字典序的3个目标.

目标（1）为配流成功的出发列车优先级总和最大，此目标考虑了到发车流不均衡，出发列车不能都满轴出发的情况，其中：变量eF，j∈｛0，1｝为出发列车fj编组作业JF，j实施标志；lj为fj的优先级；n为出发列车总数.

目标（2）为出发列车车流来源总数最少，考虑了“配流照顾解编作业”原则，其中：oj＝rj表示出发列车fj车流来源数；rj为向fj提供车流的到达列车集合，初始令rj＝Ø；对于fj所有的车流来源cF，i，j，k，如果cF，i，j，k＞0，则rj＝rj∪｛di｝，变量cF，i，j，k∈［0，aj］为fj消耗到达列车di中编组方向为ωk的车辆数；aj为fj的轴重和换长要求，用车辆数代替.

目标（3）为使到达车流尽量先到先发，提高了先到车辆的利用率，减少了车辆在站的平均停留时间，其中：变量eD，i∈｛0，1｝为di解体作业JD，i执行标志；m为到达列车数.

式（4）为3个目标的字典序，从左到右优先级依次降低.

1.2 约 束

LMCuS模型使用CP约束谓词［7］建模方法，实现了变量之间的各种关系，提高了模型的可读性，缩小了模型规模.其中，车流资源容量和调车场容车数限制等约束基于CuSP［11］理论实现.

式（8）为到发接续和不违编约束，其中：λj，k为编组特征值，若编组计划中允许fj开行ωk的车，则λj，k＝1，否则λj，k＝0.

约束（9）为配流满轴约束，其中：aj为满轴车辆数.

约束（10）为车流资源容量限制约束，即配流过程中，所有出发列车消耗车流数不超过车流资源容量.

约束（11）表示在配流过程中调车场集结的车流数不超过调车场容车数V.

与以往模型［1-6］相比，LMCuS模型考虑了到发车流不均衡、配流照顾解编作业和调车场容量限制等因素，更接近现场实际需求.与MP模型中每个约束必须被表示成（非）线性方程相比，基于CP约束谓词［7］建立的每条约束可以分别建模，可以进一步形成更复杂的混合约束或者约束松弛，不会影响其他约束［14］.

1.3 模型求解思路

编组站静态配流LMCuS模型按照目标的优先级分为3层，用带初始解的迭代算法［8-10］依次求解，主要思路是：将上层的最优解作为下层的初始解，并动态增加避免上层目标退化约束.各子层为约束优化问题（constraint optimization problem， COP）［12］，针对这种NP-Hard问题，需要模型化简技术.CP在求解时首先通过约束传播算法（constraint propagation，CPr）［11-12］剔除不可能成为解的那部分变量取值，缩小解空间.但是约束传播算法缺乏完备性，不能将部分变量的取值扩展成完整解，基本回溯算法（backtracking algorithms，BT）［12］在实例化变量时没有利用任何启发式（Heuristics）信息，且未用已实例化变量进行相容性检查避免未来冲突，所以求解时间较长，本文基于以上分析设计了约束传播和启发式回溯的结合算法（CPrHBT）.

2 CPrHBT算法

CPrHBT算法主要分为两步：先通过约束传播化简模型，再用约束传播和启发式回溯结合算法求解.

2.1 约束传播算法

CP的约束传播算法［12］主要思想是：当变量论域被修改，则所有与其相关的变量都要调用减域算法修改论域，如此反复，直到所有变量的论域都约减到最小．约束传播包括减域（domain reduction，DR）［12］和传播两部分．减域是指为了满足约束，由某一变量的有限取值推导出其他变量只能取某些值，而达到论域约减的目的．本文使用ILOG CP Optimizer提供的弧边界相容（Arc-B-Consistency）减域算法［11-12，15］．设约束c包含的变量组成的集合为X（c），变量x的论域为D（x），x←v∈D（x）表示对变量x赋值表示有序变量赋值组合满足c．记解体顺序约束（5）为c1，则对于弧［12］，变量sD，i的减域算法如下：

步骤1由蕴含关系“⇒”得：如果c11∶eD，i＝＝1∧eD，i′＝＝1∧qD，i＜qD，i′不成立，则不会触发对sD，i论域约减；否则令c12∶sD，i＜sD，i′，则弧（sD，i，c1）的减域算法等价于弧（sD，i，c12）的减域算法，转步骤2；

步骤2令a＝tD，i，b＝te－pD，i，对于赋值sD，i←a和sD，i←b如果满足：

则称在约束c1中变量sD，i的论域D（sD，i）是弧边界相容的；否则令a←a＋1或b←b－1，循环执行步骤2，直至式（12）和式（13）同时成立，以达到减域目的．

记LMCuS模型的变量集为X，变量论域集为D，约束集为C，则约束传播算法步骤如下：

步骤1输入X、D和C，生成约束传播队列

步骤2如果Q＝Ø，返回“约束传播结束”；否则，从Q中依次选择并删除（c，x）；

步骤3调用减域算法修订x的值域D（x），如果D（x）＝Ø返回“无解”；如果D（x）被修改则转步骤4；如果D（x）不变转步骤2；

步骤4在Q中增加弧：，转步骤2．

2．2 估算最小目标函数的最大取值

回溯算法在求解最优化问题时利用启发式函数将每个部分解映射成数字值，在为变量赋值时，如果计算得到的启发式函数值越界，那么当前搜索路径以下的子树将被立刻修剪掉．本算法用目标函数作为启发式函数．初始阶段，对于目标函数（1），将其等价转换为等价函数的最大值为所有出发列车都未配流成功，即eF，j＝0，∀j＝1，…，n时取值为0；对于目标函数（2），令，其中r0，j由只满足不违编约束的到达列车di组成的集合；目标函数（3）的最大值为所有到达列车都解体和所有出发列车都编组，即eD，i＝1，∀i＝1，…，m和eF，j＝1，∀j＝1，…，n的情况下取值为

2．3 CPrHBT算法

与局部和随机算法相比，BT是系统化的完备搜索算法．与同样是完备的动态规划算法相比，BT算法同时只搜索一个解，只需要多项式空间成本．此外，在BT中可以引入先进策略来控制分支选择，提高算法效率．本文在BT算法中除了引入约束传播缩小解空间，还使用了变量动态排序启发式（variable ordering heuristics）［12］为分支选择提供决策支持，使得较早地检测出冲突，称为变量动态排序启发式回溯算法（HBT）．根据HBT的最先失败原则，本算法采用基于变量论域大小的启发式方法，即优先选择最小的xi作为下一个分支，如果最小论域的变量不唯一，则按次序选择．

CPrHBT算法步骤如下：

步骤1输入X、D和C，目标函数min f，由2．2节方法估算各目标函数最大值为u，令C←C∪｛f≤u｝，对（X，D，C）进行约束传播，是否存在x∈X，使得D（x）＝Ø，是，返回“无解”；否则，转步骤2；

步骤2如果第1个变量x1论域中D（x1）还有值没有尝试，则实例化x1，转步骤3；否则，如果存在解，则返回f及解s＝（x1←v1，…，xn←vn），否则，返回“无解”；

步骤3如果所有的变量都已实例化成功，则记录目标值f和解s，且令u＝f，转步骤2；否则，选择最小的xi为下一个实例化变量，转步骤4；

步骤4如果D（xi）中所有值都已尝试过，则回溯到变量xi－1；否则按照顺序实例化为xi＝vi，转步骤5；

步骤5如果与cj相关联的所有变量都已实例化，则检验是否满足cj，如果满足转步骤6；否则，转步骤4；

步骤6对与xi相关联的且未实例化变量进行约束传播，是否存在使得D（xk）＝Ø的变量xk，是，转步骤4；否则，转步骤3．

3 带初始解的迭代算法

按照1．3节求解思路，将通过CPrHBT算法得到的第i－1层最优解πi－1，作为第i层的初始解，并增加避免第i－1层目标值变劣约束，再调用CPrHBT算法求解第i层，如此迭代，直到i等于目标数．此算法比不带初始解的迭代算法［8-10］求解速度更快．如下所示为迭代算法步骤：

编组站静态配流LMCuS模型的带初始解迭代、约束传播和启发式回溯的混合算法在求解前和求解过程中都使用了约束传播算法，加快了冲突检查；同时，在选择实例化变量前对变量进行动态排序，增加了算法快速收敛的可能性，这些协调方法提高了算法的效率.

4 实验分析

4.1 实例验证

本算法是在Inter Core i3-2310M 2.1 GHz＆DRAM 2G＆Windows XP的PC机上使用ILOG CP Optimizer和Java编程实现.测试数据来自2013年7月21日某编组站上行方向，ts＝6：00，te＝12：00，到达和出发技术作业持续时间均为60 min，解体作业持续时间为25 min，编组作业持续时间为30 min，调车场容车数为3 500辆.调车场和到达场现车数据如表1所示，计划到达列车数据如表2所示，出发列车数据如表3所示.编组内容中“／”的前项表示车流属性ωk，后项表示属性为ωk的车辆数cD，i，k.

将表1、表2和表3作为模型的输入，根据车站列车到发强度和调度员对计划自动编制平均可接受时间上限得到算法总的求解时间为3 min，则设置每层求解时间上限为60 s，如图1所示为每层的求解过程.图1（a）为对f1求解得到最优解集π1；图1（b）为以π1为初始解对f2求解得到最优解集π2；图1（c）为以π2为初始解对f3求解得到最优解集π3，最后得到调车场现车是否被出发列车使用及到达列车解体作业情况如表4所示，出发列车实际编组作业情况和配流方案如表5所示.

4.2 结果分析

出发车10301的最晚开始编组时间＝发车时间－出发技术作业时间＝7：18，如果10301在此时刻之前编组，根据编组作业顺序约束（6）会导致其他出发车配流不成功，最终会使得主目标f1的值减少，所以10301配流不成功.同理出发车10463配流不成功.

表1 现车数据Tab.1 Data of the car-groups already on the classification tracks and receiving tracks

表2 计划到达列车数据Tab.2 Data of inbound trains

表3 计划出发列车数据Tab.3 Data of outbound trains

图1 LMCuS模型最优解求解过程Fig.1 Process of solving optimal solutions for the LMCuS model

表4 到达列车实际解体作业情况Tab.4 Results of disassembly operations of inbound trains

表5 出发列车配流和实际编组作业情况Tab.5 Results of wagon-flow allocation and assembly operations of outbound trains

由表5得到编组车种为“C”的车流总数为17.假如使用“在不破坏之前出发列车配流方案的前提下，保证每列出发列车车流来源数最少”的贪心算法求解，得到这6列车的配流方案为“SB04／C／35，31213／C／18”、“36035／C／13，41071／C／11，31013／C／29”、“31213／C／15，34025／C／31，26181／C／7”、“41293／C／9，41077／C／44”、“31013／C／6，85655／C／10，41297／C／47”和“85655／C／7，26181／C／6，41295／C／36，41293／C／8，41297／C／6”.从结果得到：虽然前几列车车流来源数和本算法得到的差不多，但是之后列车的车流来源数异常增多，使得贪心算法得到车流来源总数比回溯算法要多，所以回溯算法保证了全局最优.

到达列车“41291”中有40辆“C”车，多于“41295”的36辆，如果只是单纯求解目标函数（3）应该解体“41291”而不是“41295”，但为了保证主目标函数（1）达到最优，解体“41295”可以为出发列车“10467”提供27辆编组方向为“33”的车流；同理，可以得到“41299”不解体的原因.

4.3 与其他算法比较

由图1可得，本算法总的求解时间t为15.6 s，3个目标f1、f2和f3的最优值分别为150、54和3 065.以3个目标的最优值及总的求解时间为指标，分别与随机选取实例化变量的回溯算法A1、不带约束传播的算法A2和不带初始解的迭代算法A3比较，从表6可知本算法比其他算法效率要高，且求解质量优于算法A2.

表6 其他算法求解结果Tab.6 Results of other algorithms

5 结 论

本文针对编组站静态配流字典序多目标累积调度模型设计了带初始解迭代、约束传播和启发式回溯的混合算法.通过某编组站实际数据验证得到：算法求解时间符合现场对计划编制的实时性要求，与其他算法相比，本算法的效率和解的质量更高.

［1］ 王慈光.用表上作业法求解编组站配流问题的研究［J］.铁道学报，2002，24（4）：1-5.WANGCiguang.Studyonwagon-flowallocating problem in a marshalling station by using calculating method on-table［J］.Journal of the China Railway Society，2002，24（4）：1-5.

［2］ 王慈光.编组站静态配流网络模型［J］.交通运输工程与信息学报，2003，1（2）：67-71.WANG Ciguang.Network model of static wagon-flow allocation in a marshalling station［J］.Journal of Transportation Engineering and Information，2003，1（2）：67-71.

［3］ 景云，王慈光，王如义，等.运用学习规则求解编组站静态配流问题的研究［J］.铁道运输与经济，2010，32（1）：22-26.JING Yun，WANG Ciguang，WANG Ruyi，et al.Study on resolvingstaticwagon-flowallocationbyusing learning rules［J］.Railway Transport and Economy，2010，32（1）：22-26.

［4］ 薛锋，王慈光，罗建.双向编组站静态配流的优化［J］.西南交通大学学报，2008，43（2）：159-164.XUE Feng，WANG Ciguang，LUO Jian.Optimization forstaticwagon-flowallocationinbidirectional marshalling station［J］.Journal of Southwest Jiaotong University，2008，43（2）：159-164.

［5］ 赵军，彭其渊.单向编组站配流与调机运用综合问题［J］.铁道学报，2012，34（11）：1-9.ZHAO Jun，PENGQiyuan.Integratedwagon-flow allocation and shunting locomotive scheduling problem at single-direction marshalling station［J］.Journal of the China Railway Society，2012，34（11）：1-9.

［6］ 王世东，郑力，张智海，等.编组站阶段计划自动编制的数学模型及算法［J］.中国铁道科学，2008，29（2）：120-124.WANG Shidong，ZHENG Li，ZHANG Zhihai，et al.Mathematical model and algorithm for automatically programming the stage plan of marshalling station［J］.China Railway Science，2008，29（2）：120-124.

［7］ HOOKER J N.Logic，optimization，and constraint programming［J］.Informs Journal on Computing，2002，14（4）：295-321.

［8］ 纪昌明，段国圣，冯尚友.多目标动态规划分层解法与Pareto最优解［J］.系统工程理论与实践，1995（6）：76-80.JI Changming，DUAN Guosheng，FENG Shangyou.The hierarchical optimization criteria and pareto solution of multiobjectivedynamicprogramming［J］.Systems Engineering-Theory＆Practice，1995（6）：76-80.

［9］ 王明慧.字典序多目标多阶段决策问题的嘉量解法［J］.西南交通大学学报，2005，40（3）：390-393.WANG Minghui.Application of jar-metric principle for solving lexicographic order multiobject and multistage decision problems［J］.Journal of Southwest Jiaotong University，2005，40（3）：390-393.

［10］ OJHA A K，BISWAL K K.Lexicographic multiobjective geometric programming problems［J］.IJCSI International Journal of Computer ScienceIssues，2009，6（2）：20-24.

［11］ 刘露.基于约束传播技术的资源受限项目调度问题求解算法［D］.沈阳：东北大学，2011：10-30.

［12］ ROSSI F，BEEK P V，WALSH T.Handbook of constraint programming［M］.Pisa：Elsevier，2006：27-78，206-235，541-580，778-781.

［13］ 刘士新，郭哲，唐加福.具有优先关系的累积调度问题的约束传播算法［J］.自动化学报，2010，36（4）：603-609.LIUShixin，GUOZhe，TANGJiafu.Constraint propagation for cumulative scheduling problems with precedences［J］.ActaAutomaticaSinica，2010，36（4）：603-609.

［14］ 张居阳.基于约束的现代调度系统研究［D］.长春：吉林大学，2006.

［15］ LHOMMEO.Consistencytechniquesfornumeric CSPs［M］.San Francisco：Morgan Kaufmann Publishers，1998：232-238.

（中文编辑：唐 晴 英文编辑：周 尧）

Constraint Propagation and Heuristics Backtracking Algorithm for Static Wagon-Flow Allocation at a Marshalling Station

MA Liang1， GUO Jin1， CHEN Guangwei2
（1.School of Information Science and Technology，Southwest Jiaotong University，Chengdu 610031，China；2.Information and Technologies Center，MOR，Beijing 100860，China）

In order to improve the efficiency of stage planning，a hybrid algorithm was designed to solve the lexicographic multi-objective cumulative scheduling model of the static wagon-flow allocation problem at a marshalling station.The proposed algorithm is based on iteration method，constraint propagation technique and heuristic backtracking.The whole model is divided into three layers according to the lexicographical order of the multi-objective.The total priorities of the on-time outbound trains is maximized in the first sub-model，minimizing the total number of the inbound trains providing cars to each outbound trains is the objective in the second sub-model，while，the average dwell time of railcars in the station should be decreased as possible in the final sub-model.Firstly，each sub-model is simplified and the search space is reduced by constraint propagation algorithm.Then，the optimal solution is searched fast by the combined algorithm of heuristic backtracking and constraint propagation.In the lower sub-model，the optimal solution of the upper sub-model is considered as the initial solution，and the constraint is added to avoid degradation of the optimal value of the upper objective，so that the whole model is solved by the iteration algorithm.Experiment results from a marshalling station show that the total running time of the algorithm is less than 20 s，which meets the real-time requirements of scheduling in the field，and the algorithm can solve a better wagonflow allocation solution compared with other algorithms.

marshalling station；static wagon-flow allocation；constraint propagation；heuristics backtracking；constraint satisfaction problem

U292.16

A

0258-2724（2014）06-1116-07

10.3969／j.issn.0258-2724.2014.06.027

2013-08-31

铁道部科技研究开发计划重点课题（2010X010-F）；铁道部科技研究开发计划重大项目（2012X003-A）

马亮（1987－），男，博士研究生，研究方向为交通运输信息化理论与技术等，电话：028-87603029，E-mail：liangma9213＠163.com

马亮，郭进，陈光伟.编组站静态配流的约束传播和启发式回溯算法［J］.西南交通大学学报，2014，49（6）：1116-1122.