編組站靜態(tài)配流的約束傳播和啟發(fā)式回溯算法

馬 亮， 郭 進(jìn)， 陳光偉

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

編組站靜態(tài)配流的約束傳播和啟發(fā)式回溯算法

馬 亮1， 郭 進(jìn)1， 陳光偉2

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

為了提高階段計(jì)劃的編制效率，針對編組站靜態(tài)配流字典序多目標(biāo)累積調(diào)度模型，設(shè)計(jì)了迭代、約束傳播和啟發(fā)式回溯的混合算法.該算法根據(jù)多目標(biāo)的字典序?qū)⒛Ｐ头譃?層：第1層為配流成功的出發(fā)列車優(yōu)先級(jí)總和最大化，第2層為出發(fā)列車車流來源總數(shù)最少化，第3層為車輛平均停留時(shí)間最短化.每層先通過約束傳播算法化簡模型、縮小解空間，再通過啟發(fā)式回溯算法和約束傳播技術(shù)聯(lián)合快速求解.上一層的最優(yōu)解作為下一層的初始解，并動(dòng)態(tài)增加避免上一層目標(biāo)退化的約束，迭代求解每層的最優(yōu)解.通過某編組站實(shí)際數(shù)據(jù)驗(yàn)證表明，本算法耗時(shí)小于20 s，滿足現(xiàn)場對階段計(jì)劃編制的實(shí)時(shí)性要求，且求得的配流方案優(yōu)于其他算法.

編組站；靜態(tài)配流；約束傳播；啟發(fā)式回溯；約束滿足問題

在鐵路編組站三層調(diào)度指揮體系中，階段計(jì)劃是一個(gè)班各階段工作的具體安排，是完成路局班計(jì)劃任務(wù)和指標(biāo)的保證，也是編制調(diào)車作業(yè)計(jì)劃的主要依據(jù)，統(tǒng)籌分配和排程車站一個(gè)階段時(shí)間（3～4 h）內(nèi)的各種資源和作業(yè).主要包括配流、資源分配和作業(yè)排程等相互關(guān)聯(lián)的3個(gè)子計(jì)劃，其中配流是核心，分為靜態(tài)配流和動(dòng)態(tài)配流［1-2］，靜態(tài)配流主要研究在解編順序確定的情況下優(yōu)化的配流方案.

針對靜態(tài)配流問題，文獻(xiàn)［1］使用表上作業(yè)法求解靜態(tài)配流運(yùn)輸模型；文獻(xiàn)［2］用最小費(fèi)用最大流算法求解靜態(tài)配流網(wǎng)絡(luò)模型；文獻(xiàn)［3］設(shè)計(jì)了靜態(tài)配流網(wǎng)絡(luò)模型的學(xué)習(xí)算法；文獻(xiàn)［4］用禁忌搜索策略和配流網(wǎng)絡(luò)相結(jié)合的算法求解靜態(tài)配流的雙層多目標(biāo)整數(shù)規(guī)劃模型；文獻(xiàn)［5］用有偏隨機(jī)鍵遺傳算法求解單向編組站配流的混合整數(shù)線性規(guī)劃模型；文獻(xiàn)［6］針對配流問題NPC特點(diǎn)，設(shè)計(jì)了先到先服務(wù)的啟發(fā)式算法.以往研究都是設(shè)計(jì)智能算法求解靜態(tài)配流數(shù)學(xué)規(guī)劃（mathematical programming，MP）模型，這些算法缺乏約束推理技術(shù)，導(dǎo)致求解時(shí)間較長；此外，算法通用性不好，問題的一個(gè)微小變化就可能導(dǎo)致算法不再適用.本文基于約束程序（constraint programming，CP）［7］理論，針對編組站靜態(tài)配流字典序多目標(biāo)累積調(diào)度（lexicographic multi-objective cumulative scheduling，LMCuS）模型，設(shè)計(jì)了帶初始解的迭代［8-10］、約束傳播［11-12］和啟發(fā)式回溯［12］的混合算法.經(jīng)過某編組站現(xiàn)場數(shù)據(jù)試驗(yàn)表明該算法的實(shí)用性和計(jì)算的高效性.

1 編組站靜態(tài)配流LMCuS模型

編組站靜態(tài)配流是多目標(biāo)車流資源受限項(xiàng)目調(diào)度問題（resource constrained project scheduling problem，RCPSP）［7，13］，到達(dá)車流容量大于1，可以同時(shí)為多個(gè)出發(fā)列車提供車流，所以也是資源累積調(diào)度問題（cumulativeschedulingproblem，CuSP）［11］.以往的MP模型都是將約束寫成算術(shù)表達(dá)式，針對復(fù)雜問題需要增加額外的變量和約束；而且MP只提供了約束的全局處理，針對包含多種約束的混合問題建模困難.此外，在部分研究中使用線性加權(quán)和法將多目標(biāo)變成單目標(biāo)，這種方法需要針對不同的數(shù)據(jù)環(huán)境確定不同權(quán)值.本文基于CP的約束謂詞［7］建模方法、字典序多目標(biāo)優(yōu)化（lexicographic multi-objective optimization，LMO）［8-10］和CuSP理論建立了編組站靜態(tài)配流LMCuS模型.為了便于建模，不妨將編組場現(xiàn)車、到達(dá)場待解車列、計(jì)劃到達(dá)列車和交換場、貨場、車輛段、專用線等地點(diǎn)待取車組統(tǒng)稱為“到達(dá)列車”.

1.1 字典序目標(biāo)

編組站靜態(tài)配流LMCuS模型基于LMO理論，按照現(xiàn)場到發(fā)車流不均衡等實(shí)際情況和現(xiàn)場車站調(diào)度員的決策偏好建立具有字典序的3個(gè)目標(biāo).

目標(biāo)（1）為配流成功的出發(fā)列車優(yōu)先級(jí)總和最大，此目標(biāo)考慮了到發(fā)車流不均衡，出發(fā)列車不能都滿軸出發(fā)的情況，其中：變量eF，j∈｛0，1｝為出發(fā)列車fj編組作業(yè)JF，j實(shí)施標(biāo)志；lj為fj的優(yōu)先級(jí)；n為出發(fā)列車總數(shù).

目標(biāo)（2）為出發(fā)列車車流來源總數(shù)最少，考慮了“配流照顧解編作業(yè)”原則，其中：oj＝rj表示出發(fā)列車fj車流來源數(shù)；rj為向fj提供車流的到達(dá)列車集合，初始令rj＝?；對于fj所有的車流來源cF，i，j，k，如果cF，i，j，k＞0，則rj＝rj∪｛di｝，變量cF，i，j，k∈［0，aj］為fj消耗到達(dá)列車di中編組方向?yàn)棣豮的車輛數(shù)；aj為fj的軸重和換長要求，用車輛數(shù)代替.

目標(biāo)（3）為使到達(dá)車流盡量先到先發(fā)，提高了先到車輛的利用率，減少了車輛在站的平均停留時(shí)間，其中：變量eD，i∈｛0，1｝為di解體作業(yè)JD，i執(zhí)行標(biāo)志；m為到達(dá)列車數(shù).

式（4）為3個(gè)目標(biāo)的字典序，從左到右優(yōu)先級(jí)依次降低.

1.2 約 束

LMCuS模型使用CP約束謂詞［7］建模方法，實(shí)現(xiàn)了變量之間的各種關(guān)系，提高了模型的可讀性，縮小了模型規(guī)模.其中，車流資源容量和調(diào)車場容車數(shù)限制等約束基于CuSP［11］理論實(shí)現(xiàn).

式（8）為到發(fā)接續(xù)和不違編約束，其中：λj，k為編組特征值，若編組計(jì)劃中允許fj開行ωk的車，則λj，k＝1，否則λj，k＝0.

約束（9）為配流滿軸約束，其中：aj為滿軸車輛數(shù).

約束（10）為車流資源容量限制約束，即配流過程中，所有出發(fā)列車消耗車流數(shù)不超過車流資源容量.

約束（11）表示在配流過程中調(diào)車場集結(jié)的車流數(shù)不超過調(diào)車場容車數(shù)V.

與以往模型［1-6］相比，LMCuS模型考慮了到發(fā)車流不均衡、配流照顧解編作業(yè)和調(diào)車場容量限制等因素，更接近現(xiàn)場實(shí)際需求.與MP模型中每個(gè)約束必須被表示成（非）線性方程相比，基于CP約束謂詞［7］建立的每條約束可以分別建模，可以進(jìn)一步形成更復(fù)雜的混合約束或者約束松弛，不會(huì)影響其他約束［14］.

1.3 模型求解思路

編組站靜態(tài)配流LMCuS模型按照目標(biāo)的優(yōu)先級(jí)分為3層，用帶初始解的迭代算法［8-10］依次求解，主要思路是：將上層的最優(yōu)解作為下層的初始解，并動(dòng)態(tài)增加避免上層目標(biāo)退化約束.各子層為約束優(yōu)化問題（constraint optimization problem， COP）［12］，針對這種NP-Hard問題，需要模型化簡技術(shù).CP在求解時(shí)首先通過約束傳播算法（constraint propagation，CPr）［11-12］剔除不可能成為解的那部分變量取值，縮小解空間.但是約束傳播算法缺乏完備性，不能將部分變量的取值擴(kuò)展成完整解，基本回溯算法（backtracking algorithms，BT）［12］在實(shí)例化變量時(shí)沒有利用任何啟發(fā)式（Heuristics）信息，且未用已實(shí)例化變量進(jìn)行相容性檢查避免未來沖突，所以求解時(shí)間較長，本文基于以上分析設(shè)計(jì)了約束傳播和啟發(fā)式回溯的結(jié)合算法（CPrHBT）.

2 CPrHBT算法

CPrHBT算法主要分為兩步：先通過約束傳播化簡模型，再用約束傳播和啟發(fā)式回溯結(jié)合算法求解.

2.1 約束傳播算法

CP的約束傳播算法［12］主要思想是：當(dāng)變量論域被修改，則所有與其相關(guān)的變量都要調(diào)用減域算法修改論域，如此反復(fù)，直到所有變量的論域都約減到最小．約束傳播包括減域（domain reduction，DR）［12］和傳播兩部分．減域是指為了滿足約束，由某一變量的有限取值推導(dǎo)出其他變量只能取某些值，而達(dá)到論域約減的目的．本文使用ILOG CP Optimizer提供的弧邊界相容（Arc-B-Consistency）減域算法［11-12，15］．設(shè)約束c包含的變量組成的集合為X（c），變量x的論域?yàn)镈（x），x←v∈D（x）表示對變量x賦值表示有序變量賦值組合滿足c．記解體順序約束（5）為c1，則對于弧［12］，變量sD，i的減域算法如下：

步驟1由蘊(yùn)含關(guān)系“?”得：如果c11∶eD，i＝＝1∧eD，i′＝＝1∧qD，i＜qD，i′不成立，則不會(huì)觸發(fā)對sD，i論域約減；否則令c12∶sD，i＜sD，i′，則?。╯D，i，c1）的減域算法等價(jià)于?。╯D，i，c12）的減域算法，轉(zhuǎn)步驟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，循環(huán)執(zhí)行步驟2，直至式（12）和式（13）同時(shí)成立，以達(dá)到減域目的．

記LMCuS模型的變量集為X，變量論域集為D，約束集為C，則約束傳播算法步驟如下：

步驟1輸入X、D和C，生成約束傳播隊(duì)列

步驟2如果Q＝?，返回“約束傳播結(jié)束”；否則，從Q中依次選擇并刪除（c，x）；

步驟3調(diào)用減域算法修訂x的值域D（x），如果D（x）＝?返回“無解”；如果D（x）被修改則轉(zhuǎn)步驟4；如果D（x）不變轉(zhuǎn)步驟2；

步驟4在Q中增加?。海D(zhuǎn)步驟2．

2．2 估算最小目標(biāo)函數(shù)的最大取值

回溯算法在求解最優(yōu)化問題時(shí)利用啟發(fā)式函數(shù)將每個(gè)部分解映射成數(shù)字值，在為變量賦值時(shí)，如果計(jì)算得到的啟發(fā)式函數(shù)值越界，那么當(dāng)前搜索路徑以下的子樹將被立刻修剪掉．本算法用目標(biāo)函數(shù)作為啟發(fā)式函數(shù)．初始階段，對于目標(biāo)函數(shù)（1），將其等價(jià)轉(zhuǎn)換為等價(jià)函數(shù)的最大值為所有出發(fā)列車都未配流成功，即eF，j＝0，?j＝1，…，n時(shí)取值為0；對于目標(biāo)函數(shù)（2），令，其中r0，j由只滿足不違編約束的到達(dá)列車di組成的集合；目標(biāo)函數(shù)（3）的最大值為所有到達(dá)列車都解體和所有出發(fā)列車都編組，即eD，i＝1，?i＝1，…，m和eF，j＝1，?j＝1，…，n的情況下取值為

2．3 CPrHBT算法

與局部和隨機(jī)算法相比，BT是系統(tǒng)化的完備搜索算法．與同樣是完備的動(dòng)態(tài)規(guī)劃算法相比，BT算法同時(shí)只搜索一個(gè)解，只需要多項(xiàng)式空間成本．此外，在BT中可以引入先進(jìn)策略來控制分支選擇，提高算法效率．本文在BT算法中除了引入約束傳播縮小解空間，還使用了變量動(dòng)態(tài)排序啟發(fā)式（variable ordering heuristics）［12］為分支選擇提供決策支持，使得較早地檢測出沖突，稱為變量動(dòng)態(tài)排序啟發(fā)式回溯算法（HBT）．根據(jù)HBT的最先失敗原則，本算法采用基于變量論域大小的啟發(fā)式方法，即優(yōu)先選擇最小的xi作為下一個(gè)分支，如果最小論域的變量不唯一，則按次序選擇．

CPrHBT算法步驟如下：

步驟1輸入X、D和C，目標(biāo)函數(shù)min f，由2．2節(jié)方法估算各目標(biāo)函數(shù)最大值為u，令C←C∪｛f≤u｝，對（X，D，C）進(jìn)行約束傳播，是否存在x∈X，使得D（x）＝?，是，返回“無解”；否則，轉(zhuǎn)步驟2；

步驟2如果第1個(gè)變量x1論域中D（x1）還有值沒有嘗試，則實(shí)例化x1，轉(zhuǎn)步驟3；否則，如果存在解，則返回f及解s＝（x1←v1，…，xn←vn），否則，返回“無解”；

步驟3如果所有的變量都已實(shí)例化成功，則記錄目標(biāo)值f和解s，且令u＝f，轉(zhuǎn)步驟2；否則，選擇最小的xi為下一個(gè)實(shí)例化變量，轉(zhuǎn)步驟4；

步驟4如果D（xi）中所有值都已嘗試過，則回溯到變量xi－1；否則按照順序?qū)嵗癁閤i＝vi，轉(zhuǎn)步驟5；

步驟5如果與cj相關(guān)聯(lián)的所有變量都已實(shí)例化，則檢驗(yàn)是否滿足cj，如果滿足轉(zhuǎn)步驟6；否則，轉(zhuǎn)步驟4；

步驟6對與xi相關(guān)聯(lián)的且未實(shí)例化變量進(jìn)行約束傳播，是否存在使得D（xk）＝?的變量xk，是，轉(zhuǎn)步驟4；否則，轉(zhuǎn)步驟3．

3 帶初始解的迭代算法

按照1．3節(jié)求解思路，將通過CPrHBT算法得到的第i－1層最優(yōu)解πi－1，作為第i層的初始解，并增加避免第i－1層目標(biāo)值變劣約束，再調(diào)用CPrHBT算法求解第i層，如此迭代，直到i等于目標(biāo)數(shù)．此算法比不帶初始解的迭代算法［8-10］求解速度更快．如下所示為迭代算法步驟：

編組站靜態(tài)配流LMCuS模型的帶初始解迭代、約束傳播和啟發(fā)式回溯的混合算法在求解前和求解過程中都使用了約束傳播算法，加快了沖突檢查；同時(shí)，在選擇實(shí)例化變量前對變量進(jìn)行動(dòng)態(tài)排序，增加了算法快速收斂的可能性，這些協(xié)調(diào)方法提高了算法的效率.

4 實(shí)驗(yàn)分析

4.1 實(shí)例驗(yàn)證

本算法是在Inter Core i3-2310M 2.1 GHz＆DRAM 2G＆Windows XP的PC機(jī)上使用ILOG CP Optimizer和Java編程實(shí)現(xiàn).測試數(shù)據(jù)來自2013年7月21日某編組站上行方向，ts＝6：00，te＝12：00，到達(dá)和出發(fā)技術(shù)作業(yè)持續(xù)時(shí)間均為60 min，解體作業(yè)持續(xù)時(shí)間為25 min，編組作業(yè)持續(xù)時(shí)間為30 min，調(diào)車場容車數(shù)為3 500輛.調(diào)車場和到達(dá)場現(xiàn)車數(shù)據(jù)如表1所示，計(jì)劃到達(dá)列車數(shù)據(jù)如表2所示，出發(fā)列車數(shù)據(jù)如表3所示.編組內(nèi)容中“／”的前項(xiàng)表示車流屬性ωk，后項(xiàng)表示屬性為ωk的車輛數(shù)cD，i，k.

將表1、表2和表3作為模型的輸入，根據(jù)車站列車到發(fā)強(qiáng)度和調(diào)度員對計(jì)劃自動(dòng)編制平均可接受時(shí)間上限得到算法總的求解時(shí)間為3 min，則設(shè)置每層求解時(shí)間上限為60 s，如圖1所示為每層的求解過程.圖1（a）為對f1求解得到最優(yōu)解集π1；圖1（b）為以π1為初始解對f2求解得到最優(yōu)解集π2；圖1（c）為以π2為初始解對f3求解得到最優(yōu)解集π3，最后得到調(diào)車場現(xiàn)車是否被出發(fā)列車使用及到達(dá)列車解體作業(yè)情況如表4所示，出發(fā)列車實(shí)際編組作業(yè)情況和配流方案如表5所示.

4.2 結(jié)果分析

出發(fā)車10301的最晚開始編組時(shí)間＝發(fā)車時(shí)間－出發(fā)技術(shù)作業(yè)時(shí)間＝7：18，如果10301在此時(shí)刻之前編組，根據(jù)編組作業(yè)順序約束（6）會(huì)導(dǎo)致其他出發(fā)車配流不成功，最終會(huì)使得主目標(biāo)f1的值減少，所以10301配流不成功.同理出發(fā)車10463配流不成功.

表1 現(xiàn)車數(shù)據(jù)Tab.1 Data of the car-groups already on the classification tracks and receiving tracks

表2 計(jì)劃到達(dá)列車數(shù)據(jù)Tab.2 Data of inbound trains

表3 計(jì)劃出發(fā)列車數(shù)據(jù)Tab.3 Data of outbound trains

圖1 LMCuS模型最優(yōu)解求解過程Fig.1 Process of solving optimal solutions for the LMCuS model

表4 到達(dá)列車實(shí)際解體作業(yè)情況Tab.4 Results of disassembly operations of inbound trains

表5 出發(fā)列車配流和實(shí)際編組作業(yè)情況Tab.5 Results of wagon-flow allocation and assembly operations of outbound trains

由表5得到編組車種為“C”的車流總數(shù)為17.假如使用“在不破壞之前出發(fā)列車配流方案的前提下，保證每列出發(fā)列車車流來源數(shù)最少”的貪心算法求解，得到這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”.從結(jié)果得到：雖然前幾列車車流來源數(shù)和本算法得到的差不多，但是之后列車的車流來源數(shù)異常增多，使得貪心算法得到車流來源總數(shù)比回溯算法要多，所以回溯算法保證了全局最優(yōu).

到達(dá)列車“41291”中有40輛“C”車，多于“41295”的36輛，如果只是單純求解目標(biāo)函數(shù)（3）應(yīng)該解體“41291”而不是“41295”，但為了保證主目標(biāo)函數(shù)（1）達(dá)到最優(yōu)，解體“41295”可以為出發(fā)列車“10467”提供27輛編組方向?yàn)椤?3”的車流；同理，可以得到“41299”不解體的原因.

4.3 與其他算法比較

由圖1可得，本算法總的求解時(shí)間t為15.6 s，3個(gè)目標(biāo)f1、f2和f3的最優(yōu)值分別為150、54和3 065.以3個(gè)目標(biāo)的最優(yōu)值及總的求解時(shí)間為指標(biāo)，分別與隨機(jī)選取實(shí)例化變量的回溯算法A1、不帶約束傳播的算法A2和不帶初始解的迭代算法A3比較，從表6可知本算法比其他算法效率要高，且求解質(zhì)量優(yōu)于算法A2.

表6 其他算法求解結(jié)果Tab.6 Results of other algorithms

5 結(jié) 論

本文針對編組站靜態(tài)配流字典序多目標(biāo)累積調(diào)度模型設(shè)計(jì)了帶初始解迭代、約束傳播和啟發(fā)式回溯的混合算法.通過某編組站實(shí)際數(shù)據(jù)驗(yàn)證得到：算法求解時(shí)間符合現(xiàn)場對計(jì)劃編制的實(shí)時(shí)性要求，與其他算法相比，本算法的效率和解的質(zhì)量更高.

［1］ 王慈光.用表上作業(yè)法求解編組站配流問題的研究［J］.鐵道學(xué)報(bào)，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］ 王慈光.編組站靜態(tài)配流網(wǎng)絡(luò)模型［J］.交通運(yùn)輸工程與信息學(xué)報(bào)，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］ 景云，王慈光，王如義，等.運(yùn)用學(xué)習(xí)規(guī)則求解編組站靜態(tài)配流問題的研究［J］.鐵道運(yùn)輸與經(jīng)濟(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］ 薛鋒，王慈光，羅建.雙向編組站靜態(tài)配流的優(yōu)化［J］.西南交通大學(xué)學(xué)報(bào)，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］ 趙軍，彭其淵.單向編組站配流與調(diào)機(jī)運(yùn)用綜合問題［J］.鐵道學(xué)報(bào)，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ì)劃自動(dòng)編制的數(shù)學(xué)模型及算法［J］.中國鐵道科學(xué)，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］ 紀(jì)昌明，段國圣，馮尚友.多目標(biāo)動(dòng)態(tài)規(guī)劃分層解法與Pareto最優(yōu)解［J］.系統(tǒng)工程理論與實(shí)踐，1995（6）：76-80.JI Changming，DUAN Guosheng，F(xiàn)ENG Shangyou.The hierarchical optimization criteria and pareto solution of multiobjectivedynamicprogramming［J］.Systems Engineering-Theory＆Practice，1995（6）：76-80.

［9］ 王明慧.字典序多目標(biāo)多階段決策問題的嘉量解法［J］.西南交通大學(xué)學(xué)報(bào)，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］ 劉露.基于約束傳播技術(shù)的資源受限項(xiàng)目調(diào)度問題求解算法［D］.沈陽：東北大學(xué)，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］ 劉士新，郭哲，唐加福.具有優(yōu)先關(guān)系的累積調(diào)度問題的約束傳播算法［J］.自動(dòng)化學(xué)報(bào)，2010，36（4）：603-609.LIUShixin，GUOZhe，TANGJiafu.Constraint propagation for cumulative scheduling problems with precedences［J］.ActaAutomaticaSinica，2010，36（4）：603-609.

［14］ 張居陽.基于約束的現(xiàn)代調(diào)度系統(tǒng)研究［D］.長春：吉林大學(xué)，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

鐵道部科技研究開發(fā)計(jì)劃重點(diǎn)課題（2010X010-F）；鐵道部科技研究開發(fā)計(jì)劃重大項(xiàng)目（2012X003-A）

馬亮（1987－），男，博士研究生，研究方向?yàn)榻煌ㄟ\(yùn)輸信息化理論與技術(shù)等，電話：028-87603029，E-mail：liangma9213＠163.com

馬亮，郭進(jìn)，陳光偉.編組站靜態(tài)配流的約束傳播和啟發(fā)式回溯算法［J］.西南交通大學(xué)學(xué)報(bào)，2014，49（6）：1116-1122.