鐵路快運班列開行方案與車底周轉一體化優化研究

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

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

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

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

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

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

1 “時間-空間-狀態”服務網絡的構建

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

圖1 鐵路物理網絡

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

相比于傳統動態服務網絡，此種網絡構建方式雖然在一定程度上擴大了網絡規模，但可實現貨物中轉、車底接續與班列停站的差異化表達，有助于清晰刻畫車底和貨物在時間和空間上的周轉過程。

圖2 “時間-空間-狀態”服務網絡示意圖

2 鐵路快運班列開行方案與車底周轉一體化優化模型

2.1 模型假設

(1)能力假設。不考慮線路的區間通過能力瓶頸；各車站的作業能力能夠滿足班列到發、貨物裝卸、中轉和車底接續的作業要求。

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

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

2.2 符號定義

(1)集合與元素

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

(2)參數

(3)決策變量

2.3 模型構建

以最大化鐵路部門運營收益為優化目標，模型目標函數為

(1)

s.t.

(2)

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

(3)

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

(4)

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

(5)

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

(6)

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

(7)

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

(8)

(9)

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

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

3 基于拉格朗日松弛的啟發式算法

3.1 拉格朗日對偶問題的構造

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

(10)

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

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

(11)

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

L(D)=maxL(ρ,σ)

s.t.

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

(12)

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

3.2 獲得可行解的啟發式算法

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

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

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

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

Step3車底周轉的可行化。將服務網絡中已被指派車底的弧段剔除；更新車輛流m的最小費用徑路，轉至Step2。

Step4確定貨流規劃優先級。對?f∈F，其規劃優先級系數ψf為

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

(13)

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

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

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

Step6貨流分配的可行化。將服務網絡中Ccap

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

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

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

(14)

(15)

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

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

3.4 算法流程

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

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

Step6終止條件檢驗。如果迭代次數k大于預設的最大迭代次數則算法終止；否則k=k+1，轉至Step2。

4 算例分析

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

圖3 鐵路路網拓撲結構

(1)貨流數據見表1。

表1 貨流信息

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

(2)車底數據見表2。

表2 車底信息

車底的起訖節點按照其始發站抽象為服務網絡中的虛擬節點。車底的最小接續時間設定為4 h。

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

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

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

表3 其他參數取值

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

表4 班列開行方案

表5 車底周轉計劃

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

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

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

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

5 結論

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