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

馬 亮， 郭 進， 陳光偉

（1.西南交通大學信息科學與技術學院，四川成都610031；2.鐵道部信息技術中心，北京100860）

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

馬 亮1， 郭 進1， 陳光偉2

（1.西南交通大學信息科學與技術學院，四川成都610031；2.鐵道部信息技術中心，北京100860）

為了提高階段計劃的編制效率，針對編組站靜態配流字典序多目標累積調度模型，設計了迭代、約束傳播和啟發式回溯的混合算法.該算法根據多目標的字典序將模型分為3層：第1層為配流成功的出發列車優先級總和最大化，第2層為出發列車車流來源總數最少化，第3層為車輛平均停留時間最短化.每層先通過約束傳播算法化簡模型、縮小解空間，再通過啟發式回溯算法和約束傳播技術聯合快速求解.上一層的最優解作為下一層的初始解，并動態增加避免上一層目標退化的約束，迭代求解每層的最優解.通過某編組站實際數據驗證表明，本算法耗時小于20 s，滿足現場對階段計劃編制的實時性要求，且求得的配流方案優于其他算法.

編組站；靜態配流；約束傳播；啟發式回溯；約束滿足問題

在鐵路編組站三層調度指揮體系中，階段計劃是一個班各階段工作的具體安排，是完成路局班計劃任務和指標的保證，也是編制調車作業計劃的主要依據，統籌分配和排程車站一個階段時間（3～4 h）內的各種資源和作業.主要包括配流、資源分配和作業排程等相互關聯的3個子計劃，其中配流是核心，分為靜態配流和動態配流［1-2］，靜態配流主要研究在解編順序確定的情況下優化的配流方案.