編組站靜態配流的約束傳播和啟發式回溯算法

馬 亮， 郭 進， 陳光偉

（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.