鐵路快運班列開行方案與車底周轉(zhuǎn)一體化優(yōu)化研究

李新毅，李海鷹，王 瑩，廖正文,，苗建瑞

(1.北京交通大學 交通運輸學院,北京 100044; 2.中國鐵路設(shè)計集團有限公司 線路站場樞紐設(shè)計研究院，天津 300308；3.北京交通大學 軌道交通控制與安全國家重點實驗室,北京 100044)

鐵路快運班列是在固定發(fā)到站間，有固定運行線和確定運行周期的一種貨運產(chǎn)品，服務(wù)對象以高時效、小批量的快捷運輸需求為主。隨著鐵路市場化進程的加快與既有線運能的釋放，鐵路部門采取直達、中轉(zhuǎn)、循環(huán)等相結(jié)合的班列組織方式，以有效利用運輸能力，提高班列服務(wù)水平。差異化的開行模式，使得運輸組織工作日趨復(fù)雜。此外，車底是班列開行方案兌現(xiàn)質(zhì)量的保障，而貨運的快速化需求對列車提出了運行高速化和裝卸便捷化的要求，導(dǎo)致可供運用的車底資源呈現(xiàn)出緊缺狀態(tài)。如何同步實現(xiàn)開行方案的合理編制與車底資源的高效周轉(zhuǎn)，成為值得研究的問題。

班列開行方案是在盡可能滿足貨物運輸需求的基礎(chǔ)上，科學合理地安排班列的起訖站點、運行徑路、編組內(nèi)容、開行頻率等，實現(xiàn)從貨流到車流再到列流的組織方案[1]。班列的車底周轉(zhuǎn)計劃則用于指派各車底承擔相應(yīng)的班列運行任務(wù)，以實現(xiàn)車底的合理循環(huán)運用。專家學者對以上兩個問題進行了深入研究，在優(yōu)化班列開行方案時，或考慮不同因素直接構(gòu)建優(yōu)化模型[2-4]或基于服務(wù)網(wǎng)絡(luò)構(gòu)建網(wǎng)絡(luò)流模型[5-7]；對于車底周轉(zhuǎn)計劃的優(yōu)化，主要將問題抽象為旅行商問題和指派問題[8-10]。上述研究通常將開行方案與車底周轉(zhuǎn)兩個問題割裂考慮，打破了頂層計劃與底層資源的關(guān)聯(lián)，使得優(yōu)化結(jié)果具有局限性。班列開行方案是通過匹配貨物運輸需求與鐵路運力資源，實現(xiàn)“組流上線”的運輸計劃，其計劃質(zhì)量決定運營收入，車底周轉(zhuǎn)計劃則是在開行方案的基本框架下，給出移動運力資源在時間和空間上的配置方案，該方案決定開行方案的兌現(xiàn)成本。如果能夠在決策階段考慮二者的一體化優(yōu)化，既可以實現(xiàn)鐵路部門降本增效，又可以保障班列的順暢組織，同時其優(yōu)化結(jié)果可為確定班列運行線提供有效參考。

近年來，也有學者利用服務(wù)網(wǎng)絡(luò)設(shè)計方法對上述兩個問題的一體化優(yōu)化展開了研究，通過將時間維度引入服務(wù)網(wǎng)絡(luò)來刻畫車底的周轉(zhuǎn)運用，使原問題轉(zhuǎn)化為一類網(wǎng)絡(luò)設(shè)計問題[11-15]。文獻[11-12]研究了考慮多資源周轉(zhuǎn)的開行方案優(yōu)化問題，分別構(gòu)建了點-弧和弧-路網(wǎng)絡(luò)流模型，目標是最小化貨物運輸成本。文獻[13]在文獻[11-12]的基礎(chǔ)上，提出一種分支-定價的求解框架，提高了模型的求解效率。文獻[14]將原問題拆分為服務(wù)網(wǎng)絡(luò)構(gòu)建、貨物流量分配、車輛運用安排3個階段，并設(shè)計了面向大規(guī)模案例的求解算法。文獻[15]對考慮車輛周轉(zhuǎn)的鐵路動態(tài)貨運服務(wù)網(wǎng)絡(luò)設(shè)計問題進行研究，構(gòu)建了基于路徑的多商品網(wǎng)絡(luò)流模型，并給出一種分支-定價-切割的求解算法。但是既有研究往往為降低求解難度而增大時間離散精度，不利于對車底接續(xù)、貨流中轉(zhuǎn)等作業(yè)環(huán)節(jié)的刻畫，優(yōu)化結(jié)果難以應(yīng)用于實際。

本文針對班列開行方案與車底周轉(zhuǎn)一體化優(yōu)化問題，引入“運輸狀態(tài)”維度，建立“時間-空間-狀態(tài)”服務(wù)網(wǎng)絡(luò)，將原問題轉(zhuǎn)化為考慮車底周轉(zhuǎn)的服務(wù)網(wǎng)絡(luò)設(shè)計問題。貨物的運輸過程和車底的運用安排可看作貨物與車底在服務(wù)網(wǎng)絡(luò)中的流動過程，即所謂貨流和車輛流，車底資源與貨運需求以服務(wù)網(wǎng)絡(luò)為媒介實現(xiàn)供給與需求的匹配。基于此構(gòu)建0-1整數(shù)規(guī)劃優(yōu)化模型，設(shè)計基于拉格朗日松弛算法的快速求解框架，并通過算例對模型和算法的求解效率和優(yōu)化質(zhì)量進行驗證。

1 “時間-空間-狀態(tài)”服務(wù)網(wǎng)絡(luò)的構(gòu)建

考慮圖1所示的鐵路物理網(wǎng)絡(luò)。將車站抽象為車站節(jié)點，在時間軸上將車站節(jié)點按照單位時段拓展離散，在空間軸上將車站節(jié)點進一步拆分為到達節(jié)點和出發(fā)節(jié)點。引入“運輸狀態(tài)”維度L={l1,l2，…，lmax}，L中元素為為貨物和車底的“運輸狀態(tài)”。對于貨物而言，運輸狀態(tài)是指貨物當前所裝載的班列；對于車底而言，運輸狀態(tài)是指車底當前所擔當?shù)陌嗔小；诖藰?gòu)建“時間-空間-狀態(tài)”服務(wù)網(wǎng)絡(luò)G=(N,A)，其中：N為節(jié)點集合；Na、Nd分別為車站的到達節(jié)點和出發(fā)節(jié)點集合，表示班列的到發(fā)作業(yè)，Na、Nd∈N；Nv為虛擬節(jié)點集合，表示貨流和車輛流在網(wǎng)絡(luò)中的邏輯起點與終點，Nv∈N；A為節(jié)點間的有向弧集合，包括運行弧集合As∈A、停站弧集合Ae∈A、中轉(zhuǎn)弧集合At∈A、接續(xù)弧集合Ac∈A和虛擬弧集合Av∈A，其中，運行弧和停站弧是班列的組成部分，分別表示班列的區(qū)間運行過程和停站作業(yè)過程，中轉(zhuǎn)弧和接續(xù)弧穿插于不同的運輸狀態(tài)維度，通過運輸狀態(tài)的變化表示貨物在班列間的中轉(zhuǎn)過程和車底在班列間的接續(xù)過程，虛擬弧無實際含義，僅用于描述貨流和車輛流在網(wǎng)絡(luò)中的生成與消失。

圖1 鐵路物理網(wǎng)絡(luò)

在構(gòu)建時空狀態(tài)服務(wù)網(wǎng)絡(luò)時，根據(jù)貨流的出發(fā)時間窗和貨物的運到時限給出貨物的到達時間窗，然后生成所有符合時間窗約束的虛擬弧，并根據(jù)貨流的最小中轉(zhuǎn)時間生成所有符合中轉(zhuǎn)時間約束的中轉(zhuǎn)弧，從而保證服務(wù)網(wǎng)絡(luò)中所有可能被選擇的服務(wù)路徑均滿足上述關(guān)于時效性的約束。圖2為時空狀態(tài)服務(wù)網(wǎng)絡(luò)的示意圖，圖中，一支發(fā)到站分別為TA站和TD站的貨流，首先在班列l(wèi)1的運行弧集合中選擇一條弧段，實現(xiàn)由TA至TB的站間運輸，然后經(jīng)由合適的中轉(zhuǎn)弧進行運輸狀態(tài)的轉(zhuǎn)換，從而實現(xiàn)貨流從班列l(wèi)1中轉(zhuǎn)至班列l(wèi)2，貨流從TB站至TD站的運輸作業(yè)將由班列l(wèi)2完成，通過班列l(wèi)1、l2及一次貨流中轉(zhuǎn)，實現(xiàn)從TA站至TD站的運輸。類似的，通過對運行弧、停站弧和接續(xù)弧進行選擇組合也可刻畫車輛流的周轉(zhuǎn)過程。在上述貨流和車輛流的流動過程中，車輛流是弧段運輸能力的供給方，而貨流則是弧段運輸能力的消耗方，通過約束貨流與車輛流在服務(wù)網(wǎng)絡(luò)中的時空一致性，得到車底資源與貨運需求的供需匹配結(jié)果，即獲得班列的出發(fā)和到達時刻、運行徑路、貨流的分配方案以及車底的接續(xù)方案等信息，從而確定班列開行方案和車底周轉(zhuǎn)計劃。

相比于傳統(tǒng)動態(tài)服務(wù)網(wǎng)絡(luò)，此種網(wǎng)絡(luò)構(gòu)建方式雖然在一定程度上擴大了網(wǎng)絡(luò)規(guī)模，但可實現(xiàn)貨物中轉(zhuǎn)、車底接續(xù)與班列停站的差異化表達，有助于清晰刻畫車底和貨物在時間和空間上的周轉(zhuǎn)過程。

圖2 “時間-空間-狀態(tài)”服務(wù)網(wǎng)絡(luò)示意圖

2 鐵路快運班列開行方案與車底周轉(zhuǎn)一體化優(yōu)化模型

2.1 模型假設(shè)

(1)能力假設(shè)。不考慮線路的區(qū)間通過能力瓶頸；各車站的作業(yè)能力能夠滿足班列到發(fā)、貨物裝卸、中轉(zhuǎn)和車底接續(xù)的作業(yè)要求。

(2)貨運需求不固定。班列是否開行取決于運輸收益，滿足貨運需求僅作為軟約束，對未能通過班列運輸?shù)呢浟?，可由普通列車運輸完成。

(3)車底固定編組、固定區(qū)段運行。班列運行中無車輛甩掛、解編作業(yè)，貨物裝卸依靠集裝化器具和快速化機械設(shè)備完成。

2.2 符號定義

(1)集合與元素

V為車輛流(車底)集合，v∈V；ov、dv分別為車輛流v的始發(fā)、終到節(jié)點，ov、dv∈Nv；Tv為車底v的編成輛數(shù)(車輛流流量)。

(2)參數(shù)

(3)決策變量

2.3 模型構(gòu)建

以最大化鐵路部門運營收益為優(yōu)化目標，模型目標函數(shù)為

(1)

s.t.

(2)

式(2)為貨流流量約束，該約束保證被服務(wù)的流量之和小于等于總的貨流流量。按照模型假設(shè)(2)的描述，約束取小于等于而非等于。

(3)

式(3)為貨流的流平衡約束，貨流是否分配至弧段a∈A以0-1變量的形式體現(xiàn)，從而確保各支貨流在唯一空間路徑上不可拆分。

(4)

式(4)為車輛流的流平衡約束，車輛流是否流經(jīng)弧段a∈A以0-1變量的形式體現(xiàn)，從而確保車輛流在唯一空間路徑上不可解編。

(5)

式(5)為車底運用數(shù)量約束，表示投入運用的車底數(shù)量必須小于或等于可供運用的車底數(shù)量。

(6)

式(6)為車底指派約束，該約束保證任一班列任務(wù)僅與唯一車底存在指派關(guān)系。

(7)

式(7)為弧段運輸能力約束，該約束體現(xiàn)了車底與貨流的供需關(guān)系，即車底為弧段提供的運輸能力須大于其上貨流流量。

(8)

(9)

式(8)、式(9)表示決策變量的取值范圍約束。

上述模型為0-1整數(shù)規(guī)劃模型，模型約束和決策變量規(guī)模與時空狀態(tài)網(wǎng)絡(luò)的弧段規(guī)模相對應(yīng)。動態(tài)服務(wù)網(wǎng)絡(luò)經(jīng)過時空維度的節(jié)點離散后，弧段規(guī)模較大，使用商用優(yōu)化求解器難以在可接受時間內(nèi)獲取最優(yōu)解，而本文在動態(tài)服務(wù)網(wǎng)絡(luò)的基礎(chǔ)上又進行了狀態(tài)維度的拓展，模型的求解難度更高，故給出基于拉格朗日松弛的求解算法，通過松弛強耦合約束，使原問題分解為貨流分配和車底周轉(zhuǎn)兩類結(jié)構(gòu)簡單的子問題，實現(xiàn)大規(guī)模問題的分而治之。

3 基于拉格朗日松弛的啟發(fā)式算法

3.1 拉格朗日對偶問題的構(gòu)造

本文優(yōu)化模型求解的困難之處在于貨流分配和車底周轉(zhuǎn)之間的強耦合性。因此在采用拉格朗日松弛算法時，我們將弧段運輸能力約束(式(7))和車底指派約束(式(6))松弛，在目標函數(shù)中引入拉格朗日乘子懲罰項，構(gòu)造拉格朗日松弛問題，為

(10)

式中：ρa、σa為拉格朗日乘子。

式(10)為利潤最大化問題可進一步等價變換為成本最小化問題即

(11)

式(11)中L(ρ,σ)的目標值對應(yīng)模型的下界值，為獲取模型的最大下界，我們構(gòu)造拉格朗日對偶問題L(D)，目標函數(shù)為

L(D)=maxL(ρ,σ)

s.t.

式(2)～式(5)、式(8)、式(9)

(12)

拉格朗日對偶問題通過在松弛約束中添加新的變量(拉格朗日乘子)，使得兩類子問題的耦合關(guān)系打開，因此新的整數(shù)問題分解為一類經(jīng)典的運籌學優(yōu)化問題——最小費用路徑問題。通過逐一構(gòu)建符合貨流和車輛流約束條件的服務(wù)網(wǎng)絡(luò)，即可借助最短路算法快速求得對偶問題的可行解。

3.2 獲得可行解的啟發(fā)式算法

由于部分約束被松弛，因此求解拉格朗日對偶問題得到的下界解可能為非可行解，需要針對該問題設(shè)計啟發(fā)式算法。該算法將下界中的車輛流和貨流在服務(wù)網(wǎng)絡(luò)中的路徑信息作為啟發(fā)信息，按照一定的順序逐一規(guī)劃各車輛流和貨流，從而求得可行解。

m、n分別為車輛流和貨流編號，弧段運輸能力為Ccap。基于松弛問題解得到可行解的步驟如下：

Step1初始化。令m=0，n=0，對?a∈A，令Ccap=0。

Step2加載車輛流。令m=m+1，若m>R，進入Step4；提取下界解中第m支車輛流的周轉(zhuǎn)路徑，遍歷路徑中弧段的車底占用標記，若已被占用，轉(zhuǎn)至Step3，否則令弧段Ccap=Tm(Tm為車輛流m的流量大小)，繼續(xù)Step2。

Step3車底周轉(zhuǎn)的可行化。將服務(wù)網(wǎng)絡(luò)中已被指派車底的弧段剔除；更新車輛流m的最小費用徑路，轉(zhuǎn)至Step2。

Step4確定貨流規(guī)劃優(yōu)先級。對?f∈F，其規(guī)劃優(yōu)先級系數(shù)ψf為

μ+ω=1μ,ω∈[0,1]

(13)

式中：Hf為貨流f∈F的路徑費用。

取μ=0.2，ω=0.8，ψf值越大表明服務(wù)該貨流的收益越高。

Step5加載貨流。按照ψf由大至小順序更新貨流編號n。令n=n+1，若n>P(P為待服務(wù)貨流數(shù)量)，進入Step7；加載第n支貨流至服務(wù)網(wǎng)絡(luò)。遍歷貨流路徑中弧段，若存在弧段其Ccap

Step6貨流分配的可行化。將服務(wù)網(wǎng)絡(luò)中Ccap

Step7保存可行解，計算原問題上界，算法結(jié)束。

3.3 拉格朗日乘子的更新方法

在給定的拉格朗日乘子下，我們可以獲得拉格朗日對偶問題的一個下界解，在求解時，通過對拉格朗日乘子值進行迭代更新，使下界解逐步逼近最優(yōu)解。拉格朗日乘子的次梯度更新方法為

(14)

(15)

式中：k為迭代次數(shù)；δ為迭代步長，δk=1/k+1。

式(14)、式(15)中，拉格朗日乘子ρa是當供需不平衡時產(chǎn)生的“懲罰費用”，反映了弧段運輸能力與其上貨流流量的適應(yīng)程度，而σa可以理解為弧段這一時空資源的“占用價格”，即車輛流占用弧段的代價。次梯度法是根據(jù)車輛流和貨流的弧段占用信息，對“懲罰費用”與“占用價格”迭代更新，實現(xiàn)弧段資源的動態(tài)定價，繼而影響貨流與車輛流在下次迭代中的路徑選擇。通過對“資源定價”與“路徑選擇”過程的反復(fù)迭代[16]，最終得到貨流需求與車底資源的最佳時空映射關(guān)系。

3.4 算法流程

Step2拉格朗日對偶子問題的求解。

Step5以3.3節(jié)所述方法更新拉格朗日乘子ρa、σa。

Step6終止條件檢驗。如果迭代次數(shù)k大于預(yù)設(shè)的最大迭代次數(shù)則算法終止；否則k=k+1，轉(zhuǎn)至Step2。

4 算例分析

以包含8座車站的鐵路路網(wǎng)作為算例對模型和算法進行驗證，見圖3。用C#語言編寫拉格朗日松弛啟發(fā)式算法的計算程序，程序運行環(huán)境為Intel(R)Core(TM)i5-3470 3.2 GHz，4.00 GB內(nèi)存的臺式計算機。在該算例中，以3 d作為決策周期，時空狀態(tài)服務(wù)網(wǎng)絡(luò)時間離散化的精度設(shè)為1 h，站間距離以區(qū)間運行時間的形式表示，均為單位時間長度的整數(shù)倍，并在圖中進行了標注。

圖3 鐵路路網(wǎng)拓撲結(jié)構(gòu)

(1)貨流數(shù)據(jù)見表1。

表1 貨流信息

關(guān)于貨流的到發(fā)時間窗，本文在考慮貨物的運到時限的同時，還結(jié)合了貨主的接取送達時間以給出更符合實際的到發(fā)時間窗。由于時空狀態(tài)服務(wù)網(wǎng)絡(luò)中包含時間屬性，因此在網(wǎng)絡(luò)構(gòu)建時，可根據(jù)貨流的到發(fā)時間窗生成可能的虛擬弧段，貨流的出發(fā)和到達作業(yè)均通過訪問以上虛擬弧段實現(xiàn)，從而既保證貨物的運到時限又滿足貨主在接取送達時間上的要求。貨流的最小中轉(zhuǎn)時間設(shè)定為2 h，以保證車站運輸組織工作順利進行。

(2)車底數(shù)據(jù)見表2。

表2 車底信息

車底的起訖節(jié)點按照其始發(fā)站抽象為服務(wù)網(wǎng)絡(luò)中的虛擬節(jié)點。車底的最小接續(xù)時間設(shè)定為4 h。

在本算例中，貨流和車輛流通過運行弧和停站弧的價格均為固定的時間成本(1元/(車·h))，中轉(zhuǎn)弧價格為50元/車。此外，不考慮虛擬弧、停站弧和中轉(zhuǎn)弧的能力限制。

(3)班列備選集數(shù)據(jù)。由于服務(wù)網(wǎng)絡(luò)引入了狀態(tài)維度，因此須事先給出班列的可選集合。在本算例中，不考慮各運輸區(qū)段的通過能力，貨流均可通過最短路徑滿足運輸需求，因此班列備選集通過最短路算法給出。具體方法是，在圖3所示的鐵路物理網(wǎng)絡(luò)中，以每一個貨流OD需求為輸入，借助最短路算法生成各OD對之間的運行徑路。在此基礎(chǔ)上，遵循車底周轉(zhuǎn)循環(huán)的原則確定班列的運行徑路，并以此作為班列的備選集。

(4)其他參數(shù)。貨流的運輸成本與收入在貨流由起點出發(fā)訪問相應(yīng)虛擬弧時產(chǎn)生，即貨流被服務(wù)則產(chǎn)生以上收益；與班列開行相關(guān)的線路使用費和開行成本等在車輛流訪問相應(yīng)虛擬弧和接續(xù)弧時產(chǎn)生，即車底選擇執(zhí)行班列任務(wù)時需付出以上費用。其他參數(shù)取值見表3。

表3 其他參數(shù)取值

利用拉格朗日松弛算法進行300次迭代，對上述算例進行測算，總耗時81.5 s，最優(yōu)目標函數(shù)值為2 428 651.36元。班列開行方案和車底周轉(zhuǎn)計劃見表4、表5。

表4 班列開行方案

表5 車底周轉(zhuǎn)計劃

由表4可知，優(yōu)化方案開行班列總數(shù)為11，其中有6列為一站直達班列，在剩余5列停站班列中有兩列班列間存在貨流的中轉(zhuǎn)關(guān)系(班列6與班列10)。在上述班列中，執(zhí)行班列3、4、5運輸任務(wù)的車底為同一車底(見表5“擔當班列”)，可組合為循環(huán)班列，剩余8對班列組成往返對開班列。在20支貨流中，貨流7和貨流15未被運輸，這說明服務(wù)上述小股貨流將出現(xiàn)返程班列回空現(xiàn)象，導(dǎo)致運營虧損，因此予以舍棄。

由表5可知，在決策周期內(nèi)，各車底的起訖車站相同，表明車底以固定區(qū)段的方式循環(huán)周轉(zhuǎn)。算例共使用5組車底，兩組車底未被運用，原因是車底空車走行的成本高，而剩余小股貨流不足以組織對開班列。

在上述算例中，如果設(shè)定僅可開行直達班列，經(jīng)算法測試，最優(yōu)目標函數(shù)值降低為1 984 161.52元。班列總數(shù)依然為11列，但未被運輸貨流數(shù)量變?yōu)?支，多為小批量貨流，分別為貨流3、4、7、10、13、14、15、16、18，這表明本文優(yōu)化方法可以根據(jù)貨流特點，通過組織開行適當數(shù)量的停站班列，以有效吸引小股貨流，實現(xiàn)鐵路運營收益的最大化；考慮到中轉(zhuǎn)班列的作業(yè)復(fù)雜，如果假設(shè)按照直達和停站班列結(jié)合的模式組織運輸，不開行中轉(zhuǎn)班列，則共開行班列11列，貨流10(H—E)未被運輸，目標函數(shù)值降低為2 358 196.56元。

進一步地，維持原有算例的數(shù)據(jù)集不變，減少可供運用的車底數(shù)量，保留車底1、2、3、6，班列開行總數(shù)變?yōu)?列，車底6的擔當班列變?yōu)榘嗔?(A—G)和班列9(G—A)，班列10(A—E)和班列11(E—A)停開，共有7支貨流未被運輸，最優(yōu)目標函數(shù)值降低為2 127 834.32元。

5 結(jié)論

本文研究了鐵路快運班列開行方案與車底周轉(zhuǎn)的一體化優(yōu)化問題，為實現(xiàn)貨物運輸與車底周轉(zhuǎn)過程的清晰表達，在傳統(tǒng)動態(tài)服務(wù)網(wǎng)絡(luò)中引入運輸狀態(tài)維度，構(gòu)建了“時間-空間-狀態(tài)”服務(wù)網(wǎng)絡(luò)，并據(jù)此構(gòu)建了考慮貨流中轉(zhuǎn)和車底接續(xù)的網(wǎng)絡(luò)流模型。文中給出一種基于拉格朗日松弛的啟發(fā)式求解算法，在相同算例數(shù)據(jù)集下的靈敏度分析驗證了模型與算法的有效性。結(jié)果表明，本文提出的優(yōu)化方法不僅可以基于貨流特點與組織方式給出收益最佳的班列開行方案，還可以實現(xiàn)班列開行方案和車底周轉(zhuǎn)計劃在不同車底資源配置場景下的一體化優(yōu)化調(diào)整。在算例求解時，班列開行備選集的完備性與合理性對優(yōu)化結(jié)果有一定影響，對于班列備選集的生成策略尚待進一步完善。