鐵路集裝箱運輸服務網絡設計優化模型及算法

江雨星，李和壁

(1. 蘭州交通大學 交通運輸學院，蘭州 730070;2. 中國鐵道科學研究院 鐵道科學技術研究發展中心，北京 100081)

作為貨物運輸物流化的主要形式，鐵路集裝箱運輸在現代物流和國際集裝箱多式聯運體系中居于重要地位[1].每日有大量的集裝箱通過公路交通送至鐵路集裝箱辦理站，由辦理站間組織開行的集裝箱班列進行運輸.對于這樣的鐵路集裝箱運輸決策問題，最重要的任務就是設計合理的集裝箱運輸服務網絡.高質量的運輸服務網絡，不僅可滿足多樣化的運輸需求、提高客戶滿意度，同時還能保證鐵路企業的高效運營及盈利.可見，鐵路集裝箱運輸服務網絡的設計與優化具有重要的現實意義.

運輸服務網絡理論在交通運輸領域中的應用極為廣泛，如航空企業中航班時刻表的優化[2]、公路貨運中車輛運行路徑的確定[3]、海洋運輸中船舶在各航線上的合理分配[4]、鐵路運輸中旅客列車開行方案的編制[5]及客流分配[6].對于鐵路貨物運輸服務網絡的設計，國內外學者作了大量研究.Crainic[7]系統性的闡述了運輸服務網絡設計的理論與方法.Newton等[8]將貨物列車編組計劃轉化為服務網絡設計問題.王保華等[9]為解決快捷貨物運輸動態服務網絡的設計問題，建立了線性整數規劃模型.沈睿[10]針對鐵路行包快運服務產品，研究了運輸服務網絡的設計方法.唐金金等[11]將列車開行方案轉化為服務網絡，構建了服務網絡動態配流的優化模型.Duan等[12]在設計運輸服務網絡時，綜合考慮了鐵路貨物運輸的時效性及可靠性.

部分學者專門研究了鐵路集裝箱運輸服務網絡設計的問題.Newman等[13]以成本最小為優化目標建立了整數規劃模型，將大量集裝箱有效分配到開行的班列上.閆海峰等[14]采用遺傳算法求解構建的集裝箱班列開行方案優化模型.張小強等[15]為分析運輸價格制定與班列開行決策之間的關系，構建了雙層規劃模型.夏陽等[16]研究了客運化模式下集裝箱班列開行方案的編制問題.

現有的鐵路集裝箱運輸服務網絡設計的研究，雖已通過建立數學模型及設計求解算法，確定出班列運行徑路、開行頻度及箱流分配方案，但是在此過程中較少考慮集裝箱辦理站裝卸能力及鄰接路段通過能力的約束.同時，隨著鐵路企業運輸服務質量的不斷改進，客戶對于集裝箱運輸的時效性提出了更高的要求，而現有文獻很少考慮.本文綜合考慮集裝箱辦理站裝卸能力、鄰接路段通過能力及集裝箱運到期限的要求，構建鐵路集裝箱運輸服務網絡設計的線性混合整數規劃模型，并設計基于遺傳算法的求解方法.

1 問題描述

目前，我國鐵路企業組織開行的集裝箱班列主要為直達班列，即班列從出發站至到達站間途中不辦理任何集裝箱裝卸和車組甩掛作業.基于此，本文考慮任意兩集裝箱辦理站間開行的集裝箱班列均為直達班列.依據運輸服務網絡構建思想，將鐵路物理網絡中的辦理站作為服務網絡中的節點，辦理站間開行的所有直達去向作為服務網絡中有向服務弧段集合.如圖1所示，已知設有4個辦理站和4條有向路段的鐵路網絡，其對應開行的全部可能直達去向如圖2所示.將這4個辦理站作為服務網絡中的節點，所有直達去向作為節點間的服務弧段集合，如圖3所示.需要說明的是，本次研究中各服務弧段對應的直達去向在物理網絡中的實際運行路徑均已給定，為出發站至到達站間的最短路徑.例如：圖3中服務弧段1對應的直達去向為辦理站1→辦理站4，其在物理網絡中(圖1)的實際運行路徑由路段1和路段2組成.

依據鐵路貨運系統中同股車流不可拆分的性質，本文假設同一OD間的箱流同樣是不可拆分的.鐵路集裝箱運輸服務網絡的設計，就是在服務弧段集合中選出一系列連續的弧段組成服務路徑來運輸節點間的集裝箱，并確定各弧段的服務頻度(即服務弧段關聯起點與終點間開行的直達班列數量).對于任意兩節點間的箱流，可能有多條服務路徑供其選擇，不同的服務路徑表示不同的運輸作業過程.例如：對于起點為節點1、終點為節點3的箱流，可選擇服務弧段2作為服務路徑，也可選擇服務弧段3和5組成服務路徑.若選擇弧段2，則表示該箱流由1站開往3站的集裝箱班列進行直達運輸；若選擇弧段3和5，則表示該箱流先由1站開往2站的班列承運，到達2站后卸下，再裝至2站開往3站的班列將其運至終到站.同時，集裝箱辦理站裝卸能力、鄰接路段通過能力及集裝箱運到期限的限制，對服務弧段的選擇有很大的影響.例如：弧段3和5組成服務路徑的運輸時間超過了節點1去往節點3箱流的運到期限，而弧段2的運輸時間在運到期限范圍內，則該箱流只能選擇弧段2.服務弧段的選擇及其頻度的確定，不僅要滿足運輸需求，還要盡可能減小支出成本，再加上辦理站裝卸能力、鄰接路段通過能力及運到期限約束，使得問題求解比一般的網絡設計更為困難.

2 優化模型構建

2.1 參變量定義

2.2 優化模型

2.2.1 目標函數

本文以成本最小為優化目標，總成本分為兩部分,一部分是服務成本(班列的開行成本),另一部分是與集裝箱運輸有關的成本，后者包括途中運輸成本及中轉裝卸成本，則目標函數如式(1)所示.

(1)

2.2.2 約束條件

1) 箱流唯一性約束

(2)

表示任意1組箱流在途中是不可拆分的.

2) 流量守恒約束

(3)

表示任意1組箱流在途經站的中轉裝卸是連續的，并保證全部集裝箱能從出發站點運送至終到站點.

3) 箱流中轉裝卸約束

(4)

4) 運到期限約束

(5)

表示任意箱流的運輸時間不能超過規定的運到期限，其中箱流的運輸時間包括出發站點收箱至將集裝箱發出的時間、途經辦理站的中轉裝卸作業時間及途中運行時間.

5) 辦理站裝卸能力約束

(6)

6) 路段通過能力約束

(7)

表示物理網絡中任意有向路段上通過的班列數量，不能超過該路段的通過能力.

7) 服務能力與箱流量的關系約束

(8)

表示弧段的服務能力應滿足所運輸的箱流量.

3 算法設計

本文構建的模型為線性混合整數規劃模型，隨著鐵路網絡規模、集裝箱運輸需求的增加，精確求解算法或商業優化軟件無法在接受時間內得到優化結果.遺傳算法是一種基于隨機搜索的群體智能算法，具有較高的求解效率，本文將運用遺傳算法求解構建的數學模型.

3.1 染色體編碼

(9)

3.2 初始種群

在滿足運輸完整性的約束下，箱流通過連續的服務弧段組成1條由出發站點至終到站點的服務路徑，因此，確定箱流與服務弧段的對應關系可視為服務路徑的選擇.服務路徑選擇的前提和基礎是要確定出各箱流可選擇的服務路徑集合.為此，本文運用回溯法的思想，搜索滿足箱流唯一性、流量守恒及運到期限約束的的可行服務路徑.對于箱流q，可行服務路徑的搜索流程如下：

Step1：令Lq表示箱流q的運輸時間，選定箱流q的出發站點o(q)作為搜索起點，并將起點o(q)視為當前節點，初始化運輸時間Lq=wq，轉Step2；

Step2：檢查以當前節點為起點的服務弧段是否都已遍歷，若都已遍歷，轉Step5；否則，轉Step3；

Step3：在以當前節點為起點的服務弧段中，選擇未遍歷的弧段a，已知該弧段的終點為u，更新運輸時間Lq=Lq+τa，判斷運輸時間是否滿足運到期限的要求，若Lq≤Tq，轉Step4；否則，將弧段a標記為已遍歷，返回該弧段起點，同時還原運輸時間Lq=Lq-τa，轉Step2；

得到各OD箱流可選的服務路徑集合后，依次讓各箱流在其可行路徑方案中隨機選取1條路徑，以此產生一定數量的初始方案.再將各初始方案代入式(9)，計算不同方案下的服務頻度.

上述生成初始種群的方法可使各染色體均滿足箱流唯一性、流量守恒及運到期限約束.對于其中不滿足辦理站裝卸能力及路段通過能力約束的初始染色體，則運用下文設計的啟發式策略進行修復.

3.3 染色體修復

算法設計的核心思想，就是通過交叉、變異等操作對箱流選擇的服務路徑進行不斷改變.顯然，初始染色體及遺傳操作后產生的新染色體始終滿足箱流唯一性、流量守恒及運到期限約束，但是各OD箱流選擇的服務路徑及各弧段服務頻度的不斷變化，使得辦理站裝卸集裝箱數量及路段通過班列數量隨之改變，部分染色體可能不滿足辦理站裝卸能力及路段通過能力要求.對于這些不可行染色體，需設計適宜的方法進行處理.相較于既有文獻常采用的罰函數法和直接刪除法，染色體修復可使種群規模不改變的同時，保證染色體組合的多樣性.為此，本文考慮對不可行的染色體進行修復，并設計相應的啟發式修復規則.

啟發式修復規則的實現過程具體為：檢驗各節點裝卸的集裝箱數量，對于節點n，若裝卸的集裝箱數量超過裝卸能力kn，則選出在該節點進行中轉裝卸的任意1組箱流，在其可選的路徑集合中選出不在節點n中轉的1條路徑，替換當前路徑.同時，檢驗各路段上通過的班列數量是否滿足要求，若路段e上通過的班列數量大于其通過能力fe，則先選出對應的直達去向在物理網絡中的實際運行路徑經過路段e的服務弧段a，再選取通過服務弧段a的任意1組箱流，在該箱流可選的路徑集合中選出不經過弧段a的1條路徑替換當前路徑.以此進行調整，直至各辦理站裝卸箱數及各路段上通過的班列數量滿足約束要求.

3.4 遺傳算法流程

設計遺傳算法流程如下：

Step1：生成初始種群.

Step2：令目標函數的倒數為適應度函數，將當前所有染色體帶入適應度函數計算適應度值.

Step3：選擇操作.為避免優秀個體被破壞，采用輪盤賭與精英保留相結合的策略進行選擇.

Step4：交叉操作.隨機選取1組箱流，將表示該箱流及之后所有箱流與服務弧段對應關系的基因，與另一染色體中相同位置的基因進行互換，修復不可行染色體.

Step5：變異操作.在執行變異操作的染色體中，隨機選取1組箱流，改變該箱流與服務弧段對應關系，即在其可選的服務路徑集合中任選1條與當前不同的路徑進行替換，修復不可行染色體.

Step6：判斷循環終止條件，若迭代次數沒有達到設定的最大循環次數，則轉Step2；否則算法結束.

4 求解算例

4.1 參數輸入

構造如圖5所示的路網結構對本文模型和算法進行仿真計算，圖中圓圈表示鐵路集裝箱辦理站，連線為車站之間的有向路段.鐵路物理網絡中路段相關參數如表1所列，服務網路中服務弧段相關參數如表2所列，各OD箱流相關參數如表3所列.各OD箱流的出發站收箱至將集裝箱發出的時間均為4 h，途經各站辦理中轉裝卸作業的時間均為8 h，運到期限均為24 h.各服務弧段對應直達去向上班列的運行時間，由物理網絡中該去向途經各路段的運行時間相加而得，各辦理站裝卸能力均為1 800箱，中轉裝卸成本為10元/箱，班列的最大編成箱數為50箱.

表1 路段相關參數Tab.1 Related parameters of each section

表2 服務弧段相關參數Tab.2 Related parameters of each service arc

表3 箱流相關參數Tab.3 Related parameters of container flow

4.2 求解結果分析

運用Matlab2014編程對算例進行測試，種群規模取30，交叉概率取0.9，變異概率取0.09，迭代次數為500次.計算過程中適應度函數值的變化如圖6所示，在運行了104 s后得到最終解，其適應度值為6.264 890 86×10-8，目標函數值為15 961 970元.由圖6可知，隨著迭代次數的增加，適應度函數值逐漸增加，在260次以后，適應度值已無明顯變化，表明算法的收斂性良好，具有較高的計算效率.

表4 箱流經過的服務弧段Tab.4 Passing service arcs of each container flow

表5 服務頻度Tab.5 Service frequency

表6 各集裝箱辦理站裝卸箱數Tab.6 Number of containers loaded and unloaded at each container terminal

表7 各路段通過的班列數量Tab.7 Number of trains passing each section

5 結論

本文對鐵路集裝箱運輸服務網絡的設計方法進行了研究，運用遺傳算法求解構建的線性混合整數規劃模型，通過算例的求解表明：對于大規模的集裝箱運輸服務網絡設計問題，提出的模型及算法可在較短時間內獲得滿意解，具有較高的計算效率；所得結果中，各OD間箱流的運輸時間均在運到期限范圍內，集裝箱辦理站裝卸箱數和路段通過班列數量均滿足能力要求，驗證了本文提出的方法是有效可行的，可為鐵路企業優化集裝箱運輸組織提供決策參考.現實中部分班列需在途經站辦理集裝箱裝卸或車組甩掛作業，未來研究會針對這一情況做深入分析，使設計的方案與現實更好的吻合.