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

張雪松，馬 亮

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

a.決定每列到達(dá)列車的推峰時(shí)間、開始解體時(shí)間和解完時(shí)間；

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

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

d.決定每個(gè)出發(fā)計(jì)劃的牽出時(shí)間。

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

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

（9）將結(jié)果提交給編組站管理信息系統(tǒng)，由系統(tǒng)展示給站調(diào)，通過交互確認(rèn)計(jì)劃。

上述步驟是我們?cè)诙啻螌?shí)踐中提煉、總結(jié)出來的。其中決策的關(guān)鍵點(diǎn)是步驟（6）“調(diào)用約束規(guī)劃算法求解”。下面重點(diǎn)剖析該步驟的算法模型。

3 算法模型

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

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

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

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

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

決策包括兩項(xiàng)內(nèi)容：

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

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

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

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

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

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

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

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

（1）到達(dá)車開始解體時(shí)間：S={s1,s2, …,sm}；

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

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

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

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

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

4 模型求解

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

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

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

圖2 初始解生成流程圖

4.2 用搜索技術(shù)結(jié)合過程約束轉(zhuǎn)播改進(jìn)初始解

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

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

5 結(jié)束語

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

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

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

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

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

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

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

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

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