基于邏輯程序的調機路徑規劃研究

,,2

(1.桂林電子科技大學 計算機與信息安全學院,廣西 桂林541004;2.廣西可信軟件重點實驗室,廣西 桂林 541004)

0 概述

隨著信息化建設的發展,鐵路技術站作業計劃的編制由傳統的手工作業進入到計算機輔助作業階段,并逐漸向智能化調度作業階段發展。技術站作業計劃包括了班計劃、階段計劃和調車作業計劃3個部分,其中與階段計劃編制相關的信息系統的研制和開發大多還停留在數據處理的層次,缺乏輔助決策功能,不能為階段計劃的編制提供決策支持[1]。因此,目前階段計劃的編制仍以人工為主,作業勞動強度大,容易出現計劃編制不及時、計劃質量低等問題。

調機運用計劃是技術站階段計劃的關鍵內容之一,主要是確定到達列車的解體次序、出發列車的編組次序、調機的作業時間以及承擔該作業的調機移動路線,將直接影響鐵路貨物運輸的周轉和整個路網的通過能力。如何實現調機運用計劃的自動編制是當前研究的重點,其中要解決的問題之一是如何令單個調機的移動路徑最短,即單個調機的運用問題。

目前,國內外處理調機運用計劃編制問題的方法主要包括:1)數學優化方法[2-3],如動態規劃、整數規劃和混合整數規劃法、拉格朗日松弛算法等。該類方法的優點是具有嚴格的數學模型,但在編制調機運用計劃時通常要處理一些半結構化和非結構化的信息,這些信息來自編制人員手工作業時累積的豐富經驗,而這些經驗則難以從數學模型的角度嚴格描述。2)啟發式算法[4],如局部鄰域搜索算法、迭代搜索算法等。該類算法往往需要仔細地設計一個合理的啟發函數,才能在較快的時間內成功避免局部最優,得到最優解。但目前此類算法的設計缺乏統一、完整的理論體系。3)智能優化類算法[5-6],如遺傳算法、模擬退火算法、禁忌搜索算法等。此類算法是從隨機的可行初始解出發,采用迭代改進的策略去逼近問題的最優解,從理論上講是一種全局尋優的計算方法,但通常計算量比較大,所需時間較長[7]。

邏輯程序設計是一種聲明式的程序設計方法,與傳統程序設計方法有較大差異,目前主流的方法有回答集程序設計(Answer Set Programming,ASP)[8]、有限域的約束邏輯程序設計(Constraint Logic Programming over Finite Domains,CLP(FD))[9]等。由于邏輯程序設計方法的模型表達能力強,人工經驗可以有效地轉變成規則表示的知識庫以及編碼緊湊、編碼方式容易理解等優點,目前越來越受到重視[10-12]。

為了更好地探討調機路徑規劃問題的解決途徑,本文將嘗試通過基于ASP與CLP(FD)的編碼方法來解決調機路徑規劃問題。使用說明性的描述方法將模型和解決過程完全分開,集中考慮模型的建立而不用考慮如何去獲得結果,使得編制作業實現自動化。在已有的規則基礎上,通過不斷增減系統中的規則模擬現實生活中多變的環境,以降低編制作業的勞動強度。

1 基礎知識

1.1 回答集程序

ASP是一種基于約束的非單調邏輯程序技術,它把程序解釋成在一個文字集上的約束,結果是0個或者多個模型,每個模型對應問題的一個解。與傳統的邏輯程序不同的是利用ASP求解問題時,解決問題的答案不是以替換的形式給出,而是由某些原子的集合,即回答集給出。

若A是一個原子,則A或～A稱為文字,其中,A為正文字,～A為負文字,A和～A稱為一對互補字。每條規則r滿足如下形式:

L1orL2or…orLK:-LK+1,…,Lm,notLm+1,…,notLn

(1)

其中,n≥m≥k≥0,每一個Li是一個文字,not表示失敗即否定(negation as failure)。將haed(r)={L1,L2,…,LK}稱為規則頭部,pos(r)={LK+1,LK+2,…,Lm}稱為規則體的正文字,而neg(r)={Lm+1,Lm+2,…,Ln}稱為規則體的負文字。一個沒有規則頭部的規則r,稱之為約束。如果pos(r)和neg(r)均為空,則稱規則r為事實。

設正規邏輯程序P,P相對于原子集合M的Gelfond-Lifschitz規約PM是確定性邏輯程序,PM由以下方法獲得:

1)對于P中的任意規則r,如neg(r)M≠,則刪除該規則;

2)將剩余所有規則r中的neg(r)刪除。

對于原子集合M以及正規邏輯程序P,如果M是程序PM的回答集,則M是程序P的回答集。

本文采用DLV[13]系統中的相關規定,用:-代替←進行書寫,每條規則以英文句號結束。

1.2 約束邏輯程序

約束邏輯程序(Constraint Logic Programming,CLP)設計是基于人工智能(AI)中約束滿足問題(Constraint Satisfaction Problem,CSP)模型的一種程序設計框架[14]。它繼承了邏輯程序設計簡單易懂的說明性描述方法,并結合了CSP在求解問題時的效率,使得它在解決很多AI問題時有較好的表現能力。

一個CLP程序[15]是由子句的序列構成的,子句r的形式為:

H←C1,C2,…,CmB1,B2,…,Bn,m≥0,n≥0

(2)

其中,B1,B2,…,Bn為原子公式,C1,C2,…,Cm為約束。特別地,當m=0時,子句形式:H:-B1,B2,…,Bn,而當n=0時,子句表示一種事實。一個原子公式形如:p(t1,t2,…,tn)的表達式(n個變元謂詞),其中ti(i=1,2,…,n)稱為項。項定義為一個變量,或者一個常量,或者一個作用于n個項的一個函數f(t1,t2,…,tn)。

約束邏輯程序語言(CLP(FD))的約束關系是基于聲明的整數運算,是用來實現純整數之間的關系表達式的計算。程序設計時加入了庫(clpfd),它能夠更好地聯系枚舉謂詞和更復雜的約束之間關系。

常用的求解器有SWI Prolog、Sicstus Prolog等,本文采用SWI系統中的相關規定,用:-代替←進行書寫,每條規則以英文句號結束。

2 問題描述

編組站是我國鐵路網絡中的重要節點,在這里到達列車會被分散成零散的車廂,出發列車又會由零散的車廂重新組合到一起,其作業組織會直接影響鐵路貨物運輸的效率。首先,到達列車將安排在到達場的合適軌道上展開到達作業,包括摘除干線機車和檢查列車的輪軸狀態等;接著,由解體調機將列車推送到一個稱為駝峰的人造小山峰執行解體作業,當各個去向的車廂將到達駝峰的頂峰時,摘去其與后續車廂相連接的車鉤,使其憑借自身重力溜放到軌道上;然后,車廂在調車場中與之前已停留的和后續到達的同去向車廂共同等待滿足出發條件完成集結作業;最后,多節車廂滿足出發條件被重新組合在一起完成編組作業成為一列新的出發列車,列車經過檢查完成出發作業駛出站點。如圖1所示,上述列車或車廂在車站進行了一系列的技術作業過程,又可稱為“到-解-集-編-發”過程。

圖1 編組站的典型布置示意圖

為更好地描述調機路徑規劃問題定義了一些相關概念,對調車場內所需要涉及的軌道進行分類,用來停放和存儲車廂的軌道稱為容納軌道,該類軌道可分為來源軌道和集結軌道,來源軌道停放了各個去向的車廂,集合軌道集結了去向相同的車廂。根據需要移動車廂的相對位置,來源軌道又可分為直接軌道和間接軌道。

本文討論了調機路徑規劃問題,通過調機將存放在不同來源軌道的車廂集中到集結軌道完成集結任務,目的是為調機尋找一條最短的移動路徑。

本文以圖2停留在調車場的小規模列車廂為例,顏色各異的方框代表去向各不相同的車廂,四邊圓弧的方框表示調機,假設斜線方框代表去往目的地A的車廂,黑色方框代表去往目的地B的車廂,白色方框代表去往目的地C的車廂。所有車廂都連續性的停放在來源軌道而不是分散在任意軌道上,而且車廂移動必須通過調機來實現。

圖2 單個調機問題示意圖

根據圖中車廂的初始位置可知,軌道2稱為間接軌道,軌道3成為直接軌道,軌道4是集結軌道,現在要將去往目的地B的車廂即黑色方框代表的車廂聚集到集結軌道直到滿足出發條件出站。而調機移動間接軌道的車廂時,要注意還要將去往另一個目的地A的車廂即斜線方框代表的車廂移回到原來的位置。換句話說,現在面臨的問題就變成了尋找調機將黑色車廂聚集到集結軌道并將灰色車廂返回到原來的位置的最佳路徑。

為了能更好地使用邏輯程序語言編碼問題,根據文獻[2]中轉換網絡圖的方法,可以將圖2中調車場的車廂初始位置圖轉換成網絡圖,那么該問題就變成了尋求符合約束條件的路徑問題。在圖3中,節點S表示調機的初始位置軌道,節點D表示直接軌道,節點B表示集結軌道,節點I1和I2都表示間接軌道且是同一條軌道,也就是說節點I2是節點I1的虛擬節點,目的是為了避免雙向路徑的存在,節點E表示結束軌道,箭頭直線表示調機可以在這兩軌道之間移動。

圖3 網絡圖轉換示意圖

3 解決方案

3.1 ASP問題描述

借鑒文獻[11]中用ASP對火車路徑的編碼方法,目的是為了得到符合規則的最短路徑的回答集。定義的網絡圖是由一系列的節點和邊組成的,節點代表軌道,邊代表調機在兩軌道間能進行移動。為了能更直觀地描述網絡圖,本文定義下列謂詞,如表1所示。

表1 ASP程序謂詞及含義

上述所定義謂詞以ASP規則形式給出相互之間的推導關系:

規則1node(X):-arc(X,Y)

規則2node(Y):-arc(X,Y)

由規則1可知節點是來源于邊的,當存在一條邊開始于X時,可推斷出X是一個節點。規則R2類似。

規則3in(X,Y)v～in(X,Y):-arc(X,Y),reached (X)

由規則3可知如果存在一條邊,調機會通過它的節點,那么這條邊可能會成為回答集的一部分。因為存在從相同的節點出發的多條邊的情況,而只有其中一條會成為最短路徑的一部分。

規則4:-in(X,Y),in(X1,Y),X!=X1

規則5:-in(X,Y),in(X,Y1),Y!=Y1

由規則4可知在回答集中不可能有從同一個節點出發而在不同節點結束的兩條邊同時存在的情況。規則5類似規則4,但是將結束節點代替了開始節點。

規則6reached(Y):-in(X,Y)

由規則6可知當一條邊成為最短路徑的一部分時,調機一定會通過連接這條邊的2個節點。

規則7reached(X):-start(X)

規則7可知最終得到的最短路徑是必須通過指定的開始節點和結束節點。規則8就是適用于處理這2個特殊的節點,這是必要的規則。

規則8:-node(X),not reached(X)

為確保整個程序的運行過程能持續進行直到找出符合條件的回答集,其實也就是為了確保網絡圖中每個節點都被調機遍歷一遍。規則8可以理解為求解出的回答集中不可能存在一個沒有被調機所經過的節點X。

規則9～規則14是將調機所有可以移動的路徑都表示出來:

規則9arc(X,Y):-start(X),a1(Y)

規則10arc(X,Y):-start(X),f2(Y)

規則11arc(X,Y):-a1(X),f2(Y)

規則12arc(X,Y):-f2(X),f3(Y)

規則13arc(X,Y):-a1(X),f3(Y)

規則14arc(X,Y):-a2(X),end(Y)

為得到切實的回答集答案,將節點用“a”“b”“c”“d”“e”代替,給以事實F1～F6:start(a)、f3(b)、f2(c)、a1(d)、a2(e)、end(f)。

3.2 CLP(FD)描述問題

這個方法描述了已設定的節點和邊之間可能存在的最短路徑。為更好地描述事實,引入了列表的概念,列表的元素由方括號括起。為了能更直觀地描述網絡圖,定義下列謂詞,如表2所示。

表2 CLP(FD)程序謂詞及含義

上述所定義謂詞以CLP(FD)規則形式給出相互之間的推導關系如下:

規則15solution(List):-succlist(List),start(List),end(List),pass1(List),pass2(List),pass3(List),pass4(Li st),order(List),domain(List,1,K),labeling([ff],List)

由規則15可知符合所有約束條件的列表。

規則16succ(Pre,Succ):-graph(Nodes,Edges),me mber(Pre,Nodes),member(Succ,Nodes),member([Pre,Succ],Edges

由規則16可知邊由前繼節點和后繼節點構成。

規則17succlist([X,Y]):-succ(X,Y)

規則18succlist([X,Y|R]):-succ(X,Y),succlist ([Y|R])

由規則17、規則18可知從開始節點到結束節點的邊必須形成通路,而且要遍歷所有節點。

由規則19可知節點I1優先級比節點I2。相比而言,其他方法很難將這個約束條件簡潔地表示出來。

規則20～規則30是將調機所有可以移動的路徑表示出來:

規則20end([′E′|[]])

規則21end([_|T]):-end(T)

規則22start([′S′|_])

規則24pass1([_|T]):-pass1(T)

規則26pass2([_|T]):-pass2(T)

規則27pass3([′B′|_])

規則28pass3([_|T]):-pass3(T)

規則29pass4([′D′|_])

規則30pass4([_|T]):-pass4(T)

為更好地尋求答案,給予相對應的事實graph([‘S’,‘I1’,‘B’,‘D’,‘I2’,‘E’],[[‘S’,‘I1’],[‘S’,‘D’],[‘I1’,‘D’],[‘I1’,‘B’],[‘D’,‘B’],[‘B’,‘I2’],[‘I2’,‘E’]])。第1列列表代表節點,第2列列表表示節點之間存在的邊。

4 實驗結果與分析

4.1 運行結果

將ASP方法中的全部規則與事實輸入到DLV求解器中得到的回答集如圖4所示。

圖4 ASP方法中得到的回答集

該回答集羅列了從開始節點到結束節點存在的最短路徑。調機從節點S出發到達節點I1,然后移動車廂到達節點D,接著將要組成出發列車的車廂移動到節點B,最后將多余的車廂移回到原始軌道即節點I2,調機到達節點E標志著整個移動過程結束。

同樣地,將CLP(FD)方法所編寫的規則和事實輸入到SWI求解器得到一個列表如圖5所示。

圖5 CLP(FD)方法列表

根據該列表可得調機的移動路徑,首先調機從節點S移動到間接軌道節點I1進行作業,然后再移動到直接軌道節點D接著移動到了集結軌道節點B,并將多余的車廂移動返回到原始的間接軌道節點I2,最后調機到達節點E完成所有的移動工作。

根據以上結果可知2種方法所得到的移動路徑是一致的。結合圖3可知調機不可能一次將所有去向相同的車廂移動到集結軌道,只能一次一次分步驟地將它們移動到集結軌道。分析上述運行結果可知調機的移動路徑:

1)調機從初始位置移動到間接軌道;

2)將所有停放在間接軌道的車廂移動到直接軌道;

3)將所有黑色車廂包括在它之前已經停放在調車場的其他去向的車廂一起移動到集結軌道;

4)將其他去向的車廂移回到原始位置結束移動。

文獻[2]也采用混合整數線性規劃模型對該實例進行了討論,并且采用了SimShunt仿真軟件進行了驗證,而本文所得的答案與其仿真結果也是一致的,說明邏輯程序能得到最優結果,并且證明了邏輯程序對解決該類問題是有效的。

4.2 比較實驗

本節內容旨在尋求不同軌道數量大小下2種方法的求解效率,為今后實現調機運用計劃的自動編制工作的方法選取奠定基礎。以中國最大編組站之一的豐臺西站為例,可知上行系統的調車場有30個股道,以此作為調車場軌道數的最大值進行實驗。根據新添加規則的規律編寫了如圖6所示的程序隨機產生器。

圖6 程序隨機產生器

圖6中隨機輸入代表間接軌道的節點數,會產生相對應的程序規則。由于不同解決器效率并不相同,將選擇多種求解器來運行程序。ASP程序要在求解器DLV和Smodels中運行,CLP(FD)也要在2種不同的求解器SWI和SICStus中運行。同一程序在不同求解器運行的語法會有差別,對于在Smodels和SICStus中運行的程序語法要根據各自的使用手冊稍做修改。

程序在不同求解器的運行結果所表示的移動路徑是一致的,但是運行時間各不相同,如表3所示。

表3 不同運行程序運行時間 s

由圖7可知:當間接軌道數增加時,不管是ASP程序還是CLP(FD)程序運行時間都有所增加,這是符合實際情況的。在間接軌數較小時,CLP(FD)程序在2種求解器的運行時間均比ASP程序的運行時間短,但隨著軌道數不斷增加,CLP(FD)程序運行時間反而驟然增加,遠超過ASP程序的運行時間。反觀ASP程序運行時間增長緩慢,增長率相比CLP(FD)程序低很多。對于運行ASP程序的兩種解決器,DLV運行時間增加量極少,一直趨于穩定,增長率比Smodels低。由這些趨勢可判斷,當問題中軌道規模增大時,ASP程序在解決單個調機路徑規劃問題上比CLP(FD)有更好的表現,并且DLV求解器相比其他求解器更能有效地克服軌道數量增大帶來的影響。

圖7 求解器運行時間效率

5 結束語

針對各臺編組調機移動路徑的編排工作,本文分別給出基于ASP和CLP(FD)的邏輯程序設計方法,并結合實例分析了該方法能有效解決調機路徑規劃問題,實驗結果表明,在此類問題的解決上ASP的運行時間比CLP(FD)短,ASP能更加快速地得到路徑編排結果,在軌道數不斷增多的情況下,DLV求解器相比其他求解器運行時間增長緩慢,趨于穩定,即DLV求解器比其他的求解器能更有效地克服軌道數目增減帶來的影響。下一步將利用本文方法研究編組站單雙向系統的多調機運行計劃的編制問題。

[1] 黎浩東,何世偉,王保華,等.鐵路編組站階段計劃編制研究綜述[J].鐵道學報,2011,33(8):13-22.

[2] ADLBRECHT J A,HUTTLER B,ZAZGORNIK J,et al.The Train Marshaling by a Single Shunting Engine Problem[J].Transportation Research Part C,2015,58:56-72.

[3] 趙 軍,韓雪松,彭其淵.技術站配流與調機運用綜合問題的拉格朗日松弛算法[J].鐵道學報,2011,33(11):1-7.

[4] AHUJA S G,RAVINDRA K.Single-machine Scheduling with Stepwise Tardiness Costs and Release Times[J].Journal of Industrial and Management Optimization,2011,7(4):825-848.

[5] 徐 杰,杜 文,李宗平,等.基于模擬退火算法和圖著色的調車機安排研究[J].鐵道學報,2003,25(3):24-30.

[6] 王 爍,何世偉,黎浩東,等.禁忌搜索算法在編組站調機運用計劃中的應用[J].鐵道運輸與經濟,2011,7(1):76-79.

[7] 張瑞鋒.基于混合算法的帶時間窗的車輛路徑問題求解[J].計算機工程,2007,33(14):185-187.

[8] BREWKA G,EITER T,TRUSZCZYNSKI M.Answer Set Programming at a Glance[J].Communications of the ACM,2011,54(12):92-103.

[9] FRIIHWIRTH T,HEROLD A,KIICHENHOFF V,et al.Constraint Logic Programming——An Informal Introduction[C]//Proceedings of the 2nd International Logic Programming Summer School.Zurich,Switzerland:[s.n.].1992:1-35.

[10] BOENN G,BRAIN M,de V M et al.Automatic Music Composition Using Answer Set Programming[J].Theory and Practice of Logic Programming,2011,11(2/3):397-427.

[11] ADLBRECHT J A,HUTTTLER B,ILO N,et al.Train Routing in Shunting Yards Using Answer Set Programming[J].Expert Systems with Applications,2015,42(1):7292-7302.

[12] 徐成剛,易軍凱,肖 洋.基于約束邏輯程序設計的排課算法研究[J].計算機工程與應用,2006,42(31):197-199.

[13] LEONE N,PFEIFER G,FABER W,et al.The DLV System for Knowledge Representation and Reasoning[J].ACM Transactions on Computational Logic,2006,7(3):499-562.

[14] 黨華銳,鄭守淇.約束邏輯程序設計綜述[J].計算機科學,1994,21(4):11-14.

[15] 常萬軍,郭祖華,魏昆鵬.約束邏輯程序的良基模型研究[J].計算機工程,2013,39(9):298- 302.