基于突破性局部搜索的集裝箱班列同步轉運作業調度優化①

何 迅,郭 鵬,欒玉麟

(西南交通大學 機械工程學院,成都 610031)

(軌道交通運維技術與裝備四川省重點實驗室,成都 610031)

鐵路運輸作為最為低碳的貨運方式,在內陸腹地運輸方面極具優勢.我國鐵路貨運總量占比在面臨殘酷的市場競爭時連年下滑,已由2009年的11.96%降至2017年的7.81%[1].目前我國鐵路集裝箱運量僅占鐵路貨運量的5.4%,遠遠低于發達國家(美國占比49%,法國占比40%,英國占比30%,德國占比20%,日本占比100%)[2].如此大的差距表明我國鐵路集裝箱運輸存在巨大的潛力和發展空間.當前,我國沿海港口積極發展內陸“無水港”,加快港口鐵路集疏運,積極推動船、車、班列、港口、場站、貨物等信息開放共享.國家“十一五規劃”規劃建設了18 個鐵路集裝箱中心站,有利于實現區域集裝箱鐵路運輸與其他運輸方式的無縫銜接.在“一帶一路”國家戰略的帶動下,鐵路集裝箱多式聯運更是迎來了彌足珍貴的發展契機,研究提升鐵路集裝箱多式聯運效率具有重要的現實與戰略意義.

作為多式聯運鐵路站場主要活動,轉運作業效率直接影響鐵路集裝箱多式聯運的整體運作水平.為了保證自動化堆場作業計劃生成的準確性,現有鐵路集裝箱站場轉運作業均要求集裝箱班列或卡車經堆場方可實現.經集裝箱站場實現不同運載工具之間的轉運必然存在兩次裝卸和一次暫存作業.對于提高轉運作業效率來說,暫存和額外的裝卸作業完全是無效操作,且會使有限的堆場空間資源更為緊張.減少暫存中轉作業的關鍵是提高同步轉運(也叫連續轉運或直裝直卸)集裝箱比率.同步轉運旨在通過合理安排集裝箱班列進入堆場的作業時間窗,實現在站的兩類運輸設備之間的集裝箱流同步交互,盡可能地縮短集裝箱站內中轉時間.

國內外學者對鐵路集裝箱站場的作業效率提升進行了不少研究.Boysen等[3]對鐵路站場的設施布局與作業調度優化研究現狀進行了歸類總結.Otto和Pesch[4]分析了多式聯運下鐵路堆場中班列與堆場指派問題,以最小化再指派次數為目標更新了下界計算方法.Boysen等[5]構建了鐵路-鐵路(Rail-Rail)站場的數學規劃模型來確定主裝卸線上各臺起重機的最優作業區域.Kellner等[6]考慮集裝箱班列停靠位置對轉運作業的影響,并構建數學模型來確定其最佳位置以便減少集裝箱移動距離.Boysen等[7,8]提出采用集裝箱整理系統支持站內轉運,并對比分析了四種不同的集裝箱整理系統在鐵路-鐵路聯運站場中的作業效率.起重機作為集裝箱站場的主要轉運設備,Guo等[9,10]對公鐵聯運的集裝箱中心站軌道式起重機調度問題進行了建模優化,并希望將外部卡車服務水平納入調度優化模型.王力等[11,12]認為集裝箱班列卸箱作業和裝箱作業過程相同,以卸箱作業過程建立了中心站起重機調度優化模型,設計了混合粒子群算法進行求解;還考慮堆場混堆優化問題,以兩階段優化模型來平衡堆場各箱區進站箱和出站箱的數量及減少堆存所產生的壓箱數.而上述研究聚焦在鐵路站場的箱位指派、集裝箱班列位置指派、裝卸設備調度問題上,尚未考慮同步轉運作業.

在不同的運輸方式之間利用轉運工具實現乘客或貨物中轉,盡可能保證進出運載工具的同步,能夠大幅提升轉運效率[13].Boysen等[14]為鐵路-鐵路(Rail-Rail)集裝箱站場調度問題構建了數學模型,通過確定集裝箱班列集合中每趟車的服務間隙來最小化班列重回站場的次數和集裝箱分割裝卸的移動次數,證明了該問題是NP-hard的,并提出了基于動態規劃和束搜索的求解算法.該研究對集裝箱班列的轉運調度進行優化,以求實現同步轉運,本文在此基礎上提出集裝箱班列同步轉運調度模型,通過分析問題的特征設計基于突破性局部搜索的求解算法.利用算例驗證本文算法可以在提高求解質量的同時,顯著縮短求解時間,對站場效率提升具有重要的參考價值.

1 問題描述與數學模型

在集裝箱班列同步轉運作業調度問題(Freight Trains Scheduling Problem with Synchronized Transferring,FTSPST)中,n趟班列需要進入堆場實施裝卸轉運操作.堆場鋪設有m組并行鐵軌,每次最多可牽引m趟班列進入.假設有T個時間段實施牽引進站作業,則有T=n/m.為了方便描述,在此假設n=T×m.在實際作業過程中,若班列數不足n,可通過引入未裝載集裝箱的虛擬班列來滿足.針對班列i(i=1,…,n),最早進入堆場時間段為ei,最晚離開堆場時間段為li.假設班列i和j之間存在Aij個集裝箱須進行轉運,若兩趟班列能夠在同一時間段t牽引進堆場,則可成功實現Aij個集裝箱同步轉運.需要轉運到班列i的集裝箱位于其他班列之上,用Li表示能與班列i進行同步轉運作業的其他班列集合.在此定義決策變量xit與zij,若集裝箱班列i進入堆場的時間段為t則xit=1,否則為0;若集裝箱班列i和j在同一時間段進入堆場則zij=1,否則為0.以同步轉運的集裝箱箱數最大化為優化目標,構建如下混合整數規劃模型:

s.t.

上述優化模型中,目標函數(1)保證同步轉運的集裝箱箱數最大化;約束(2)確保一輛班列只能被安排在一個時間段;約束(3)確保同一時間段內進入堆場的班列數不超過鋪設的軌道數;約束(4)表示同一時間段進入堆場的班列i和j對應的變量zij必須為1;約束(5)定義決策變量的取值范圍.

2 突破性局部搜索算法

突破性局部搜索算法(Breakout Local Search,BLS)是一種自適應的鄰域搜索算法,在一般鄰域搜索算法的基礎上增加了自適應擾動機制,能快速逃離局部最優以及提高穩定性[15].該算法分為局部搜索階段和擾動階段.通過某種方法產生初始可行解π0,利用鄰域搜索算子產生所有的可行解,從中找出局部最優解π.然后通過適當的擾動對當前解π進行操作以幫助算法逃離當前的局部最優解,擾動獲得的解將成為下一輪鄰域搜索的起點.上述搜索一直迭代直到達到算法終止條件為止.BLS算法在搜索過程中融入了局部迭代搜索、禁忌搜索與模擬退火算法的操作機制,具有搜索質量高、計算時間短等優點,現已用于求解最大團問題[16]、最大割問題[17]、二次指派問題[15]、裝配序列規劃問題[18]以及門分派問題[19]等,并獲得較好的求解效果.BLS算法流程圖如圖1所示.

圖1 BLS算法流程圖

2.1 自適應擾動機制

BLS算法對局部最優解的擾動取決于擾動幅度和擾動類型,擾動的強弱依賴于當前搜索操作的狀態,主要是通過當前解π和當前最佳解連續未改善的次數ω來確定擾動幅度K和擾動類型[16].BLS首先搜索鄰近的局部最優解,只有當搜索停滯不前,才能移動到下一個鄰域.在每次局部搜索后,BLS執行小幅度的定向或近似隨機移動,以保證能夠逃離當前局部最優解.如果擾動幅度不足以逃離局部最優解,則增加擾動幅度K;否則將其設置為默認值,即K=K0.如果當前最佳解連續未改善的次數超過了給定的閥值Ω,則將擾動幅度設置為最大值Kmax,以保證搜索過程能夠脫離當前鄰域解空間.

所提出的BLS算法采用置換序列的編碼形式,譬如5趟班列與2組鐵軌的算例,則當前解序列π={1,5,2,3,4},其中π2=5表示編號為5的班列安排在序列位置2處,若班列1與班列5均可在時間段t=1進入堆場,則其進入堆場的時間段為1.鄰域操作與擾動采用交換操作,則π’=π⊕swap(u,v)表示交換位置u和v上的班列序號得到新的候選解.

BLS算法采用以下三種擾動類型:定向,近似隨機和隨機擾動.定向擾動基于禁忌搜索原則來實施,當搜索到的候選解優于目前為止找到的最佳解時,該操作對應的禁忌狀態消除.同時產生候選解的操作在禁忌周期γ之外時,也可消除禁忌狀態.定向擾動依賴于上一次迭代搜索的歷史信息以及不會禁止良好的擾動操作.針對定向擾動的判斷由集合 R表征:

其中,H是上次執行擾動時跟蹤迭代次數的矩陣,Iter是當前迭代次數,f是當前解對應的目標函數值,fbest是當前已找到的最佳解對應的目標函數值,u、v為需要進行置換擾動的變量.γ值越大代表著擾動越強烈,在 BLS 算法中γ=n×r1+rand(0,1)×n×r2,其中r1與r2為待確定的常數值.近似隨機擾動僅依賴于由H矩陣提供的歷史信息,由集合 Z表征為:

隨機擾動簡單地執行隨機均勻的擾動,由集合C表征:

為了實現強化搜索和多樣性搜索的平衡,BLS算法引入概率選擇操作確定擾動類型.根據當前搜索狀態和當前最佳解連續未改善的次數ω動態確定應用特定擾動的概率.在迭代搜索過程中,若找到新的最佳解或ω超過給定閾值Ω時,ω被重置為零.鄰域搜索初期算法更偏向于采用定向擾動.隨著ω的增加,使用定向擾動的幾率逐漸降低,同時隨機和近似隨機擾動的概率會增加,從而達到自適應的多樣性擾動.

另外,從計算分析中已經觀察到,保證定向擾動的最小概率是有用的.因此,采用定向擾動的概率p取不小于閾值p0的值:

基于計算出的定向擾動概率p,則可分別通過(1-p)*Q和(1-p)*(1-Q)確定近似隨機和隨機擾動的概率,其中Q為區間[0,1]之間的常數.確定了各自的概率后,則可通過區間位于(0,1)之間隨機數來確定擾動類型.

2.2 基于問題的算法改進

鐵路集裝箱班列同步轉運過程中,存在每輛班列最早與最晚離開堆場的時間段和現有鐵軌數的約束.為此需對BLS算法進行必要的改進以適應所考慮的問題.為了加快算法搜索速度,在此設計算法1中的BLS初始可行解產生算法.

算法1.BLS初始解生成流程輸入:班列間同步轉運的集裝箱箱數矩陣A,每輛班列的最早進入或最晚離開堆場時間段,待安排的班列集合Θ.初始化:將決策變量x和z置為0矩陣.1.根據班列最晚離開堆場的時間段對班列進行升序排列.2.班列進入堆場的時間段分為T個.3.時間段計數器t=1.4.while待安排的班列集合Θ不為空do 5. 從集合Θ中依次選擇m趟班列.6. if選定的m趟班列能在時間段t進入堆場7. 讓m輛班列依次進入堆場.8. 從集合Θ刪除已進入堆場的班列序號.9. end if 10. 更新m趟班列間能實施集裝箱同步轉運的0-1矩陣z和時間段指派矩陣x.11. t=t+1.12. 計算成功實施同步轉運的集裝箱箱數.13.end while 14.輸出:x和z.

鄰域搜索與擾動產生的候選解對應的目標函數值計算將耗費大量的計算成本.為了縮短計算時間,在此依據每次班列置換后的增益來計算候選解的目標函數值.針對數學規劃模型的特點確定班列置換判斷條件.當班列i與班列j進行置換時,班列i與j必須滿足置換之前各自被分配在不同的時間段,并且置換后分配的時間段不能超出各自最早進入和最晚離開堆場時間段.π’是當前解π通過交換位置r和s上的班列所得到的鄰域解.則當前解π與鄰域解π’之間的增益用式(10)計算:

式(10)的時間復雜度僅為O(n).如果π’是通過交換r和s后得到的鄰域解,則對增益矩陣δ(π’,u,v)進行計算i 被標記為禁忌狀態;重復上述過程直至達到班列j 的最大集裝箱數或所有班列均為禁忌狀態為止.?

式(11)在計算增益方面采用前解指導后解的思路,在保留每一階段的最優值同時進行置換計算,大大提高目標函數值計算效率.

BLS算法終止須滿足下列條件之一,則停止迭代輸出最佳解結果:1)達到給定最大迭代次數10 000次;2)達到給定最大計算時間600秒.

3 算例分析

為了驗證算法的求解質量與效率,將所提出的算法BLS與Boysen等[14]提出的束搜索算法(Beam Search,BS)和數學規劃模型的計算結果進行對比.數學規劃模型求解采用Gurobi8.0求解器,計算時間設定為1800秒.BLS和BS算法采用C#編程并在Visual Studio 2013中實現.所有方法在CPU為Inter(R)Core(TM)i7-4790M@3.60 GHz、內存為8 GB以及系統為Windows7的個人電腦完成測試.將各個方法求解得到的目標函數值轉換成相對百分偏差(Relative Percent Deviation,RPD),以此作為算法性能分析的響應變量.RPD計算如下式所示:

3.1 算例設計

針對所研究的集裝箱班列轉運調度問題,尚未有公開的算例測試集.在此利用Boysen等[14]提出的方法產生本問題的測試算例.為了生成測試算例,表1中列出了用于產生算例相關參數的取值范圍.矩陣Aij產生方式如下:用車廂數量乘以載荷系數產生班列間能夠交互的最大集裝箱箱數;對于每輛班列j,隨機選取另一輛班列i,其能夠轉運的集裝箱箱數從區間[1,MaxTr]中采用均勻分布隨機產生,其中MaxTr是指兩輛班列之間能夠轉運的集裝箱箱數上限;隨后,班列

表1 算例參數表

算例的產生充分考慮時間限制的生成.若不限制的話,則班列i設置ei=1和li=T.若僅有進入時間限制,則從區間[1,T]隨機確定ei并且所有li=T,其中ei=1有50%的概率出現而其余則采用均勻分布隨機產生.若進入與離開均有時間限制,則從區間[1,T/2] 中選擇ei,區間[T/2,T]中選擇li,對于ei=1有50%的概率出現,對于li=T也有50%的概率出現.在此所有生成的算例都需要試算以保證至少存在一個可行解,否則將重新生成.表2為算例中班列與軌道的關系.

表2 班列數與軌道數取值范圍

根據班列的進出堆場的時間段將算例分為FTSPST1,FTSPST2和FTSPST3三種類型,FTSPST1代表所有班列最早進入與最晚離開堆場時間段一樣;FTSPST2代表所有班列最早進入堆場時間段不同最晚離開堆場時間段相同;FTSPST3代表所有班列最早進入最晚離開堆場時間段都不相同.針對表2所示的班列數和軌道數生成105組算例,其中12-2,12-4和16-2,16-4的算例總共生成5組,其余都為1組.

基于初始計算測試,BLS算法采用表3所示的參數將獲得不錯的計算性能,以求在較短的時間給出不錯的求解結果.

表3 BLS算法參數表

3.2 算例計算分析

將班列數在50輛以下的歸為小規模算例,而將班列數在50輛以上歸為大規模算例.由于篇幅限制,在此僅列出班列數為12和80的算例計算詳細結果.表4給出了班列數為12的一組算例計算結果.在該表中列出了各個算法求得的目標函數、計算時間以及利用式(12)計算出的相對百分偏差RPD,其中BLS與BS的計算時間為600秒內首次搜索到該算例最佳解時記錄的時間.下標BLS表示BLS算法相關的結果,下標BS表示束搜索算法相關的結果,下標G表示優化器Gurobi的相關結果.從中可以看出3個方法均能夠在較短的計算時間內給出最優解,但BLS的計算時間最短,BS次之,優化器Gurobi耗時最長.

表4 12輛班列算例計算結果

表5給出了班列數為80時的計算結果,其中涉及的指標與表4一樣.從中可以看出BLS依然給出所有算例的最好解,但其計算時間比BS的用時稍長一些.優化器Gurobi耗光了給定的時間限制1800秒,且求解性能易受算例類型的影響.也就是說進入或離開堆場的時間段的不同使得求解空間的規模不一樣,優化器求解性能亦不一樣.BS的求解質量相對較為穩定,RPD的均值為13.3%.

表5 80輛班列算例計算結果

表6和表7分別給出了小規模算例與大規模算例的平均計算結果.從計算精度上來說,對于50輛以下的班列數,BLS算法能很快計算出與Gurobi相同的最優解,而BS則與最優解存在1.69%的差距.對于50輛以上班列數的大規模算例,Gurobi的平均計算時間為24分鐘,BLS算法為105.59秒,而BS算法僅為26.11秒,可見在大規模算例上BS算法有優勢;但是在解的精確度上BLS算法明顯比Gurobi和BS的計算結果更好,而且BS算法在解50以上規模的FTSPST2和FTSPST3類型算例時解的精度較差,和Gurobi的計算結果相比存在較大的差距.對于100輛左右的班列數,Gurobi優化器和BS算法很難求出該問題的較優解,而BLS能夠在230.66秒的平均計算時間內給出最好的解.因此,BLS算法針對集裝箱班列的同步轉運調度問題具有較為明顯的優勢,不僅計算精確度高,而且計算耗時也很短.

表6 小規模算例平均計算結果

表7 大規模算例平均計算結果

4 結論

本文在考慮同步轉運作業需求的前提下,研究了集裝箱班列調度問題,以最大化同步轉運的集裝箱箱數為目標,提出了相應的混合整數規劃模型.由于該問題的復雜性,本文提出利用突破性局部搜索框架對問題進行求解.該算法依據搜索狀態自適應確定擾動類型與擾動幅度,以突破局部最優解對迭代過程的束縛.基于問題的結構特征,提出利用進入離開堆場時間段排序的方式產生初始解,同時重定義了目標函數值增益矩陣的計算方式.算例分析表明,本文所提出的BLS算法較之Gurobi優化器與文獻中的BS算法具有明顯的求解優勢,且明顯提高了調度優化的計算效率.該優化方法對于鐵路集裝箱站場提升運作管理效率具有一定的理論指導意義.未來將公路-鐵路聯運的轉運需求納入該調度問題中將進一步提升站內作業效率.