基于約束規(guī)劃的編組站階段作業(yè)計劃優(yōu)化研究

張雪松，馬 亮

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

編組站是鐵路樞紐的核心，是車流大量集散的基地，其作業(yè)組織效率直接影響著鐵路樞紐乃至整個路網的效率。在目前中國鐵路的組織型運輸模式中，編組站的作業(yè)組織包括作業(yè)組織計劃、行動計劃和具體行動計劃3個層次。其中，作業(yè)組織計劃包括日/班計劃，它們對應于鐵路局的日/班計劃，用來對當日/當班的生產經營任務進行總體安排和宏觀組織；行動計劃指階段作業(yè)計劃，用來組織一個3 h～4 h階段的具體作業(yè)安排，要具體考慮作業(yè)能力的限制和運輸資源的合理運用；具體行動計劃即調車計劃，是對實際車輛位移活動的具體安排。3個計劃中，階段作業(yè)計劃起著承上啟下的作用，既要考慮保證日/班計劃的實現(xiàn)，又要考慮各種實際資源限制，是整個編組站作業(yè)指揮的核心，也是編組站運輸組織優(yōu)化的關鍵。

1 編組站階段作業(yè)計劃介紹

從優(yōu)化的角度講，編組站階段作業(yè)計劃的內容包括：到發(fā)線使用計劃、本務機走行計劃、駝峰/調機使用計劃、配流方案/解編（含取送）順序4個部分。優(yōu)化的內容包括運力資源的分配和作業(yè)順序的確定。其中運力資源包括到/發(fā)線、本務機、駝峰、調機、分類線等，作業(yè)包括到達技術作業(yè)、推峰-解體、編組、出發(fā)技術作業(yè)、出發(fā)，以及取送、裝卸、機車整備等。最核心的業(yè)務是解體—編組作業(yè)，最稀缺的資源是駝峰和分類線，因此，配流方案/解編順序的確定是整個計劃的核心。在本質上，兩者是同一問題的兩個方面。確定解編順序的目的是為了優(yōu)化車流接續(xù)方案，確定了解編順序，配流方案就迎刃而解，兩者是密不可分的，需要同時考慮。解編順序一旦確定，就可以利用計算機精確地推算階段內任意時刻的現(xiàn)場狀態(tài)，并在此基礎上安排、優(yōu)化到發(fā)線使用、本務機走行和駝峰/調機使用計劃。

在設計配流方案/解編順序時，不可避免地涉及到出發(fā)列車計劃的確定。按照規(guī)定，出發(fā)計劃應由鐵路局計劃調度員下達。但是在實際作業(yè)中，由于車站調度人員對站內車流和技術設備情況掌握比較細致、準確，也經常需要參與出發(fā)計劃的確定，因此，在考慮配流方案時，必須同步考慮出發(fā)列車方案，否則，所形成的方案就無法真正運用到生產實踐。

綜上所述，編組站階段作業(yè)計劃優(yōu)化的核心是包含出發(fā)列車計劃的配流方案/解編順序的確定。計算機對上述問題的求解，可劃分為3種思路。思路1：經驗法。即根據(jù)現(xiàn)場作業(yè)人員的經驗，模擬人的思維、行為模式，設計特殊算法求解。這類方法基本上是基于先到先解的順序進行局部優(yōu)化、調整，雖然在個案上不乏實用的樣例，但很難形成通用系統(tǒng)。思路2：基于經典運籌學理論的研究。這方面的研究論述甚多[1～4]，例如將配流轉換為運輸問題，運用表上作業(yè)法進行求解。對階段計劃DSS中的優(yōu)化模型進行了全面構造和綜合集成，并針對這一問題形成了實用系統(tǒng)，在豐臺西等站進行了大量實踐。但總的說來，由于中國鐵路運輸非常復雜，配流的理論研究還未能取得突破性成果，還沒有形成具有通用性的應用。 思路3：非經典優(yōu)化方法[5～6]。所謂非經典優(yōu)化方法，是相對經典運籌學理論而言的，門類較多。如約束規(guī)劃、產生式系統(tǒng)、啟發(fā)式算法等都屬于這一范疇。利用遺傳算法求解進行解編順序的方法，即屬于非經典方法。編組站配流問題屬于組合優(yōu)化問題。它涉及因素眾多，各因素之間的關聯(lián)千絲萬縷，模型異常復雜，不具有良性結構，經典算法難以發(fā)揮其長處。相比之下，非經典方法通常能更貼近生產實踐，而且不需要高深復雜的數(shù)學理論知識，更能為現(xiàn)場人員所接受，并且能夠讓實踐經驗豐富的業(yè)務人員參與到項目研發(fā)過程中來，更易于發(fā)揮經驗和主觀能力的作用，更加適合編組站階段計劃的優(yōu)化問題。

本文基于約束規(guī)劃理論，依托IBM ILOG工具，結合多年的編組站應用和優(yōu)化研究實踐，提出了一套求解編組站階段作業(yè)計劃生成與優(yōu)化的方法體系，并就其核心算法—配流方案/解編順序問題建立了數(shù)學模型，給出計算機實現(xiàn)方法。

2 基于約束規(guī)劃求解的基本思路

約束規(guī)劃[7]（Constraint Programming）是解決約束滿足問題（CSP，Constraint Satisfaction Problem）的方法。一個約束滿足問題包括有限變量集、每個變量的有限論域和有限約束集。每條約束限制了變量集賦值的組合。約束滿足問題的解是為每個變量賦一個對應論域上的值，使之滿足所有的約束。求解約束滿足問題的目標是找到一個可行解或是全部可行解。約束規(guī)劃廣泛地借鑒了人工智能、計算機科學和運籌學的技術，從某種意義上講，與數(shù)學規(guī)劃（Mathematical Programming）類似，用戶可以定義決策變量、聲明優(yōu)化目標，并指定關于決策變量可行解的一組約束。

借助于IBM ILOG工具，研究人員可以將精力聚焦到描述業(yè)務目標和約束上來，而不去關心具體的實現(xiàn)細節(jié)。當確認所建模型能夠得到滿意解后，再集中精力研究模型優(yōu)化，解決性能問題。按照這種思路，在早期建模階段，可以邀請業(yè)務人員參與，分享其業(yè)務經驗，使模型在設計之初就能從實際出發(fā)，貼近現(xiàn)場的作業(yè)習慣和思維方式。即使在后期調優(yōu)階段，業(yè)務人員仍然能發(fā)揮較大作用，根據(jù)經驗增加約束，有效地縮減解空間規(guī)模。

求解約束規(guī)劃的關鍵是性能問題。當決策變量達到一定規(guī)模時，其性能會發(fā)生突變。因此，在建立約束規(guī)劃模型時，首先要分解問題域，在不破壞業(yè)務完整性和連續(xù)性的前提下，把復雜問題分解成一系列簡單問題。同時，要根據(jù)約束規(guī)劃的特點設計應用，將數(shù)據(jù)預處理，結果的細化、校驗、修正剝離出來，約束規(guī)劃只負責最核心的配流和解編順序的確定。這一思路使應用程序設計和約束規(guī)劃算法設計全面結合起來，兩者相得益彰，充分發(fā)揮各自的優(yōu)勢，最終構建成統(tǒng)一、完整的應用系統(tǒng)。

按照上述思路，設計的求解編組站階段作業(yè)計劃生成與優(yōu)化問題的基本步驟如下：

（1）從編組站管理信息系統(tǒng)提取數(shù)據(jù)。包括編組站結存車輛、到達場到達列車、預計到達列車（預確報）、出發(fā)場待發(fā)列車、鐵路局下達的班計劃、當前階段作業(yè)計劃、已編制的調車計劃等。

（2）調用編組站管理信息系統(tǒng)的推流服務，推算出待編階段起始時刻的車流。

（3）對步驟（2）推算的車流數(shù)據(jù)進行預處理，挑選出不參加編組的車輛（如扣修車、本站待卸車等），并將其余車輛（即參加編組車輛）按特征分組。經本步處理后，車流分類一律用方向號表示，不再使用重車按方向、空車按車種、非運用車按標記的分類表示方式。

（4）計算每列列車解體需要的時間。解體時間包括推峰時間和分解時間兩部分。分解時間按解體鉤數(shù)和送禁溜次數(shù)計算。

（5）對班計劃（或編組計劃）的出發(fā)計劃進行整理，計算并表示出每列車的編組內容、最晚開編時間（在此前所有相關到達列車的解體工作都要完成）、夠軸條件（本步驟按車數(shù)掌握）等。

（6）調用約束規(guī)劃算法，求解以下決策變量值。決策的結果通常不只是一個可用解，而是一組可用解。決策內容包括：

a.決定每列到達列車的推峰時間、開始解體時間和解完時間；

b.決定哪些出發(fā)列車被選用；

c.決定所選用出發(fā)列車的編組內容；

d.決定每個出發(fā)計劃的牽出時間。

（7）對規(guī)劃結果進行校驗、完善、修正，包括確定每列出發(fā)列車的具體車流來源，精確計算軸重和軸長，檢驗編組隔離限制，以及為每項任務分配具體駝峰、調機等資源。在步驟（6）中，出于效率考慮，駝峰等資源均是作為資源池考慮，僅約束了其能力（并行作業(yè)數(shù)量），而沒有分配到具體資源，因此，需要在事后再次分配具體資源。

（8）按照步驟7得出的結果，安排到發(fā)線使用等其它計劃。

（9）將結果提交給編組站管理信息系統(tǒng)，由系統(tǒng)展示給站調，通過交互確認計劃。

上述步驟是我們在多次實踐中提煉、總結出來的。其中決策的關鍵點是步驟（6）“調用約束規(guī)劃算法求解”。下面重點剖析該步驟的算法模型。

3 算法模型

基于約束規(guī)劃求解配流方案/解編順序問題的基本元素是車輛。為縮減算法規(guī)模，降低決策變量數(shù)量，采用了車組表示車流的方式，在模型中不考慮具體車輛。這種方式在判斷列車滿軸時只能通過車數(shù)判斷，可能造成一定失真，但決策變量得到了大幅度削減。而由于失真所產生的問題，可以在后續(xù)處理中通過計劃微調進行解決，不會影響決策結果。

采用了列車—車組表示車流的簡化模型可描述如下：

階段時間[ts,te]內，m個編組方向組成集合為D={d1,d2,…,dm}。為統(tǒng)一表示，所有車輛，包括空車、非運用、作業(yè)車等均用方向表示。

mA個到達列車組成集合為A={ai|ai=}，其中，t1i為ai的最早開始解體時刻，即列車到達時間加上標準技術作業(yè)時間，t2i為ai解體占用時間，在前序步驟中計算得出；Pi為列車編組集合，每個元素為同一方向的一組車，可表示為Pi={ni1,ni2,…,nim}，其中nik為方向dk(dk∈D)的車數(shù)。為統(tǒng)一表示，到達場、編組場車輛也表示在集合A中，到達場待解列車的tji為max(tji,ts)，其中，tji為ai實際技術作業(yè)完畢時間。編組場列車t1i=ts，t2i=0。

mF個出發(fā)車組成集合為F={fj|fj=}，其中，tj為fj的發(fā)車時間；fullj為fj的滿軸車數(shù)；Dj={λj1,λj2,…λjm}為fj的編組方向要求，若fj編組包括方向dk，則λjk=1，否則為0。

決策包括兩項內容：

（1）到達列車解體開始時間集合S={s1,s2,…,sm}，其中si為到達列車ai的開始解體時間；

（2）出發(fā)列車計劃集合為DF={dfj|dfj=}，其中tmj為編組完成時間，optj為是否選擇該出發(fā)車，取值為[0, 1]，Pj為出發(fā)列車編組，表示同到達編組。

車組建模的關鍵，是按車流方向表示到發(fā)接續(xù)關系，模型中僅完成到達解體時間、出發(fā)編組時間和出發(fā)車流組成的決策，而不進行具體配流方案的制定，從而提高算法效率。算法的核心是車流表示。在ILOG環(huán)境下，通過車流累積函數(shù)（Cumulative Function）的概念來表示某一方向的車流隨著作業(yè)的動態(tài)變化。

定義1：車流累積函數(shù)是階躍函數(shù)，具體表現(xiàn)為：以時間為橫軸，車流數(shù)為縱軸，車流隨著各作業(yè)的實施而進行累加或者累減。記（+/－）Θ（n,t），表示t時刻累加/累減了n個車流；（+/－）Θ（0,n,t），表示t時刻累加/累減[0,n]個車流，其中，n,t∈Z*。

定義2 ：車流累積函數(shù)的高度（+/－）heightAt（Θ,t）表示時刻t累積函數(shù)Θ的變化值，為正數(shù)。

圖1 車流累積函數(shù)

圖1 為車流累積函數(shù)，分別累加了n1和[0,n2]個車流，累減了n3個車流。

通過上述分析得到模型的決策變量和決策表達式，包括：

（1）到達車開始解體時間：S={s1,s2, …,sm}；

（2）出發(fā)車決策內容：DF={dfj|dfj=}；

（3）整個階段時間各方向車流累積函數(shù)：

(∨i∨j∨k)Ni,j,k=Θ(nik,si)－Θ(0,fullj,tmj)g λjk

（4）出發(fā)車fj使用到達車ai方向dk的車數(shù)：(∨i∨j∨k)HZi,j,k=－h(huán)eightAt(Ni,j,k,tmj)gλjk出發(fā)車滿軸約束條件如下：

模型的目標為出發(fā)車最多：

4 模型求解

本研究通過約束傳播機制和搜索策略[10～11]對模型進行求解，其中約束傳播機制分為：初始化約束傳播和搜索過程約束傳播，主要目的是對可行解域進行縮減。初始化約束傳播是在初始可行解集的基礎上刪除那些不可能成為解的那部分域；而搜索過程約束傳播與搜索策略結合在剩余搜索空間的基礎上刪除那些不滿足約束的解集，并通過搜索樹對解進行搜索。

4.1 利用初始化約束傳播得到初始解

本研究采用系統(tǒng)搜索算法獲得初始解，先確定源車流的解體順序和出發(fā)車的編組順序，然后對目標函數(shù)進行枚舉賦值以找到可行解，主要流程如圖2。

圖2 初始解生成流程圖

4.2 用搜索技術結合過程約束轉播改進初始解

得到初始解后，將它作為當前解，利用禁忌搜索算法的鄰域函數(shù)隨機改變當前解的調整模式的某一個分量，產生相對于當前解的移動。這里，調整模式是指所有調整變量的一組取值。在每一步移動之后，利用約束傳播算法求解批量變量，并計算目標函數(shù)值。選擇鄰域中非禁忌或解禁后目標函數(shù)值最大的解編順序作為新的當前解，繼續(xù)產生移動得到新的解，從而不斷地對解進行改進。禁忌搜索流程如圖3。

圖3 搜索技術搜索最優(yōu)解

5 結束語

本文在對編組站階段作業(yè)計劃優(yōu)化問題系統(tǒng)分析的基礎上，提出了求解的基本方法，并對方法的核心部分建立了基于約束規(guī)劃的模型和求解方法。方法經大量現(xiàn)場數(shù)據(jù)仿真試驗，已基本接近人工編制計劃的水平。后續(xù)工作中，我們準備從業(yè)務和技術兩方面努力。在業(yè)務方面，通過比對模型結果，發(fā)現(xiàn)模型的不足，不斷修改、增加約束條件，使結果更加優(yōu)化，逐漸趕上并超過人工編制的水平，增強算法的適用性。在技術方面，深入探索，不斷提高算法的性能，保證能夠滿足現(xiàn)場作業(yè)的時間要求。

本文介紹的優(yōu)化方法的目標，鎖定在編組站綜合自動化系統(tǒng)的“智能化”領域，期望通過計算機替代人的腦力勞動，實現(xiàn)編組站運輸組織的宏觀優(yōu)化，推動編組站自動化水平的不斷提高。更進一步，依托本算法良好的說明特性和聯(lián)合求解的優(yōu)勢，可以將它運用于鐵路局計劃調度應用，實現(xiàn)局站一體化的目標。

[1]王慈光.用表上作業(yè)法求解編組站配流問題的研究[J]. 鐵道學報，2002，24（4）：1-5.

[2]何世偉，宋 瑞，朱松年. 鐵路編組站階段計劃編制的模型及其算法研究[J].系統(tǒng)工程理論與實踐，1997，2（2）：88-94.

[3]薛 鋒，王慈光，羅 建. 雙向編組站靜態(tài)配流的優(yōu)化[J].西南交通大學學報， 2008，43（2）：159-164.

[4]崔炳謀. 鐵路編組站綜合自動化若干問題的研究[D]. 北京：鐵道科學研究院，2005：3-6.

[5]王世東，鄭 力，張智海，等. 編組站階段計劃自動編制的數(shù)學模型及算法[J].中國鐵道科學，2008，29（2）：120-125.

[6]姜英新，孫吉貴. 約束滿足問題求解及ILOG SOLVER系統(tǒng)簡介[J]. 吉林大學學報（理學版），2002，（1）：53-60.

[7]竺 東，楊建軍.基于約束規(guī)劃的調整時間與順序有關的Job Shop調度研究[J]. 先進制造工藝技術，2007，24（2）：53-63.