,,2

(1.桂林電子科技大學(xué) 計(jì)算機(jī)與信息安全學(xué)院,廣西 桂林541004;2.廣西可信軟件重點(diǎn)實(shí)驗(yàn)室,廣西 桂林 541004)

0 概述

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

調(diào)機(jī)運(yùn)用計(jì)劃是技術(shù)站階段計(jì)劃的關(guān)鍵內(nèi)容之一,主要是確定到達(dá)列車的解體次序、出發(fā)列車的編組次序、調(diào)機(jī)的作業(yè)時(shí)間以及承擔(dān)該作業(yè)的調(diào)機(jī)移動路線,將直接影響鐵路貨物運(yùn)輸?shù)闹苻D(zhuǎn)和整個(gè)路網(wǎng)的通過能力。如何實(shí)現(xiàn)調(diào)機(jī)運(yùn)用計(jì)劃的自動編制是當(dāng)前研究的重點(diǎn),其中要解決的問題之一是如何令單個(gè)調(diào)機(jī)的移動路徑最短,即單個(gè)調(diào)機(jī)的運(yùn)用問題。

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

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

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

1 基礎(chǔ)知識

1.1 回答集程序

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

若A是一個(gè)原子,則A或～A稱為文字,其中,A為正文字,～A為負(fù)文字,A和～A稱為一對互補(bǔ)字。每條規(guī)則r滿足如下形式:

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

(1)

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

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

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

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

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

本文采用DLV[13]系統(tǒng)中的相關(guān)規(guī)定,用:-代替←進(jìn)行書寫,每條規(guī)則以英文句號結(jié)束。

1.2 約束邏輯程序

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

一個(gè)CLP程序[15]是由子句的序列構(gòu)成的,子句r的形式為:

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

(2)

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

約束邏輯程序語言(CLP(FD))的約束關(guān)系是基于聲明的整數(shù)運(yùn)算,是用來實(shí)現(xiàn)純整數(shù)之間的關(guān)系表達(dá)式的計(jì)算。程序設(shè)計(jì)時(shí)加入了庫(clpfd),它能夠更好地聯(lián)系枚舉謂詞和更復(fù)雜的約束之間關(guān)系。

常用的求解器有SWI Prolog、Sicstus Prolog等,本文采用SWI系統(tǒng)中的相關(guān)規(guī)定,用:-代替←進(jìn)行書寫,每條規(guī)則以英文句號結(jié)束。

2 問題描述

編組站是我國鐵路網(wǎng)絡(luò)中的重要節(jié)點(diǎn),在這里到達(dá)列車會被分散成零散的車廂,出發(fā)列車又會由零散的車廂重新組合到一起,其作業(yè)組織會直接影響鐵路貨物運(yùn)輸?shù)男省Ｊ紫?到達(dá)列車將安排在到達(dá)場的合適軌道上展開到達(dá)作業(yè),包括摘除干線機(jī)車和檢查列車的輪軸狀態(tài)等;接著,由解體調(diào)機(jī)將列車推送到一個(gè)稱為駝峰的人造小山峰執(zhí)行解體作業(yè),當(dāng)各個(gè)去向的車廂將到達(dá)駝峰的頂峰時(shí),摘去其與后續(xù)車廂相連接的車鉤,使其憑借自身重力溜放到軌道上;然后,車廂在調(diào)車場中與之前已停留的和后續(xù)到達(dá)的同去向車廂共同等待滿足出發(fā)條件完成集結(jié)作業(yè);最后,多節(jié)車廂滿足出發(fā)條件被重新組合在一起完成編組作業(yè)成為一列新的出發(fā)列車,列車經(jīng)過檢查完成出發(fā)作業(yè)駛出站點(diǎn)。如圖1所示,上述列車或車廂在車站進(jìn)行了一系列的技術(shù)作業(yè)過程,又可稱為“到-解-集-編-發(fā)”過程。

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

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

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

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

圖2 單個(gè)調(diào)機(jī)問題示意圖

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

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

圖3 網(wǎng)絡(luò)圖轉(zhuǎn)換示意圖

3 解決方案

3.1 ASP問題描述

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

表1 ASP程序謂詞及含義

上述所定義謂詞以ASP規(guī)則形式給出相互之間的推導(dǎo)關(guān)系:

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

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

由規(guī)則1可知節(jié)點(diǎn)是來源于邊的,當(dāng)存在一條邊開始于X時(shí),可推斷出X是一個(gè)節(jié)點(diǎn)。規(guī)則R2類似。

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

由規(guī)則3可知如果存在一條邊,調(diào)機(jī)會通過它的節(jié)點(diǎn),那么這條邊可能會成為回答集的一部分。因?yàn)榇嬖趶南嗤墓?jié)點(diǎn)出發(fā)的多條邊的情況,而只有其中一條會成為最短路徑的一部分。

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

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

由規(guī)則4可知在回答集中不可能有從同一個(gè)節(jié)點(diǎn)出發(fā)而在不同節(jié)點(diǎn)結(jié)束的兩條邊同時(shí)存在的情況。規(guī)則5類似規(guī)則4,但是將結(jié)束節(jié)點(diǎn)代替了開始節(jié)點(diǎn)。

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

由規(guī)則6可知當(dāng)一條邊成為最短路徑的一部分時(shí),調(diào)機(jī)一定會通過連接這條邊的2個(gè)節(jié)點(diǎn)。

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

規(guī)則7可知最終得到的最短路徑是必須通過指定的開始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)。規(guī)則8就是適用于處理這2個(gè)特殊的節(jié)點(diǎn),這是必要的規(guī)則。

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

為確保整個(gè)程序的運(yùn)行過程能持續(xù)進(jìn)行直到找出符合條件的回答集,其實(shí)也就是為了確保網(wǎng)絡(luò)圖中每個(gè)節(jié)點(diǎn)都被調(diào)機(jī)遍歷一遍。規(guī)則8可以理解為求解出的回答集中不可能存在一個(gè)沒有被調(diào)機(jī)所經(jīng)過的節(jié)點(diǎn)X。

規(guī)則9～規(guī)則14是將調(diào)機(jī)所有可以移動的路徑都表示出來:

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

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

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

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

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

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

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

3.2 CLP(FD)描述問題

這個(gè)方法描述了已設(shè)定的節(jié)點(diǎn)和邊之間可能存在的最短路徑。為更好地描述事實(shí),引入了列表的概念,列表的元素由方括號括起。為了能更直觀地描述網(wǎng)絡(luò)圖,定義下列謂詞,如表2所示。

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

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

規(guī)則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)

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

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

由規(guī)則16可知邊由前繼節(jié)點(diǎn)和后繼節(jié)點(diǎn)構(gòu)成。

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

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

由規(guī)則17、規(guī)則18可知從開始節(jié)點(diǎn)到結(jié)束節(jié)點(diǎn)的邊必須形成通路,而且要遍歷所有節(jié)點(diǎn)。

由規(guī)則19可知節(jié)點(diǎn)I1優(yōu)先級比節(jié)點(diǎn)I2。相比而言,其他方法很難將這個(gè)約束條件簡潔地表示出來。

規(guī)則20～規(guī)則30是將調(diào)機(jī)所有可以移動的路徑表示出來:

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 運(yùn)行結(jié)果

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

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

該回答集羅列了從開始節(jié)點(diǎn)到結(jié)束節(jié)點(diǎn)存在的最短路徑。調(diào)機(jī)從節(jié)點(diǎn)S出發(fā)到達(dá)節(jié)點(diǎn)I1,然后移動車廂到達(dá)節(jié)點(diǎn)D,接著將要組成出發(fā)列車的車廂移動到節(jié)點(diǎn)B,最后將多余的車廂移回到原始軌道即節(jié)點(diǎn)I2,調(diào)機(jī)到達(dá)節(jié)點(diǎn)E標(biāo)志著整個(gè)移動過程結(jié)束。

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

圖5 CLP(FD)方法列表

根據(jù)該列表可得調(diào)機(jī)的移動路徑,首先調(diào)機(jī)從節(jié)點(diǎn)S移動到間接軌道節(jié)點(diǎn)I1進(jìn)行作業(yè),然后再移動到直接軌道節(jié)點(diǎn)D接著移動到了集結(jié)軌道節(jié)點(diǎn)B,并將多余的車廂移動返回到原始的間接軌道節(jié)點(diǎn)I2,最后調(diào)機(jī)到達(dá)節(jié)點(diǎn)E完成所有的移動工作。

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

1)調(diào)機(jī)從初始位置移動到間接軌道;

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

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

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

文獻(xiàn)[2]也采用混合整數(shù)線性規(guī)劃模型對該實(shí)例進(jìn)行了討論,并且采用了SimShunt仿真軟件進(jìn)行了驗(yàn)證,而本文所得的答案與其仿真結(jié)果也是一致的,說明邏輯程序能得到最優(yōu)結(jié)果,并且證明了邏輯程序?qū)鉀Q該類問題是有效的。

4.2 比較實(shí)驗(yàn)

本節(jié)內(nèi)容旨在尋求不同軌道數(shù)量大小下2種方法的求解效率,為今后實(shí)現(xiàn)調(diào)機(jī)運(yùn)用計(jì)劃的自動編制工作的方法選取奠定基礎(chǔ)。以中國最大編組站之一的豐臺西站為例,可知上行系統(tǒng)的調(diào)車場有30個(gè)股道,以此作為調(diào)車場軌道數(shù)的最大值進(jìn)行實(shí)驗(yàn)。根據(jù)新添加規(guī)則的規(guī)律編寫了如圖6所示的程序隨機(jī)產(chǎn)生器。

圖6 程序隨機(jī)產(chǎn)生器

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

程序在不同求解器的運(yùn)行結(jié)果所表示的移動路徑是一致的,但是運(yùn)行時(shí)間各不相同,如表3所示。

表3 不同運(yùn)行程序運(yùn)行時(shí)間 s

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

圖7 求解器運(yùn)行時(shí)間效率

5 結(jié)束語

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

[1] 黎浩東,何世偉,王保華,等.鐵路編組站階段計(jì)劃編制研究綜述[J].鐵道學(xué)報(bào),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] 趙 軍,韓雪松,彭其淵.技術(shù)站配流與調(diào)機(jī)運(yùn)用綜合問題的拉格朗日松弛算法[J].鐵道學(xué)報(bào),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] 徐 杰,杜 文,李宗平,等.基于模擬退火算法和圖著色的調(diào)車機(jī)安排研究[J].鐵道學(xué)報(bào),2003,25(3):24-30.

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

[7] 張瑞鋒.基于混合算法的帶時(shí)間窗的車輛路徑問題求解[J].計(jì)算機(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] 徐成剛,易軍凱,肖 洋.基于約束邏輯程序設(shè)計(jì)的排課算法研究[J].計(jì)算機(jī)工程與應(yīng)用,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] 黨華銳,鄭守淇.約束邏輯程序設(shè)計(jì)綜述[J].計(jì)算機(jī)科學(xué),1994,21(4):11-14.

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