何 迅,郭 鵬,欒玉麟
(西南交通大學(xué) 機(jī)械工程學(xué)院,成都 610031)
(軌道交通運(yùn)維技術(shù)與裝備四川省重點實驗室,成都 610031)
鐵路運(yùn)輸作為最為低碳的貨運(yùn)方式,在內(nèi)陸腹地運(yùn)輸方面極具優(yōu)勢.我國鐵路貨運(yùn)總量占比在面臨殘酷的市場競爭時連年下滑,已由2009年的11.96%降至2017年的7.81%[1].目前我國鐵路集裝箱運(yùn)量僅占鐵路貨運(yùn)量的5.4%,遠(yuǎn)遠(yuǎn)低于發(fā)達(dá)國家(美國占比49%,法國占比40%,英國占比30%,德國占比20%,日本占比100%)[2].如此大的差距表明我國鐵路集裝箱運(yùn)輸存在巨大的潛力和發(fā)展空間.當(dāng)前,我國沿海港口積極發(fā)展內(nèi)陸“無水港”,加快港口鐵路集疏運(yùn),積極推動船、車、班列、港口、場站、貨物等信息開放共享.國家“十一五規(guī)劃”規(guī)劃建設(shè)了18 個鐵路集裝箱中心站,有利于實現(xiàn)區(qū)域集裝箱鐵路運(yùn)輸與其他運(yùn)輸方式的無縫銜接.在“一帶一路”國家戰(zhàn)略的帶動下,鐵路集裝箱多式聯(lián)運(yùn)更是迎來了彌足珍貴的發(fā)展契機(jī),研究提升鐵路集裝箱多式聯(lián)運(yùn)效率具有重要的現(xiàn)實與戰(zhàn)略意義.
作為多式聯(lián)運(yùn)鐵路站場主要活動,轉(zhuǎn)運(yùn)作業(yè)效率直接影響鐵路集裝箱多式聯(lián)運(yùn)的整體運(yùn)作水平.為了保證自動化堆場作業(yè)計劃生成的準(zhǔn)確性,現(xiàn)有鐵路集裝箱站場轉(zhuǎn)運(yùn)作業(yè)均要求集裝箱班列或卡車經(jīng)堆場方可實現(xiàn).經(jīng)集裝箱站場實現(xiàn)不同運(yùn)載工具之間的轉(zhuǎn)運(yùn)必然存在兩次裝卸和一次暫存作業(yè).對于提高轉(zhuǎn)運(yùn)作業(yè)效率來說,暫存和額外的裝卸作業(yè)完全是無效操作,且會使有限的堆場空間資源更為緊張.減少暫存中轉(zhuǎn)作業(yè)的關(guān)鍵是提高同步轉(zhuǎn)運(yùn)(也叫連續(xù)轉(zhuǎn)運(yùn)或直裝直卸)集裝箱比率.同步轉(zhuǎn)運(yùn)旨在通過合理安排集裝箱班列進(jìn)入堆場的作業(yè)時間窗,實現(xiàn)在站的兩類運(yùn)輸設(shè)備之間的集裝箱流同步交互,盡可能地縮短集裝箱站內(nèi)中轉(zhuǎn)時間.
國內(nèi)外學(xué)者對鐵路集裝箱站場的作業(yè)效率提升進(jìn)行了不少研究.Boysen等[3]對鐵路站場的設(shè)施布局與作業(yè)調(diào)度優(yōu)化研究現(xiàn)狀進(jìn)行了歸類總結(jié).Otto和Pesch[4]分析了多式聯(lián)運(yùn)下鐵路堆場中班列與堆場指派問題,以最小化再指派次數(shù)為目標(biāo)更新了下界計算方法.Boysen等[5]構(gòu)建了鐵路-鐵路(Rail-Rail)站場的數(shù)學(xué)規(guī)劃模型來確定主裝卸線上各臺起重機(jī)的最優(yōu)作業(yè)區(qū)域.Kellner等[6]考慮集裝箱班列??课恢脤D(zhuǎn)運(yùn)作業(yè)的影響,并構(gòu)建數(shù)學(xué)模型來確定其最佳位置以便減少集裝箱移動距離.Boysen等[7,8]提出采用集裝箱整理系統(tǒng)支持站內(nèi)轉(zhuǎn)運(yùn),并對比分析了四種不同的集裝箱整理系統(tǒng)在鐵路-鐵路聯(lián)運(yùn)站場中的作業(yè)效率.起重機(jī)作為集裝箱站場的主要轉(zhuǎn)運(yùn)設(shè)備,Guo等[9,10]對公鐵聯(lián)運(yùn)的集裝箱中心站軌道式起重機(jī)調(diào)度問題進(jìn)行了建模優(yōu)化,并希望將外部卡車服務(wù)水平納入調(diào)度優(yōu)化模型.王力等[11,12]認(rèn)為集裝箱班列卸箱作業(yè)和裝箱作業(yè)過程相同,以卸箱作業(yè)過程建立了中心站起重機(jī)調(diào)度優(yōu)化模型,設(shè)計了混合粒子群算法進(jìn)行求解;還考慮堆場混堆優(yōu)化問題,以兩階段優(yōu)化模型來平衡堆場各箱區(qū)進(jìn)站箱和出站箱的數(shù)量及減少堆存所產(chǎn)生的壓箱數(shù).而上述研究聚焦在鐵路站場的箱位指派、集裝箱班列位置指派、裝卸設(shè)備調(diào)度問題上,尚未考慮同步轉(zhuǎn)運(yùn)作業(yè).
在不同的運(yùn)輸方式之間利用轉(zhuǎn)運(yùn)工具實現(xiàn)乘客或貨物中轉(zhuǎn),盡可能保證進(jìn)出運(yùn)載工具的同步,能夠大幅提升轉(zhuǎn)運(yùn)效率[13].Boysen等[14]為鐵路-鐵路(Rail-Rail)集裝箱站場調(diào)度問題構(gòu)建了數(shù)學(xué)模型,通過確定集裝箱班列集合中每趟車的服務(wù)間隙來最小化班列重回站場的次數(shù)和集裝箱分割裝卸的移動次數(shù),證明了該問題是NP-hard的,并提出了基于動態(tài)規(guī)劃和束搜索的求解算法.該研究對集裝箱班列的轉(zhuǎn)運(yùn)調(diào)度進(jìn)行優(yōu)化,以求實現(xiàn)同步轉(zhuǎn)運(yùn),本文在此基礎(chǔ)上提出集裝箱班列同步轉(zhuǎn)運(yùn)調(diào)度模型,通過分析問題的特征設(shè)計基于突破性局部搜索的求解算法.利用算例驗證本文算法可以在提高求解質(zhì)量的同時,顯著縮短求解時間,對站場效率提升具有重要的參考價值.
在集裝箱班列同步轉(zhuǎn)運(yùn)作業(yè)調(diào)度問題(Freight Trains Scheduling Problem with Synchronized Transferring,FTSPST)中,n趟班列需要進(jìn)入堆場實施裝卸轉(zhuǎn)運(yùn)操作.堆場鋪設(shè)有m組并行鐵軌,每次最多可牽引m趟班列進(jìn)入.假設(shè)有T個時間段實施牽引進(jìn)站作業(yè),則有T=n/m.為了方便描述,在此假設(shè)n=T×m.在實際作業(yè)過程中,若班列數(shù)不足n,可通過引入未裝載集裝箱的虛擬班列來滿足.針對班列i(i=1,…,n),最早進(jìn)入堆場時間段為ei,最晚離開堆場時間段為li.假設(shè)班列i和j之間存在Aij個集裝箱須進(jìn)行轉(zhuǎn)運(yùn),若兩趟班列能夠在同一時間段t牽引進(jìn)堆場,則可成功實現(xiàn)Aij個集裝箱同步轉(zhuǎn)運(yùn).需要轉(zhuǎn)運(yùn)到班列i的集裝箱位于其他班列之上,用Li表示能與班列i進(jìn)行同步轉(zhuǎn)運(yùn)作業(yè)的其他班列集合.在此定義決策變量xit與zij,若集裝箱班列i進(jìn)入堆場的時間段為t則xit=1,否則為0;若集裝箱班列i和j在同一時間段進(jìn)入堆場則zij=1,否則為0.以同步轉(zhuǎn)運(yùn)的集裝箱箱數(shù)最大化為優(yōu)化目標(biāo),構(gòu)建如下混合整數(shù)規(guī)劃模型:
s.t.
上述優(yōu)化模型中,目標(biāo)函數(shù)(1)保證同步轉(zhuǎn)運(yùn)的集裝箱箱數(shù)最大化;約束(2)確保一輛班列只能被安排在一個時間段;約束(3)確保同一時間段內(nèi)進(jìn)入堆場的班列數(shù)不超過鋪設(shè)的軌道數(shù);約束(4)表示同一時間段進(jìn)入堆場的班列i和j對應(yīng)的變量zij必須為1;約束(5)定義決策變量的取值范圍.
突破性局部搜索算法(Breakout Local Search,BLS)是一種自適應(yīng)的鄰域搜索算法,在一般鄰域搜索算法的基礎(chǔ)上增加了自適應(yīng)擾動機(jī)制,能快速逃離局部最優(yōu)以及提高穩(wěn)定性[15].該算法分為局部搜索階段和擾動階段.通過某種方法產(chǎn)生初始可行解π0,利用鄰域搜索算子產(chǎn)生所有的可行解,從中找出局部最優(yōu)解π.然后通過適當(dāng)?shù)臄_動對當(dāng)前解π進(jìn)行操作以幫助算法逃離當(dāng)前的局部最優(yōu)解,擾動獲得的解將成為下一輪鄰域搜索的起點.上述搜索一直迭代直到達(dá)到算法終止條件為止.BLS算法在搜索過程中融入了局部迭代搜索、禁忌搜索與模擬退火算法的操作機(jī)制,具有搜索質(zhì)量高、計算時間短等優(yōu)點,現(xiàn)已用于求解最大團(tuán)問題[16]、最大割問題[17]、二次指派問題[15]、裝配序列規(guī)劃問題[18]以及門分派問題[19]等,并獲得較好的求解效果.BLS算法流程圖如圖1所示.
圖1 BLS算法流程圖
BLS算法對局部最優(yōu)解的擾動取決于擾動幅度和擾動類型,擾動的強(qiáng)弱依賴于當(dāng)前搜索操作的狀態(tài),主要是通過當(dāng)前解π和當(dāng)前最佳解連續(xù)未改善的次數(shù)ω來確定擾動幅度K和擾動類型[16].BLS首先搜索鄰近的局部最優(yōu)解,只有當(dāng)搜索停滯不前,才能移動到下一個鄰域.在每次局部搜索后,BLS執(zhí)行小幅度的定向或近似隨機(jī)移動,以保證能夠逃離當(dāng)前局部最優(yōu)解.如果擾動幅度不足以逃離局部最優(yōu)解,則增加擾動幅度K;否則將其設(shè)置為默認(rèn)值,即K=K0.如果當(dāng)前最佳解連續(xù)未改善的次數(shù)超過了給定的閥值Ω,則將擾動幅度設(shè)置為最大值Kmax,以保證搜索過程能夠脫離當(dāng)前鄰域解空間.
所提出的BLS算法采用置換序列的編碼形式,譬如5趟班列與2組鐵軌的算例,則當(dāng)前解序列π={1,5,2,3,4},其中π2=5表示編號為5的班列安排在序列位置2處,若班列1與班列5均可在時間段t=1進(jìn)入堆場,則其進(jìn)入堆場的時間段為1.鄰域操作與擾動采用交換操作,則π’=π⊕swap(u,v)表示交換位置u和v上的班列序號得到新的候選解.
BLS算法采用以下三種擾動類型:定向,近似隨機(jī)和隨機(jī)擾動.定向擾動基于禁忌搜索原則來實施,當(dāng)搜索到的候選解優(yōu)于目前為止找到的最佳解時,該操作對應(yīng)的禁忌狀態(tài)消除.同時產(chǎn)生候選解的操作在禁忌周期γ之外時,也可消除禁忌狀態(tài).定向擾動依賴于上一次迭代搜索的歷史信息以及不會禁止良好的擾動操作.針對定向擾動的判斷由集合 R表征:
其中,H是上次執(zhí)行擾動時跟蹤迭代次數(shù)的矩陣,Iter是當(dāng)前迭代次數(shù),f是當(dāng)前解對應(yīng)的目標(biāo)函數(shù)值,fbest是當(dāng)前已找到的最佳解對應(yīng)的目標(biāo)函數(shù)值,u、v為需要進(jìn)行置換擾動的變量.γ值越大代表著擾動越強(qiáng)烈,在 BLS 算法中γ=n×r1+rand(0,1)×n×r2,其中r1與r2為待確定的常數(shù)值.近似隨機(jī)擾動僅依賴于由H矩陣提供的歷史信息,由集合 Z表征為:
隨機(jī)擾動簡單地執(zhí)行隨機(jī)均勻的擾動,由集合C表征:
為了實現(xiàn)強(qiáng)化搜索和多樣性搜索的平衡,BLS算法引入概率選擇操作確定擾動類型.根據(jù)當(dāng)前搜索狀態(tài)和當(dāng)前最佳解連續(xù)未改善的次數(shù)ω動態(tài)確定應(yīng)用特定擾動的概率.在迭代搜索過程中,若找到新的最佳解或ω超過給定閾值Ω時,ω被重置為零.鄰域搜索初期算法更偏向于采用定向擾動.隨著ω的增加,使用定向擾動的幾率逐漸降低,同時隨機(jī)和近似隨機(jī)擾動的概率會增加,從而達(dá)到自適應(yīng)的多樣性擾動.
另外,從計算分析中已經(jīng)觀察到,保證定向擾動的最小概率是有用的.因此,采用定向擾動的概率p取不小于閾值p0的值:
基于計算出的定向擾動概率p,則可分別通過(1-p)*Q和(1-p)*(1-Q)確定近似隨機(jī)和隨機(jī)擾動的概率,其中Q為區(qū)間[0,1]之間的常數(shù).確定了各自的概率后,則可通過區(qū)間位于(0,1)之間隨機(jī)數(shù)來確定擾動類型.
鐵路集裝箱班列同步轉(zhuǎn)運(yùn)過程中,存在每輛班列最早與最晚離開堆場的時間段和現(xiàn)有鐵軌數(shù)的約束.為此需對BLS算法進(jìn)行必要的改進(jìn)以適應(yīng)所考慮的問題.為了加快算法搜索速度,在此設(shè)計算法1中的BLS初始可行解產(chǎn)生算法.
算法1.BLS初始解生成流程輸入:班列間同步轉(zhuǎn)運(yùn)的集裝箱箱數(shù)矩陣A,每輛班列的最早進(jìn)入或最晚離開堆場時間段,待安排的班列集合Θ.初始化:將決策變量x和z置為0矩陣.1.根據(jù)班列最晚離開堆場的時間段對班列進(jìn)行升序排列.2.班列進(jìn)入堆場的時間段分為T個.3.時間段計數(shù)器t=1.4.while待安排的班列集合Θ不為空do 5. 從集合Θ中依次選擇m趟班列.6. if選定的m趟班列能在時間段t進(jìn)入堆場7. 讓m輛班列依次進(jìn)入堆場.8. 從集合Θ刪除已進(jìn)入堆場的班列序號.9. end if 10. 更新m趟班列間能實施集裝箱同步轉(zhuǎn)運(yùn)的0-1矩陣z和時間段指派矩陣x.11. t=t+1.12. 計算成功實施同步轉(zhuǎn)運(yùn)的集裝箱箱數(shù).13.end while 14.輸出:x和z.
鄰域搜索與擾動產(chǎn)生的候選解對應(yīng)的目標(biāo)函數(shù)值計算將耗費(fèi)大量的計算成本.為了縮短計算時間,在此依據(jù)每次班列置換后的增益來計算候選解的目標(biāo)函數(shù)值.針對數(shù)學(xué)規(guī)劃模型的特點確定班列置換判斷條件.當(dāng)班列i與班列j進(jìn)行置換時,班列i與j必須滿足置換之前各自被分配在不同的時間段,并且置換后分配的時間段不能超出各自最早進(jìn)入和最晚離開堆場時間段.π’是當(dāng)前解π通過交換位置r和s上的班列所得到的鄰域解.則當(dāng)前解π與鄰域解π’之間的增益用式(10)計算:
式(10)的時間復(fù)雜度僅為O(n).如果π’是通過交換r和s后得到的鄰域解,則對增益矩陣δ(π’,u,v)進(jìn)行計算i 被標(biāo)記為禁忌狀態(tài);重復(fù)上述過程直至達(dá)到班列j 的最大集裝箱數(shù)或所有班列均為禁忌狀態(tài)為止.?
式(11)在計算增益方面采用前解指導(dǎo)后解的思路,在保留每一階段的最優(yōu)值同時進(jìn)行置換計算,大大提高目標(biāo)函數(shù)值計算效率.
BLS算法終止須滿足下列條件之一,則停止迭代輸出最佳解結(jié)果:1)達(dá)到給定最大迭代次數(shù)10 000次;2)達(dá)到給定最大計算時間600秒.
為了驗證算法的求解質(zhì)量與效率,將所提出的算法BLS與Boysen等[14]提出的束搜索算法(Beam Search,BS)和數(shù)學(xué)規(guī)劃模型的計算結(jié)果進(jìn)行對比.數(shù)學(xué)規(guī)劃模型求解采用Gurobi8.0求解器,計算時間設(shè)定為1800秒.BLS和BS算法采用C#編程并在Visual Studio 2013中實現(xiàn).所有方法在CPU為Inter(R)Core(TM)i7-4790M@3.60 GHz、內(nèi)存為8 GB以及系統(tǒng)為Windows7的個人電腦完成測試.將各個方法求解得到的目標(biāo)函數(shù)值轉(zhuǎn)換成相對百分偏差(Relative Percent Deviation,RPD),以此作為算法性能分析的響應(yīng)變量.RPD計算如下式所示:
針對所研究的集裝箱班列轉(zhuǎn)運(yùn)調(diào)度問題,尚未有公開的算例測試集.在此利用Boysen等[14]提出的方法產(chǎn)生本問題的測試算例.為了生成測試算例,表1中列出了用于產(chǎn)生算例相關(guān)參數(shù)的取值范圍.矩陣Aij產(chǎn)生方式如下:用車廂數(shù)量乘以載荷系數(shù)產(chǎn)生班列間能夠交互的最大集裝箱箱數(shù);對于每輛班列j,隨機(jī)選取另一輛班列i,其能夠轉(zhuǎn)運(yùn)的集裝箱箱數(shù)從區(qū)間[1,MaxTr]中采用均勻分布隨機(jī)產(chǎn)生,其中MaxTr是指兩輛班列之間能夠轉(zhuǎn)運(yùn)的集裝箱箱數(shù)上限;隨后,班列
表1 算例參數(shù)表
算例的產(chǎn)生充分考慮時間限制的生成.若不限制的話,則班列i設(shè)置ei=1和li=T.若僅有進(jìn)入時間限制,則從區(qū)間[1,T]隨機(jī)確定ei并且所有l(wèi)i=T,其中ei=1有50%的概率出現(xiàn)而其余則采用均勻分布隨機(jī)產(chǎn)生.若進(jìn)入與離開均有時間限制,則從區(qū)間[1,T/2] 中選擇ei,區(qū)間[T/2,T]中選擇li,對于ei=1有50%的概率出現(xiàn),對于li=T也有50%的概率出現(xiàn).在此所有生成的算例都需要試算以保證至少存在一個可行解,否則將重新生成.表2為算例中班列與軌道的關(guān)系.
表2 班列數(shù)與軌道數(shù)取值范圍
根據(jù)班列的進(jìn)出堆場的時間段將算例分為FTSPST1,FTSPST2和FTSPST3三種類型,FTSPST1代表所有班列最早進(jìn)入與最晚離開堆場時間段一樣;FTSPST2代表所有班列最早進(jìn)入堆場時間段不同最晚離開堆場時間段相同;FTSPST3代表所有班列最早進(jìn)入最晚離開堆場時間段都不相同.針對表2所示的班列數(shù)和軌道數(shù)生成105組算例,其中12-2,12-4和16-2,16-4的算例總共生成5組,其余都為1組.
基于初始計算測試,BLS算法采用表3所示的參數(shù)將獲得不錯的計算性能,以求在較短的時間給出不錯的求解結(jié)果.
表3 BLS算法參數(shù)表
將班列數(shù)在50輛以下的歸為小規(guī)模算例,而將班列數(shù)在50輛以上歸為大規(guī)模算例.由于篇幅限制,在此僅列出班列數(shù)為12和80的算例計算詳細(xì)結(jié)果.表4給出了班列數(shù)為12的一組算例計算結(jié)果.在該表中列出了各個算法求得的目標(biāo)函數(shù)、計算時間以及利用式(12)計算出的相對百分偏差RPD,其中BLS與BS的計算時間為600秒內(nèi)首次搜索到該算例最佳解時記錄的時間.下標(biāo)BLS表示BLS算法相關(guān)的結(jié)果,下標(biāo)BS表示束搜索算法相關(guān)的結(jié)果,下標(biāo)G表示優(yōu)化器Gurobi的相關(guān)結(jié)果.從中可以看出3個方法均能夠在較短的計算時間內(nèi)給出最優(yōu)解,但BLS的計算時間最短,BS次之,優(yōu)化器Gurobi耗時最長.
表4 12輛班列算例計算結(jié)果
表5給出了班列數(shù)為80時的計算結(jié)果,其中涉及的指標(biāo)與表4一樣.從中可以看出BLS依然給出所有算例的最好解,但其計算時間比BS的用時稍長一些.優(yōu)化器Gurobi耗光了給定的時間限制1800秒,且求解性能易受算例類型的影響.也就是說進(jìn)入或離開堆場的時間段的不同使得求解空間的規(guī)模不一樣,優(yōu)化器求解性能亦不一樣.BS的求解質(zhì)量相對較為穩(wěn)定,RPD的均值為13.3%.
表5 80輛班列算例計算結(jié)果
表6和表7分別給出了小規(guī)模算例與大規(guī)模算例的平均計算結(jié)果.從計算精度上來說,對于50輛以下的班列數(shù),BLS算法能很快計算出與Gurobi相同的最優(yōu)解,而BS則與最優(yōu)解存在1.69%的差距.對于50輛以上班列數(shù)的大規(guī)模算例,Gurobi的平均計算時間為24分鐘,BLS算法為105.59秒,而BS算法僅為26.11秒,可見在大規(guī)模算例上BS算法有優(yōu)勢;但是在解的精確度上BLS算法明顯比Gurobi和BS的計算結(jié)果更好,而且BS算法在解50以上規(guī)模的FTSPST2和FTSPST3類型算例時解的精度較差,和Gurobi的計算結(jié)果相比存在較大的差距.對于100輛左右的班列數(shù),Gurobi優(yōu)化器和BS算法很難求出該問題的較優(yōu)解,而BLS能夠在230.66秒的平均計算時間內(nèi)給出最好的解.因此,BLS算法針對集裝箱班列的同步轉(zhuǎn)運(yùn)調(diào)度問題具有較為明顯的優(yōu)勢,不僅計算精確度高,而且計算耗時也很短.
表6 小規(guī)模算例平均計算結(jié)果
表7 大規(guī)模算例平均計算結(jié)果
本文在考慮同步轉(zhuǎn)運(yùn)作業(yè)需求的前提下,研究了集裝箱班列調(diào)度問題,以最大化同步轉(zhuǎn)運(yùn)的集裝箱箱數(shù)為目標(biāo),提出了相應(yīng)的混合整數(shù)規(guī)劃模型.由于該問題的復(fù)雜性,本文提出利用突破性局部搜索框架對問題進(jìn)行求解.該算法依據(jù)搜索狀態(tài)自適應(yīng)確定擾動類型與擾動幅度,以突破局部最優(yōu)解對迭代過程的束縛.基于問題的結(jié)構(gòu)特征,提出利用進(jìn)入離開堆場時間段排序的方式產(chǎn)生初始解,同時重定義了目標(biāo)函數(shù)值增益矩陣的計算方式.算例分析表明,本文所提出的BLS算法較之Gurobi優(yōu)化器與文獻(xiàn)中的BS算法具有明顯的求解優(yōu)勢,且明顯提高了調(diào)度優(yōu)化的計算效率.該優(yōu)化方法對于鐵路集裝箱站場提升運(yùn)作管理效率具有一定的理論指導(dǎo)意義.未來將公路-鐵路聯(lián)運(yùn)的轉(zhuǎn)運(yùn)需求納入該調(diào)度問題中將進(jìn)一步提升站內(nèi)作業(yè)效率.