基于列生成算法的高速鐵路快捷貨運組織方案優化研究

金 偉，李夏苗，周凌云，于雪嶠

(1.中南大學 交通運輸工程學院，湖南 長沙 410075；2.中國鐵路北京局集團有限公司 貨運部，北京 100055；3.中國鐵道科學研究院集團有限公司 運輸及經濟研究所，北京 100081)

近年來，隨著城市規模和空間布局規劃的調整以及電商企業的快速發展，大城市的土地利用、交通擁堵及環境污染問題突顯，減少城市內公路貨運車輛，加快城市綠色物流體系建設勢在必行。高速鐵路(以下簡稱高鐵)快捷貨物運輸作為一種新型運輸產品，以其經濟、高效、穩定的優勢受到市場廣泛關注。高鐵貨運動車組下線運營，將進一步提升中長距離城市之間高鐵快運產品服務水平與效能。借鑒發達國家“外集內配”物流體系建設的先進經驗，充分結合我國市場需求與運輸結構特征，基于高鐵貨運列車高效、準時、運能大的優勢，充分發揮高鐵干線運輸能力及溢出效應，對減少公路貨運量、大氣環境污染，助力打贏“藍天保衛戰”具有重要的現實意義[1]。然而目前對高鐵貨物運輸組織方面的研究較少，如何平衡高鐵貨運動車組購置、運營成本與收入的關系，如何確保鐵路客運與貨運業務協同發展，以及如何充分利用高鐵時空資源成為高鐵貨運列車運輸組織的關鍵問題。

鐵路列車開行方案是鐵路運輸組織方案的基礎，其編制和優化是鐵路運輸組織領域的經典問題。國內外學者重點研究了組織方案的經濟性、時效性、服務水平、經營收益等與客戶需求的耦合關系，考慮不同場景下的發展目標構建了優化模型，并基于模型特征設計了求解算法。在模型構建方面，目前主要有考慮運營成本[2]與考慮旅客(貨物)出行(運輸)時間[3]兩種方法。在算法設計方面，受限于鐵路運輸多場景多網絡的復雜特征，既有應用精確求解算法的求解器僅能求解小規模算例，列生成算法適用于求解一類每個決策方案對應整體規劃模型中約束矩陣的一列的組合優化問題，因其不直接同時處理所有備選方案，而是基于當前生成的列的子集，通過限制原問題進行優化求解，提升了求解問題的能力，基于該思想，何必勝等[4]進一步優化了算法存在退化解和分支定界中缺乏有效上下解邊界導致求解效率較低的問題，設計了基于大規模領域搜索算法的混合列生成算法，有效避免了出現退化解的問題。許仲豪等[5]構造了一個僅包含一個乘務段的日計劃初始可行解，快速生成了滿足條件的乘務任務，且初始矩陣即為單位矩陣，初始可行解易于表達計算。對于復雜網絡的建模及計算則必須采取不同策略將原問題拆分，以降低問題及變量規模，如國外Carey等[6]、Castillo等[7]，國內周磊山等[8]、彭其淵等[9]都基于不同網絡與特征設計了基于問題分解的啟發式求解算法。

目前對于高鐵快運組織方案優化的研究相對較少，于雪嶠[10]設計了基于列車備選集的高鐵快運列車開行方案兩階段優化模型，以成本與收益關系為目標，考慮了網絡能力、需求耦合等約束，以哈大高鐵為例設計了高鐵快運列車方案。李蒞等[11]分析了貨運動車組開行的收益和成本問題，考慮了網絡能力、作業能力與運輸需求的平衡關系，構建了貨運動車組開行方案優化模型并設計了啟發式算法求解。吳優[12]分析了貨運動車組開行的可行性，借鑒鐵路旅客列車開行方案的設計思路，構建了滿足經濟效益、運輸能力及市場需求的多目標混合整數規劃模型，并提出了求解可行徑路集的K短路算法。以上研究均實現了高鐵快運組織方案的定量優化，但仍存在以下不足：均只考慮應用高鐵貨運動車組滿足市場需求，而未考慮現存的確認車、捎帶運輸、快運柜等組織模式，不符合實際運輸組織需求；僅考慮了運輸產品與貨流分配的關系，未考慮其與組織模式的相互關系，不利于指導生產實踐。

針對以上問題，本文考慮高鐵貨物快運需求、運力供給與運輸產品的匹配關系，設計基于列車備選集的兩階段組織方案優化模型，通過引入備選集的思想剔除明顯不符合高鐵貨運列車的服務徑路，再基于運輸產品及服務模式特征建立高鐵快運貨流分配優化模型，以及適應復雜網絡及大規模變量的列生成算法求解模型。

1 高鐵快運服務徑路優化模型

1.1 問題描述

高鐵快運服務徑路優化問題是一類求解規模巨大、變量組合繁多的時空資源優化配置問題，對于這一類組合優化問題，直接計算難以求得最優解，因此應在確定高鐵快運組織方案前首先剔除一些明顯不符合組織方案原則的情況，以降低配流階段的計算復雜性、降低問題規模，主要包括：某些方案沒有充分考慮網絡能力限制，部分繁忙區段運力資源緊張，沒有開行貨運列車的能力；沒有充分考慮列車與列車間的關系，導致在部分區段重復開行造成資源浪費；沒有考慮貨流與產品的耦合關系，導致區間虛糜過高等問題。為解決上述問題，首先應構造列車服務徑路優化模型，構造一個滿足貨運列車開行條件、經濟收益及貨流需求的服務網絡，即篩選出合理可行的列車服務徑路，再基于列車備選服務徑路在下一階段將其細分為服務產品與模式，實現貨流的精準分配。

1.2 問題假設和已知

假設列車在雙線鐵路網上運行，結合我國鐵路開行方案編制的實際，將車站看作網絡中的節點，高鐵快運業務開展的重要制約條件就是場站設施設備的不配套，隨著業務的拓展，鐵路也必將對場站設施進行新建或改造，以便于組織貨物裝卸、搬運、存儲，因此假設各經停車站都具有組織高鐵快遞各項業務的條件和足夠的能力，且目前貨運動車組參數與載客動車組參數相同，假設高鐵快運列車等級與客運列車等級相同，不考慮貨運動車組的車底運用問題。

模型的輸入為：列車開行的固定成本、與距離相關的可變成本、與列車起停相關的停站成本、區段能力、貨流需求及列車載運等。模型的輸出為優化后可滿足市場需求的列車可選服務徑路及組合停站模式。

1.3 模型構建

列車服務徑路優化模型的目標函數是列車運營總成本最低，即

(1)

模型約束條件如下：

(1)區間通過能力約束

(2)

式中：Cjk為區段能力。

列車區間通過能力約束能夠有效降低對高速鐵路客運業務的影響，滿足區間通過能力的限制。

(2)區間承載能力約束

(3)

貨物斷面流量的大小與列車裝載能力相關，即要求每一列車運行徑路的斷面中載貨量受列車額定裝載能力的限制，為此，設置該約束可以保證各個區間的貨運需求能夠有效被滿足。

(3)列車到達出發事件狀態約束

(4)

該約束保證了每一個OD對均有足夠承載能力的列車滿足。

2 基于列生成的模型求解算法

2.1 算法原理

從原問題與檢驗數子問題的現實意義來看，原問題中的每一“列”代表了不同停站模式的一列車，在求解檢驗數的迭代過程中，若當前存在的“列”不能有效滿足貨物運輸需求，則會“加列”，即增加另外一種新的停站模式的列車，隨著加入的“列”增多，列車的停站模式也不斷增加，直至無法加入新的列則表明沒有更優類型的停站組合模式，原問題即取得最優解。

2.2 算法流程

基于對列生成算法原理的分析可知，列生成算法的關鍵是構造原問題的檢驗數子問題，已知原問題為最小化問題，則當檢驗數子問題的最小值為非負數時，則原問題取到最優解，列生成算法流程見圖1。

圖1 列生成算法流程示意圖

2.3 檢驗數子問題模型構建

根據列生成算法的原理，出現在每一“列”位置上的變量均與列車和區間相關，因此每增加一“列”其實際含義為增加一列車。在原問題中，主要考慮的是列車與區段、需求間的耦合關系，及可考慮通過能力、載運能力等因素，而在檢驗數子問題中，則需具體考慮每一列車的停站、徑路、載運能力等因素。

檢驗數子問題的目標函數是原問題檢驗數的最小值，即

(5)

式中：α、β、γ分別為原問題中3種資源(式(2)、式(3)、式(4))的價值系數，故檢驗數子問題又可稱“定價子問題”。

模型約束如下：

(1)服務與起訖點關系約束

(6)

(7)

(8)

該組約束限定了列車i的起訖點與停站關系，即若列車i服務于OD對ω，則必須要在OD對ω的起訖點停站，反之成立。

(2)停站次數約束

(9)

式中：π為一個常數。

該約束有效限制了列車的停站次數，過多的停站會降低高鐵快運的時效性并占用更多的高鐵運輸能力資源。

(3)列車起訖點約束

(10)

(11)

(12)

該組約束定義了列車起訖點與停站間的關系，即列車的起訖點唯一，且OD對ω的起訖點均需停站。

(4)徑路選擇約束

(13)

(14)

式中：M為一個無窮大正數。

該組約束定義了列車運行徑路與OD對ω的關聯關系，即列車運行的徑路不會超過所服務OD對的范圍，即OD范圍外的車站不允許停站，且起訖點所夾區間必為列車運行徑路。

3 高鐵快運貨流分配模型構建

3.1 問題描述

第2節通過考慮列車與停站、區間與需求之間的關系確定了列車的服務徑路，生成了一個能夠滿足市場需求，包含列車運行種類、停站組合的框架性開行方案，但具體貨運需求與運輸產品和組織模式的關系并未計算。本節基于目前推出的當日達、次晨達、次日達和經濟快遞4種運輸產品，以及確認車運輸、捎帶運輸、預留車廂以及高鐵貨運列車專列4種組織模式細分市場需求，實現貨流的精準分配。

3.2 問題的假設和已知條件

在配流階段，假設每個OD對的區間均可滿足不同組織模式的作業要求，且具有所需設施設備；捎帶運輸與預留車廂模式因其基于客運列車時刻表組織運營，故假設其能夠滿足不同運輸產品對時效性的需要；各OD對需求區間調用上一階段求得的最優方案，且高鐵快運列車不與客運列車產生沖突。

模型的輸入為：高鐵快運收益與成本、高鐵快運市場需求；模型的輸出為優化后各運輸組織模式承載不同運輸產品的運量。

3.3 模型構建

配流問題的目標函數是高鐵快運收益最大，即

(15)

模型約束如下：

(1)需求滿足約束

(16)

該約束保證鐵路組織方案能夠承載OD間不同運輸產品的需求。

(2)產品供給特征約束

(17)

(18)

式中：η為列車滿載率。

該組約束考慮到產品供給特征，m=1表示服務模式為確認車，m=4表示服務模式為高鐵貨運列車，由于確認車開行時間為04:00天窗后，不能滿足當日達產品集貨需求，因此應用確認車模式不能服務與當日達產品；為保證高鐵快運列車收益，應滿足高鐵快運列車最低裝載率。

(3)開行頻次約束

fi,m∈N?i∈Tm=4

(19)

該約束保證列車的開行頻次為整數。

4 算例分析

4.1 參數取值

京滬高鐵是北京至上海的重要通道，全長1 318 km，連接了北京、天津和上海3個直轄市，經過4個省份，兩端連接京津冀和長三角兩個經濟區域，是中國社會經濟發展活躍的地區之一，也是中國客貨運輸較繁忙、增長潛力較大的客運專線。因此，以京滬高鐵為例，選取區間包括北京、天津、濟南、南京和上海6個重要城市，利用上文給出的兩階段模型，進行快運列車開行方案的設計。

本文開行方案中，高鐵快遞列車速度等級一致，列車種類i區別在于列車停站不同，可分為站站停、多站停、一站直達列車。列車停站方式應根據貨源OD靈活安排。目前設計的高鐵快遞專列單列標記載運量為87 t。根據文獻[8]關于2025年高鐵快運需求的預測，京滬間高鐵快遞日均OD量見表1。

根據文獻[13]關于高鐵快運產品貨流分擔率的研究與實際統計相對比，可預測產品分擔率見表2。

表1 京滬間主要節點高鐵快運需求 t

表2 高鐵快運產品貨流分擔率 %

表3 京滬高鐵主要節點運輸距離 km

4.2 列車備選集生成

本文用Python語言調用CPLEX12.7.1引擎編程實現列生成算法，算法運行環境為一臺CPU為Intel Xeon E5520 2.27 GHz內存2.8 GB的臺式計算機。

(1)上行方向列車備選集

上行方向共生成了8種停站類型的列車，其停站模式見圖2。

圖2 上行方向列車停站方案示意圖

(2)下行方向列車備選集

下行方向共生成了10種停站類型的列車，其停站模式見圖3。

圖3 下行方向列車停站方案示意圖

從圖2、圖3可知，列車對于運輸需求及停站的組合方式均有較好的側重，設置了多種停站類型、運行徑路的列車以滿足各地不同運輸需求。

4.3 貨流分配方案

進一步將運輸需求與列車備選集輸入貨流分配模型，可得京滬主要節點間高鐵快運產品運輸模式決策方案，因OD需求與運輸產品的組合較多，僅給出部分決策方案，見表4。

表4 高鐵快運產品運輸模式決策方案

由表4可知，4種運輸產品與4種組織模式均有匹配，實現了貨流的精準分配。從不同運輸組織模式來看，充分發揮了確認車與捎帶運輸小批量、多批次的靈活特征，承擔了部分短運距的貨運需求，預留車廂和高鐵貨運專列模式在中長距離中承擔了主要運輸任務，發揮了大節點間開行的優勢。

為進一步分析貨運動車組裝載效率及對區間的利用情況，各區段斷面流量及具體列車剩余載運能力見表5。

由表5可知，上下行貨流均被較好的分配在了相應列車，大部分OD需求由同一列車滿足，該方案便于車站裝卸組織的集中進行，能夠有效提升貨物組織效率。具體來看，上下行方向的1號列車均為“站站停”列車，能夠有效滿足沿途節點運輸需求，下行方向8號列車與上行方向5號列車為“一直直達”或停站較少的列車，其裝載率較高，可以有效滿足OD間運輸需求，并保證貨運動車組運營收益。

為直觀展示本文所構建的兩階段模型優勢，將第一階段智能生成列車備選集改為全枚舉法生成備選集和由人工經驗判斷給出的備選集，分別作為第二階段配流模型的輸入條件進行求解。研究結果表明：①在對全枚舉法生成的備選集進行配流時，由于問題規模變大，求解時間由原來的2 s變為13 min，配流方案與上文所述兩階段模型一致；②在對人工經驗判斷的備選集進行配流時，由于無法精準判斷合理備選集，貨流無法分配到最優備選集中，導致在部分方案中，因無法滿足貨流需求，增開了4列列車，相較上文方案增加了固定成本支出，在部分方案中因沒有合適的列車備選集，列車裝載率較差。

表5 各區段斷面流量

5 結束語

基于備選集的兩階段高鐵快運組織方案優化模型可以有效實現成本與效益的平衡關系，確保不同層次市場需求有足夠能力的運輸產品承載，設計的列生成算法可以實現備選集的快速生成，優化方案有效降低了高鐵快運運營成本，表明上述方法能夠為高鐵快運業務提供科學決策支撐。