基于需求響應(yīng)的鐵路集裝箱班列始發(fā)時刻優(yōu)化

江雨星，高翠香，牛惠民

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

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

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

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

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

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

本文將依據(jù)鐵路集裝箱貨物運輸需求，充分考慮集裝箱貨物與班列在時間和數(shù)量方面的匹配關(guān)系，構(gòu)建鐵路集裝箱班列始發(fā)時刻優(yōu)化的非線性混合整數(shù)規(guī)劃模型，結(jié)合模型特點，設(shè)計基于遺傳算法的求解方法，優(yōu)化基于需求響應(yīng)的鐵路集裝箱班列始發(fā)時刻。

1 問題描述及假設(shè)

以1個大型鐵路集裝箱辦理站為例，每天有大量的集裝箱貨物(以下簡稱為集裝箱)通過公路交通運送至該站，并在發(fā)送箱區(qū)進行集結(jié)，集結(jié)至要求的數(shù)量后，在集裝箱裝卸線上裝入開往目的站的集裝箱班列。對于這種運量大、貨源相對穩(wěn)定的集裝箱運輸問題，貨物需求主要體現(xiàn)在各批集裝箱送到辦理站的時間和數(shù)量?；诖?，本文優(yōu)化班列始發(fā)時刻的主要依據(jù)就是這些集裝箱送達辦理站的時間和數(shù)量，該信息可通過鐵路集裝箱運輸管理信息系統(tǒng)獲得。

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

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

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

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

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

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

2 優(yōu)化模型構(gòu)建

2.1 參數(shù)定義

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

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

(1)

2.2 優(yōu)化模型

1)約束條件

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

(2)

(2)集裝箱班列編成箱數(shù)約束：班列的編成箱數(shù)應(yīng)在[Nmin,Nmax]范圍內(nèi)。

(3)

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

q∈Q,j∈J{k}

(4)

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

j∈J{k-1,k}

(5)

2)始發(fā)時刻優(yōu)化模型

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

(6)

s.t.

式(2)—式(5)

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

3 算法設(shè)計

3.1 精確求解

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

表1 不同規(guī)模算例的Gurobi計算時間及優(yōu)化間隙

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

3.2 遺傳算法設(shè)計

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

3.2.1 染色體編碼

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

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

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

3.2.2 初始種群

1)隨機方案

j∈J{k}

(7)

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

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

表2 集裝箱批次、數(shù)量及時間信息

在滿足班列編成箱數(shù)的約束下，對于第1班列，承運集裝箱的方案共有3種，分別是承運第1和第2批集裝箱(共6箱)、第1批至第3批集裝箱(共8箱)、第1批至第4批集裝箱(共10箱)。采用最后1批集裝箱標號表示相應(yīng)的方案，則第1班列承運方案如圖3中的j=1所示。當(dāng)?shù)?班列承運第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 搜索過程示意圖

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

3.2.3 染色體修復(fù)

3.2.4 遺傳算法流程

設(shè)計遺傳算法流程如下。

Step1：生成初始種群。

Step2：令目標函數(shù)的倒數(shù)為適應(yīng)度函數(shù)，將當(dāng)前所有染色體帶入適應(yīng)度函數(shù)計算適應(yīng)度值。

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

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

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

Step6：判斷循環(huán)終止條件，若迭代次數(shù)沒有達到設(shè)定的最大循環(huán)次數(shù)，則轉(zhuǎn)Step2；否則算法結(jié)束，輸出結(jié)果。

4 求解算例

4.1 參數(shù)輸入

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

表3 集裝箱批次、數(shù)量及時間信息

4.2 求解結(jié)果

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

圖4 適應(yīng)度函數(shù)值變化

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

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

表4 基于需求相應(yīng)的集裝箱班列始發(fā)時刻

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

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

5 結(jié) 語

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