基于列生成算法的高速鐵路快捷貨運(yùn)組織方案優(yōu)化研究

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

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

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

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

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

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

1 高鐵快運(yùn)服務(wù)徑路優(yōu)化模型

1.1 問題描述

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

1.2 問題假設(shè)和已知

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

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

1.3 模型構(gòu)建

列車服務(wù)徑路優(yōu)化模型的目標(biāo)函數(shù)是列車運(yùn)營總成本最低，即

(1)

模型約束條件如下：

(1)區(qū)間通過能力約束

(2)

式中：Cjk為區(qū)段能力。

列車區(qū)間通過能力約束能夠有效降低對(duì)高速鐵路客運(yùn)業(yè)務(wù)的影響，滿足區(qū)間通過能力的限制。

(2)區(qū)間承載能力約束

(3)

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

(3)列車到達(dá)出發(fā)事件狀態(tài)約束

(4)

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

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

2.1 算法原理

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

2.2 算法流程

基于對(duì)列生成算法原理的分析可知，列生成算法的關(guān)鍵是構(gòu)造原問題的檢驗(yàn)數(shù)子問題，已知原問題為最小化問題，則當(dāng)檢驗(yàn)數(shù)子問題的最小值為非負(fù)數(shù)時(shí)，則原問題取到最優(yōu)解，列生成算法流程見圖1。

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

2.3 檢驗(yàn)數(shù)子問題模型構(gòu)建

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

檢驗(yàn)數(shù)子問題的目標(biāo)函數(shù)是原問題檢驗(yàn)數(shù)的最小值，即

(5)

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

模型約束如下：

(1)服務(wù)與起訖點(diǎn)關(guān)系約束

(6)

(7)

(8)

該組約束限定了列車i的起訖點(diǎn)與停站關(guān)系，即若列車i服務(wù)于OD對(duì)ω，則必須要在OD對(duì)ω的起訖點(diǎn)停站，反之成立。

(2)停站次數(shù)約束

(9)

式中：π為一個(gè)常數(shù)。

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

(3)列車起訖點(diǎn)約束

(10)

(11)

(12)

該組約束定義了列車起訖點(diǎn)與停站間的關(guān)系，即列車的起訖點(diǎn)唯一，且OD對(duì)ω的起訖點(diǎn)均需停站。

(4)徑路選擇約束

(13)

(14)

式中：M為一個(gè)無窮大正數(shù)。

該組約束定義了列車運(yùn)行徑路與OD對(duì)ω的關(guān)聯(lián)關(guān)系，即列車運(yùn)行的徑路不會(huì)超過所服務(wù)OD對(duì)的范圍，即OD范圍外的車站不允許停站，且起訖點(diǎn)所夾區(qū)間必為列車運(yùn)行徑路。

3 高鐵快運(yùn)貨流分配模型構(gòu)建

3.1 問題描述

第2節(jié)通過考慮列車與停站、區(qū)間與需求之間的關(guān)系確定了列車的服務(wù)徑路，生成了一個(gè)能夠滿足市場需求，包含列車運(yùn)行種類、停站組合的框架性開行方案，但具體貨運(yùn)需求與運(yùn)輸產(chǎn)品和組織模式的關(guān)系并未計(jì)算。本節(jié)基于目前推出的當(dāng)日達(dá)、次晨達(dá)、次日達(dá)和經(jīng)濟(jì)快遞4種運(yùn)輸產(chǎn)品，以及確認(rèn)車運(yùn)輸、捎帶運(yùn)輸、預(yù)留車廂以及高鐵貨運(yùn)列車專列4種組織模式細(xì)分市場需求，實(shí)現(xiàn)貨流的精準(zhǔn)分配。

3.2 問題的假設(shè)和已知條件

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

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

3.3 模型構(gòu)建

配流問題的目標(biāo)函數(shù)是高鐵快運(yùn)收益最大，即

(15)

模型約束如下：

(1)需求滿足約束

(16)

該約束保證鐵路組織方案能夠承載OD間不同運(yùn)輸產(chǎn)品的需求。

(2)產(chǎn)品供給特征約束

(17)

(18)

式中：η為列車滿載率。

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

(3)開行頻次約束

fi,m∈N?i∈Tm=4

(19)

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

4 算例分析

4.1 參數(shù)取值

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

本文開行方案中，高鐵快遞列車速度等級(jí)一致，列車種類i區(qū)別在于列車停站不同，可分為站站停、多站停、一站直達(dá)列車。列車停站方式應(yīng)根據(jù)貨源OD靈活安排。目前設(shè)計(jì)的高鐵快遞專列單列標(biāo)記載運(yùn)量為87 t。根據(jù)文獻(xiàn)[8]關(guān)于2025年高鐵快運(yùn)需求的預(yù)測(cè)，京滬間高鐵快遞日均OD量見表1。

根據(jù)文獻(xiàn)[13]關(guān)于高鐵快運(yùn)產(chǎn)品貨流分擔(dān)率的研究與實(shí)際統(tǒng)計(jì)相對(duì)比，可預(yù)測(cè)產(chǎn)品分擔(dān)率見表2。

表1 京滬間主要節(jié)點(diǎn)高鐵快運(yùn)需求 t

表2 高鐵快運(yùn)產(chǎn)品貨流分擔(dān)率 %

表3 京滬高鐵主要節(jié)點(diǎn)運(yùn)輸距離 km

4.2 列車備選集生成

本文用Python語言調(diào)用CPLEX12.7.1引擎編程實(shí)現(xiàn)列生成算法，算法運(yùn)行環(huán)境為一臺(tái)CPU為Intel Xeon E5520 2.27 GHz內(nèi)存2.8 GB的臺(tái)式計(jì)算機(jī)。

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

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

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

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

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

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

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

4.3 貨流分配方案

進(jìn)一步將運(yùn)輸需求與列車備選集輸入貨流分配模型，可得京滬主要節(jié)點(diǎn)間高鐵快運(yùn)產(chǎn)品運(yùn)輸模式?jīng)Q策方案，因OD需求與運(yùn)輸產(chǎn)品的組合較多，僅給出部分決策方案，見表4。

表4 高鐵快運(yùn)產(chǎn)品運(yùn)輸模式?jīng)Q策方案

由表4可知，4種運(yùn)輸產(chǎn)品與4種組織模式均有匹配，實(shí)現(xiàn)了貨流的精準(zhǔn)分配。從不同運(yùn)輸組織模式來看，充分發(fā)揮了確認(rèn)車與捎帶運(yùn)輸小批量、多批次的靈活特征，承擔(dān)了部分短運(yùn)距的貨運(yùn)需求，預(yù)留車廂和高鐵貨運(yùn)專列模式在中長距離中承擔(dān)了主要運(yùn)輸任務(wù)，發(fā)揮了大節(jié)點(diǎn)間開行的優(yōu)勢(shì)。

為進(jìn)一步分析貨運(yùn)動(dòng)車組裝載效率及對(duì)區(qū)間的利用情況，各區(qū)段斷面流量及具體列車剩余載運(yùn)能力見表5。

由表5可知，上下行貨流均被較好的分配在了相應(yīng)列車，大部分OD需求由同一列車滿足，該方案便于車站裝卸組織的集中進(jìn)行，能夠有效提升貨物組織效率。具體來看，上下行方向的1號(hào)列車均為“站站?！绷熊嚕軌蛴行M足沿途節(jié)點(diǎn)運(yùn)輸需求，下行方向8號(hào)列車與上行方向5號(hào)列車為“一直直達(dá)”或停站較少的列車，其裝載率較高，可以有效滿足OD間運(yùn)輸需求，并保證貨運(yùn)動(dòng)車組運(yùn)營收益。

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

表5 各區(qū)段斷面流量

5 結(jié)束語

基于備選集的兩階段高鐵快運(yùn)組織方案優(yōu)化模型可以有效實(shí)現(xiàn)成本與效益的平衡關(guān)系，確保不同層次市場需求有足夠能力的運(yùn)輸產(chǎn)品承載，設(shè)計(jì)的列生成算法可以實(shí)現(xiàn)備選集的快速生成，優(yōu)化方案有效降低了高鐵快運(yùn)運(yùn)營成本，表明上述方法能夠?yàn)楦哞F快運(yùn)業(yè)務(wù)提供科學(xué)決策支撐。