基于需求響應的鐵路集裝箱班列始發時刻優化

江雨星，高翠香，牛惠民

(1.蘭州交通大學 交通運輸學院，甘肅 蘭州 730000；2.北京交通大學 遠程與繼續教育學院，北京 100044)

制定合理的鐵路集裝箱班列始發時刻是鐵路集裝箱運輸組織的重要工作。隨著“一日一圖”列車運行組織模式的實行，集裝箱班列始發時刻的確定，不僅需要根據鐵路集裝箱辦理站和鄰接線路的技術條件，還要綜合考慮當日集裝箱貨物到達辦理站的時刻和數量，即所制定的列車開行計劃盡可能適應貨物的需求特征，這是鐵路改進貨運服務質量、迎接市場競爭的必然選擇。

集裝箱班列始發時刻優化屬于貨物列車運行圖優化問題。目前，國內外許多學者對貨物列車運行圖的優化進行了研究。文獻[1]在旅客列車運行線已定的情況下，研究了如何加入貨物列車運行線，運用拉格朗日松弛算法對建立的線性整數規劃模型進行求解。文獻[2]針對貨物列車在路網中運行徑路固定與不固定2種情況，建立了列車運行圖優化的混合整數規劃模型。文獻[3—4]研究了貨物列車運行圖與機車周轉的協同優化問題。

隨著用戶對鐵路服務質量要求的不斷提高，基于需求響應的列車運行圖優化是近年來的研究熱點，尤其在旅客列車方面，已取得較為豐富的成果。文獻[5]依據時變的客流需求及給定的停站模式，以旅客候車時間最少為目標構建了二次整數規劃模型。文獻[6]研究了基于需求驅動的地鐵列車時刻表優化問題。文獻[7]在編制列車運行圖時，綜合考慮了旅客需求和企業利益。文獻[8]針對列車間非定序越行的情況，建立了基于客流需求響應的時刻表優化模型。對于需求響應下貨物列車運行圖的優化，還少有文獻進行研究，但已有學者考慮了貨物與列車的復雜匹配關系。文獻[9]在列車始發時刻給定的前提下，充分考慮了貨主托運貨物的數量、出發時間等因素，以貨物停留時間最小為目標，構建了整數規劃模型，實現不同貨物與列車之間的最優匹配。

綜上，既有貨物列車運行圖的研究成果，主要集中在通過建立數學模型及求解算法，解決不同列車對車站、區間占用的時空沖突問題，但沒有考慮貨流的需求，這樣得到的貨物列車運行圖，會造成車站“貨物排隊”或“有線無車”的現象。在旅客列車運行圖的優化研究中，已有很多學者考慮了客流需求，但鐵路旅客運輸與集裝箱貨物運輸之間存在很大差異，現有的旅客列車運行圖研究理論無法解決基于需求響應的集裝箱班列始發時刻優化問題。

對于運輸時效性要求較高的集裝箱班列，現有研究主要集中在班列開行方案設計和集裝箱裝載方案優化方面。文獻[10]以成本最小為目標，建立了集裝箱班列開行方案優化的整數規劃模型，將集裝箱有效地分配到開行的直達和中轉班列上。文獻[11]研究了鐵路集裝箱班列開行方案與價格制定綜合優化問題。文獻[12]以單層集裝箱班列為研究對象，構建了裝載方案優化的混合整數規劃模型。文獻[13]針對于雙層集裝箱班列，探討了不同類型集裝箱的裝載方案。目前，還未有文獻考慮過集裝箱班列始發時刻的優化問題。

本文將依據鐵路集裝箱貨物運輸需求，充分考慮集裝箱貨物與班列在時間和數量方面的匹配關系，構建鐵路集裝箱班列始發時刻優化的非線性混合整數規劃模型，結合模型特點，設計基于遺傳算法的求解方法，優化基于需求響應的鐵路集裝箱班列始發時刻。

1 問題描述及假設

以1個大型鐵路集裝箱辦理站為例，每天有大量的集裝箱貨物(以下簡稱為集裝箱)通過公路交通運送至該站，并在發送箱區進行集結，集結至要求的數量后，在集裝箱裝卸線上裝入開往目的站的集裝箱班列。對于這種運量大、貨源相對穩定的集裝箱運輸問題，貨物需求主要體現在各批集裝箱送到辦理站的時間和數量。基于此，本文優化班列始發時刻的主要依據就是這些集裝箱送達辦理站的時間和數量，該信息可通過鐵路集裝箱運輸管理信息系統獲得。

集裝箱班列始發時刻對需求的響應，表現為班列運行線的分布要盡可能與動態的集裝箱需求相吻合。班列選擇不同的出發時刻，將導致集裝箱等待時間、班列裝車時間均會發生變化。如圖1所示，當第q-3，q-2和q批集裝箱由第j班列承運時，班列出發時刻Tj與這3批集裝箱到站時刻τq-3，τq-2和τq的間隔，要滿足裝車作業時間和出發技術作業時間的要求。

鐵路貨物運輸中，任意1批貨物只能由1列車運送。為滿足集裝箱班列編成箱數的要求，對于相鄰到達的2批集裝箱，其與班列間的最優匹配不一定遵循通常的“先到先服務”原則。如圖1中，對于第j班列，承運第q-3和q-2批集裝箱后，剩余承運能力小于第q-1批集裝箱的數量，但大于等于較晚送達的第q批集裝箱的數量，此時該班列將承運第q批集裝箱，而第q-1批集裝箱由后出發的第j+1班列承運。

圖1 集裝箱與班列匹配示意圖

可見，在時間及數量雙重條件的約束下，集裝箱與班列的匹配關系會非常復雜，從而極大地增加了鐵路集裝箱班列始發時刻優化的難度。為構建優化模型，做以下假設。

(1)在鐵路集裝箱辦理站，集裝箱到達、集結和裝車等作業都是滾動的，對于較晚到站的一些集裝箱，可能當天無法被運走。考慮這一情況，假定每天的最后時刻總有1列虛擬班列出發，用以承運當天未能運走的剩余集裝箱，并對裝載至該虛擬班列的集裝箱賦予較大的等待時間權重。

(2)集裝箱貨物均由20英尺的標準集裝箱裝載，每批到達辦理站的集裝箱數量不大于班列的最大編成箱數。當集裝箱數量大于最大編成箱數時，將其分割為多批，使任何1批都滿足假設條件。

2 優化模型構建

2.1 參數定義

定義如下符號和參數：Q為在24 h(1 d)內送達辦理站的集裝箱批次集合，Q={1,2,…,q,…,m-1,m}，其中m為集裝箱總批數；J為集裝箱班列序號集合，J={1,2,…,j,…,k-1,k}，其中k-1為實際開行的集裝箱班列數量，k為虛擬班列；nq為第q批集裝箱的箱量，箱；tz為單個集裝箱的平均裝車作業時間，min；tf為集裝箱班列辦理出發技術作業時間，min；Nmax和Nmin分別為集裝箱班列最大、最小編成箱數，箱；M為充分大的正數。

通常情況是在集裝箱班列開行數量給定條件下，需要確定集裝箱與班列之間的最優匹配。為確保運輸能力充足，可依據式(1)給定實際開行的班列數量，再根據下文的數學模型優化班列始發時刻。

(1)

2.2 優化模型

1)約束條件

(1)集裝箱裝車唯一性約束：任意1批集裝箱只能由1列班列運輸。

(2)

(2)集裝箱班列編成箱數約束：班列的編成箱數應在[Nmin,Nmax]范圍內。

(3)

(3)作業時間約束：班列出發時刻與其承運集裝箱到站時刻的間隔要滿足裝車作業時間和出發技術作業時間的要求。

q∈Q,j∈J{k}

(4)

(4)集裝箱班列發車間隔約束：承運同一目的站集裝箱的班列，需要在同一條集裝箱裝卸線上辦理裝車作業和出發技術作業，因此，第j班列發車后，第j+1班列才能開始進行裝車，則相鄰2列班列的發車間隔要滿足后一班列的作業時間要求。

j∈J{k-1,k}

(5)

2)始發時刻優化模型

以集裝箱在辦理站總停留時間Z最小為目標函數，以式(2)—式(5)為約束條件，建立的基于需求響應的鐵路集裝箱班列始發時刻優化模型為

(6)

s.t.

式(2)—式(5)

當集裝箱在辦理站總停留時間最小，所對應的班列始發時刻即為得到的優化結果。需要說明的是：為使到達辦理站的集裝箱盡可能當天裝車運走，應對剩余至第2天的集裝箱賦予較大的等待時間懲罰，參照鐵路旅客車站等待時間的近似計算方法[5]，本文在優化過程中假定虛擬班列延誤半天，即該班列的始發時刻Tk=1 440+720=2 160。

3 算法設計

3.1 精確求解

上述模型是一個非線性混合整數規劃問題，且約束條件為線性。運用Gurobi求解器可以對構建的模型進行精確求解，結果見表1。

表1 不同規模算例的Gurobi計算時間及優化間隙

由表1可知，當集裝箱為30批、班列數為3列時，Gurobi在4.6 s內即可得到最優解，當集裝箱和班列數量分別增加到60批和6列，求解時間達1 h時仍未獲得最優解。顯然，隨著集裝箱和班列數量的增加，運用Gurobi這類求解軟件很難得到問題的最優解。

3.2 遺傳算法設計

遺傳算法是一種基于隨機搜索的群體智能算法，具有較高的求解效率，并多次用于列車運行圖的計算問題[4,14]。因此，本文將運用遺傳算法求解構建的數學模型。算法的核心思想，是在滿足集裝箱班列編成箱數、裝車作業時間、發車間隔約束的基礎上，通過交叉、變異等操作對集裝箱與班列匹配關系進行不斷改變，從而尋找班列最有利的始發時刻。

3.2.1 染色體編碼

為避免染色體過長影響計算效率，本文采用整數編碼方案。每個染色體由2部分組成：第1部分是集裝箱與班列的匹配關系，所含的基因數量等于集裝箱總批數，其位置順序為集裝箱批次，取值為班列的序號，如圖2所示，第1部分中第2個基因的值為3，表示第2批集裝箱由第3列班列承運；第2部分為各集裝箱班列的始發時刻，所含的基因數量等于班列數量，其中最后1個基因取值為2 160，其余基因的取值為[0,1 440]間的整數，如第2部分中第3個基因值為420，表示第3列班列的始發時刻為420÷60=07:00。

圖2 染色體編碼方案示意圖

顯然，采用上述編碼方案，可使染色體在遺傳操作過程中始終滿足集裝箱裝車唯一性約束。

3.2.2 初始種群

1)隨機方案

j∈J{k}

(7)

2)遵循“先到先服務”的方案

例如：在時間段[0,60]內，有10批集裝箱陸續到達辦理站，相關參數見表2；班列編成箱數Nmax=10，Nmin=5，單個集裝箱平均裝車作業時間tz=1 min，出發技術作業時間tf=5 min；班列數量為4，其中第4列為虛擬班列，給定其始發時刻T4=60+30=90。

表2 集裝箱批次、數量及時間信息

在滿足班列編成箱數的約束下，對于第1班列，承運集裝箱的方案共有3種，分別是承運第1和第2批集裝箱(共6箱)、第1批至第3批集裝箱(共8箱)、第1批至第4批集裝箱(共10箱)。采用最后1批集裝箱標號表示相應的方案，則第1班列承運方案如圖3中的j=1所示。當第1班列承運第1和第2批集裝箱時，第2班列承運方案(j=2)有2種，分別是承運第3批至第5批集裝箱(共8箱)、第3批至第6批集裝箱(共10箱)。以此進行推算，直至確定出各班列承運集裝箱的所有情況。如圖3所示，其中方案2-5-8-10的具體意義為：第1班列承運第1和第2批集裝箱，第2班列承運第3批至第5批集裝箱，第3班列承運第6批至第8批集裝箱，第4班列承運第9和第10批集裝箱，即這2批集裝箱未能運走剩余至下一時段。

圖3 搜索過程示意圖

考慮到集裝箱送達辦理站的時間和數量具有一定的隨機性，在嚴格遵循“先到先服務”原則下，也有可能不存在滿足約束的可行方案。對于這種情況，初始種群僅由隨機方案組成，不加入遵循“先到先服務”的方案。

3.2.3 染色體修復

3.2.4 遺傳算法流程

設計遺傳算法流程如下。

Step1：生成初始種群。

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

Step3：選擇操作。為避免優秀個體在交叉、變異中被破壞，采用輪盤賭與精英保留相結合的策略進行選擇。

Step4：交叉操作。在其中1個染色體中，隨機選取表示匹配關系的1個基因，將其與之后的所有表示匹配關系的基因與另一個染色體中相同位置的基因進行互換，修復不可行染色體。

Step5：變異操作。在執行變異操作的染色體中，任意選取1個表示匹配關系的基因，改變該基因的取值，修復不可行染色體。

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

4 求解算例

4.1 參數輸入

以膠州中鐵聯集青島集裝箱中心站開往黃島的集裝箱班列為例，采用本文提出的方法進行仿真計算。在所選擇1 d的時間段內，共有100批集裝箱陸續送達青島集裝箱中心站，相關數據見表3。班列最大編成箱數為50箱，最小編成箱數為40箱，根據式(1)可確定需組織開行10列集裝箱班列進行承運。辦理出發技術作業的時間為20 min，單個集裝箱平均裝車作業時間為2 min。

表3 集裝箱批次、數量及時間信息

4.2 求解結果

運用Matlab2014編程對算例進行測試，種群規模取100，交叉概率取0.95，變異概率取0.1，迭代次數為1 500次。計算過程中適應度函數值的變化如圖4所示，在運行了132 s后得到最終解，其適應度值為9.863 2×10-6,目標函數值為101 387 箱·min。由圖4可知，隨著迭代次數的增加，適應度函數值逐漸增加，在750次以后，適應度值已無明顯變化，表明算法的收斂性良好。本文還運用Gurobi對該算例進行了求解，運算到7 200 s時，仍未找到最優解。可見，對于大規模問題，遺傳算法能在較短時間內獲得優化解，在計算效率方面具有明顯的優勢。

圖4 適應度函數值變化

優化得到的各集裝箱班列始發時刻及承運集裝箱的批次和數量見表4。由表可知：第11行為虛擬班列，其承運的第99和第100批集裝箱，是當天未能運走的剩余集裝箱；部分集裝箱與班列的匹配不遵循“先到先服務”，例如，第15批集裝箱由第2列班列承運，而較早送達辦理站的第14批集裝箱由后出發的第3列班列承運。

比較表3和表4可知，集裝箱班列始發時刻與貨物需求的變化規律是吻合的。例如：在00:00至14:11之間，大量的集裝箱密集到達辦理站，共有70批，總箱數為340箱，則組織開行了7列班列承運這些集裝箱，即表4中的第1至第7列班列，顯然這部分班列承運的集裝箱數量基本達到最大編成箱數，且發車時間安排較為緊湊，相鄰班列出發間隔時間均不超過2 h；而在14:11之后，箱量減少，且集裝箱的平均到達間隔時間較大，相應的后續出發班列的間隔時間增大。

表4 基于需求相應的集裝箱班列始發時刻

表5 均衡發車模式下集裝箱班列始發時刻

以往研究在鋪畫列車運行線時，主要考慮列車出發的均衡性[15-16]。若采用均衡發車的模式，則算例中的青島集裝箱中心站每隔144 min(1 440÷10=144 min)組織發出1列開往黃島的集裝箱班列，從而可確定各班列的始發時刻，見表5。在此基礎上，運用Gurobi計算得出各班列承運集裝箱的批次，對應的集裝箱最小總停留時間為131 655 箱·min。比較表4與表5方案的集裝箱總停留時間，不難看出前者節省了30 268 箱·min。可見，利用本文模型及算法得到的集裝箱班列始發時刻與集裝箱貨物的數量、到達時間分布之間具有較好的匹配性，使集裝箱在辦理站停留時間最短，說明制定的班列開行計劃很好地響應了用戶需求。

5 結 語

為解決鐵路集裝箱辦理站發生的“貨物排隊”或“有線無車”問題，本文考慮了集裝箱貨物送達辦理站的時間和數量分布特征，闡述了集裝箱貨物與班列的匹配規律，以集裝箱貨物在集裝箱辦理站的總停留時間最小為優化目標，構建了集裝箱班列始發時刻優化的非線性混合整數規劃模型。根據模型特點，設計了基于遺傳算法的求解方法。通過算例測試，表明本文計算得到的集裝箱班列出發時刻很好地響應了用戶需求，可為鐵路企業優化集裝箱運輸組織提供決策參考。