鄭可心 宋 瑞 李光曄

（北京交通大學綜合交通運輸大數(shù)據(jù)應用技術交通運輸行業(yè)重點實驗室 北京100044）

0 引 言

鐵路貨運“實貨制”改革[1]以后，對鐵路貨運服務質量、信息化管理水平等提出了新的要求，向鐵路貨運實現(xiàn)市場化邁進了關鍵一步。鐵路空車資源的優(yōu)化配置，有利于降低運輸成本、加快車輛周轉，是提升鐵路貨運服務質量和競爭力的一項重要內容。

現(xiàn)階段關于空車資源優(yōu)化配置的國內外主要研究可分為靜態(tài)空車調配、確定性動態(tài)空車調配[2-3]和隨機空車調配3個方面。相關研究將空車調配問題視為運輸問題、車間調度問題、庫存問題和多商品網(wǎng)絡流問題[4]等，并在此基礎上引入了車種代用[5-6]、空重車流協(xié)同優(yōu)化[7]等多個角度的研究。鐵路空車調配問題最早的研究均為靜態(tài)空車調配問題，由于缺乏對時間維度的考慮，研究得到的空車調配策略不夠靈活，不能適應鐵路實際生產(chǎn)。程學慶[8]用模糊綜合評判方法對鐵路運輸應急物資的優(yōu)先權進行了計算，結合車種代用構建了考慮應急物資優(yōu)先權的多目標空車調配模型。陳軍華等[9]將企業(yè)鐵路煤運通道空重車流的協(xié)同優(yōu)化問題視為多重指派問題，建立了企業(yè)鐵路煤運通道空重車流調配優(yōu)化模型。薛鋒等[10]提出運用D-W分解算法求解靜態(tài)空車調整模型，并證明了其時間算法復雜度的優(yōu)越性。確定性動態(tài)空車調配問題是指一定的周期內，在空車供需情況確定、路網(wǎng)條件不變的情況下，空車調配決策應隨時間推移而變化。Holmberg等[4]研究了瑞典國家鐵路的空車調配問題，將空車調配問題視為多商品網(wǎng)絡流問題，以滿足客戶需求和總費用最小為目標，并將通過能力約束、車種代用和列車時刻表等綜合考慮設計優(yōu)化模型。M.F.Gorman等[11]介紹了美國CSX公司開發(fā)動態(tài)車輛調配優(yōu)化系統(tǒng)（DCP），系統(tǒng)每隔15 min對管轄的2.1萬路網(wǎng)中全部空車進行動態(tài)配空，DCP系統(tǒng)每年為公司節(jié)省超過5 100萬美元，在實際應用中產(chǎn)生巨大的經(jīng)濟效益。王龍等[12]運用時空網(wǎng)絡技術，構建全路同構支點路網(wǎng)空車動態(tài)調配優(yōu)化模型，并提出1種基于混沌思想的粒子群算法對大規(guī)模路網(wǎng)空車動態(tài)調配問題進行求解，還通過模型計算結果設計了路網(wǎng)分界口排空流量測算方法。Jing等[13]提出了1種量子衍生免疫克隆算法求解動態(tài)空車調配問題。隨機規(guī)劃理論也被運用到空車調配問題。雷中林等[14]構建了1種特殊的隨機機會約束模型來求解鐵路空車調配問題，并設計了遺傳算法求解模型。鄒華鵬[15]采用不確定規(guī)劃中的機會約束優(yōu)化理論分別對車流波動和供需波動2種情況下的空車調配問題構建了車流運送的優(yōu)化模型。綜上，空車調配的動態(tài)性問題一直是國內外學者研究中關注的重點問題。而我國鐵路由于長期沿用計劃模式，弱化了空車調配的動態(tài)性[16]。在現(xiàn)有空車調整模式下，我國鐵路空車調配難以實現(xiàn)全路網(wǎng)動態(tài)優(yōu)化，但是路局公司（以下簡稱路局）管內的空車調配動態(tài)優(yōu)化問題是值得思考的[17]。通過構建時空網(wǎng)絡的方法，將空車調配問題建模為多商品網(wǎng)絡流問題，能夠直觀表達空車調配隨時間變化的過程，對我國鐵路局管內空車調配動態(tài)優(yōu)化問題具有指導意義。

針對路局管內動態(tài)空車調配問題，對既有時空網(wǎng)絡構建方法進行改進，將空車調配問題視為多商品網(wǎng)絡流問題，并在此基礎上引入車種代用的考慮，構建了基于時空網(wǎng)絡的鐵路空車調配動態(tài)優(yōu)化模型，為路局內部日?？哲囌{配方案提供依據(jù)。

1 時空網(wǎng)絡的構建

既有采用時空網(wǎng)絡技術解決動態(tài)空車調配問題的相關研究，將時空網(wǎng)絡分為離散型時空網(wǎng)絡和連續(xù)型時空網(wǎng)絡，為了降低網(wǎng)絡復雜度，往往選擇離散型時空網(wǎng)絡的方法，將時空網(wǎng)絡中的時段以相等的時間間隔進行劃分，取2～3 h為1個時間階段[18]。但是這種劃分方法存在描述問題的精確度不夠的缺點，為此筆者對時段劃分方法進行了改進，在既有離散型時空網(wǎng)絡的基礎上，將時空網(wǎng)絡中的時間段分為緊張時段、正常時段和空閑時段，以精確描述作業(yè)能力的變化，同時降低網(wǎng)絡規(guī)模。構建路局系統(tǒng)的時空網(wǎng)絡見圖1。

圖1 時空網(wǎng)絡的構建Fig.1 Construction of the time-space network

該時空網(wǎng)絡以1 d（24 h）為1個周期，并將1 d劃分為多個時段，各時段的時長不是固定大小的，而是根據(jù)實際路局的到發(fā)車情況進行細分。圖1中的時間段分為緊張時段、正常時段和空閑時段，例如，時段2為該路局的緊張時段，以1 h進行劃分。此外，若某1個時段中不發(fā)生空車走行，可以在時空網(wǎng)絡中將該時段去除，以減少網(wǎng)絡規(guī)模。將物理網(wǎng)絡中的節(jié)點（車站1、車站2、車站3和分界站）根據(jù)劃分的時段進行拓展得到時空網(wǎng)絡節(jié)點，圖1中A1表示車站1在時段1產(chǎn)生的時空網(wǎng)絡節(jié)點。為便于表示分界站排空車情況，將分界站設為路局內部虛擬空車需求節(jié)點。時空網(wǎng)絡中的節(jié)點確定后，根據(jù)列車編組計劃（包括空車編組計劃和重空混編列車編組計劃）和列車運行圖確定時空網(wǎng)絡中的弧段。圖1中共包括2種網(wǎng)絡弧，即配空弧和停留弧。配空弧表示空車在時空網(wǎng)絡中的走行，時間由2個部分組成，列車運行時間和車站技術作業(yè)時間，例如圖1中配空弧（A3，B4）表示在時段3由車站1出發(fā)且在時段4到達車站2的空車直達列車。同一車站不同時段的節(jié)點之間由停留弧相連，表示空車在車站停留。路局系統(tǒng)的空車時空網(wǎng)絡構建完成，表述為G（N，A），N為時空網(wǎng)絡中的節(jié)點集合（包括虛擬空車需求節(jié)點），A為網(wǎng)絡弧集合。

2 模型構建

通過構建時空網(wǎng)絡，直觀描述了空車調配的動態(tài)變化過程，每1組具有不同特征的空車（空車類型、去向）代表不同的商品流。一方面，由于鐵路空車存在不同車種之間的代用現(xiàn)象，因此不同特征的空車（商品流）不是相互獨立的。另一方面，由于路局管內空車調配要優(yōu)先考慮滿足分界口排空任務，因此要將排空與局管內配空分開考慮。故動態(tài)空車調配問題中的商品流之間是部分可替代的，即局管內空車調配考慮車種代用問題，而分界口排空只考慮多車種。

針對上述空車調配問題的特點，在建模時做如下考慮：①由于空車調配問題和多商品網(wǎng)絡流問題之間存在差異，不能直接套用，為此筆者借鑒運輸問題（Transportation Problem,TP）的基本思想，增加空車供需約束，將動態(tài)空車調配問題轉化為多商品網(wǎng)絡流問題；②設置2個整數(shù)決策變量，用來分別獲取配空方案和分界站排空方案，并且能夠直觀反映出空車在時空網(wǎng)絡中的時空徑路和流量分配；③設置0-1輔助變量，用來獲取配空方案中的車種代用情況。

2.1 模型假設

為方便描述和簡化問題，構建的基于時空網(wǎng)絡的鐵路空車調配動態(tài)優(yōu)化模型，做出以下假設。

假設1?？哲嚨漠a(chǎn)生及需求的數(shù)量、時間已知或可以預測。

假設2。不考慮因列車運行途中發(fā)生故障、車輛檢修及裝卸作業(yè)延誤而導致的時間延誤。

假設3。不考慮重車運輸過程對空車的影響。即對于重空混編列車，配空弧的能力不隨重車運輸?shù)淖兓兓?/p>

2.2 符號說明

1）集合定義。N為時空網(wǎng)絡中的節(jié)點集合，i，j，s，t∈N；S為時空網(wǎng)絡中的空車供給站節(jié)點集合,索引為s，s∈S且S?N；T為時空網(wǎng)絡中的空車需求站節(jié)點集合，索引為t，t∈T且T?N；K為時空網(wǎng)絡中的分界站節(jié)點集合，索引為k，k∈K且K?N；A為時空網(wǎng)絡中的有向弧段集合，包括配空弧和停留弧，(i，j)∈A；W st為空車供給節(jié)點與空車需求節(jié)點之間的OD對集合，(s，t)∈W st；W sk為空車供給節(jié)點與分界站節(jié)點之間的OD對集合，(s，k)∈W sk；U為空車種類集合，u∈U；V為貨物種類集合，v∈V。

2.3 數(shù)學模型

以總費用最小為目標，以供給能力約束、滿足需求約束、流量平衡約束、線路通過能力約束和車種代用約束等為約束條件，構建空車調配動態(tài)優(yōu)化模型。模型根據(jù)路局的空車供需情況和國鐵集團下達的分界口排空計劃即可實現(xiàn)空車在時空網(wǎng)絡中各條弧段上的流量分配，獲得空車調配動態(tài)優(yōu)化方案。

2.3.1 優(yōu)化目標

路局作為企業(yè)，追求目標為效益最大化，在實際生產(chǎn)過程中，空車調配會導致一系列費用的產(chǎn)生和變化。模型以路局空車調配總費用最小化為目標。具體地，將空車調配費用概括為以下3種。

1）空車通過弧段（配空弧和停留?。┊a(chǎn)生的費用?？哲囃ㄟ^配空弧產(chǎn)生的費用為空車走行費用，空車通過停留弧產(chǎn)生的費用為空車在車站內的單位時間停留費用。

2）空車貯存費用。對于空車供給站，若該站產(chǎn)生的空車在當天沒有進行調配，造成空車在該站的閑置而產(chǎn)生的費用，例如空車修護和管理費用。

3）車種代用費用?？哲囆枨笳敬b的貨物由于車種代用而產(chǎn)生的捆綁和加固費用等。

則目標函數(shù)為

2.3.2 約束條件

模型的約束條件如下。

1）空車供給站節(jié)點供給能力約束?？哲嚬┙o站節(jié)點s發(fā)出的分車種空車數(shù)應小于等于該節(jié)點所能提供的空車數(shù)量，即

2）空車需求站節(jié)點滿足需求約束?？哲囆枨笳竟?jié)點t接收的空車數(shù)量應滿足貨物裝車需求，即

3）滿足分界站節(jié)點排空約束。分界站節(jié)點k接收的分車種空車數(shù)量應滿足分界口排空計劃中的要求，即

與多商品流問題不同的是，空車調配問題沒有直接給出不同OD點對之間運輸需求，為了實現(xiàn)空車調配問題向多商品流問題的轉化，首先要確定空車在供給站、需求站和分界站之間的點對點調配方案。此時可以將空車調配問題視為傳統(tǒng)運輸問題中產(chǎn)銷不平衡的運輸問題，即式（5）～（7）中的供給能力約束和滿足需求約束。

4）中間節(jié)點流量平衡約束。由于起訖點流平衡約束已包含至式（5）～（7），故本部分只包括中間節(jié)點的流平衡約束，對于各中間節(jié)點，為保證路徑連續(xù)，節(jié)點的空車流入量和流出量應相等，即

5）線路（配空弧和停留?。┩ㄟ^能力約束。每條網(wǎng)絡弧上的空車流量不得超出其通過能力。對于配空弧，其通過能力為根據(jù)列車運行圖確定的圖定能力，對于停留弧，其通過能力由車站停留能力確定，即

6）車種代用約束。由于考慮路局內的車種代用情況，需求站節(jié)點t的分種類貨物可以由不同種類的空車運送，但每種貨物只能選擇1種空車運送，即

該約束僅保證了路局管內排空中不同車種之間的代用，而不影響分界站排空的空車種類。

7）決策變量和輔助變量類型約束

綜上，基于時空網(wǎng)絡的鐵路空車調配動態(tài)優(yōu)化模型見式（4）～（14）。該模型為線性整數(shù)規(guī)劃模型，可以利用商業(yè)優(yōu)化求解器高效求解。

3 算例分析

3.1 算例描述

為了驗證動態(tài)空車調配優(yōu)化模型的有效性，選取中國鐵路昆明局集團有限公司轄區(qū)內鐵路貨運站配空情況進行分析。為了簡化算例復雜度，對區(qū)域路網(wǎng)進行歸并，將昆明局轄區(qū)內的車站按照裝車數(shù)占路局裝車比重進行排序，見表1。

表1 車站裝車比重排序表Tab.1 List of loading proportions at stations

選取裝車比重大于1且車收入高于路局平均水平的車站，將距離較近的車站也進行歸并，得到簡化昆明局區(qū)域路網(wǎng)見圖2。簡化路網(wǎng)中共有11個車站，其中有10個技術站和1個分界站，滬昆鐵路貴昆段的宣威站為分界站。

圖2 簡化路網(wǎng)Fig.2 Simplified road network

表2 和表3是分別為某日空車需求站請求空車數(shù)據(jù)和空車供給站分車種卸空車情況。

根據(jù)表4列車（空車和空重混編列車）編組計劃確定時空網(wǎng)絡中的配空弧，配空弧的起點和終點分別是列車發(fā)站和到站，弧段的時間跨度由列車開行時間和車站作業(yè)時間共同組成。

表2 空車需求站請求空車情況Tab.2 Requested conditions of stations demanding for empty cars

表3 空車供給站有效空車數(shù)Tab.3 Effective number of empty cars of supply stations

表4 列車編組計劃Tab.4 Formation of freight trains

根據(jù)上述數(shù)據(jù)構建包含11個車站的時空網(wǎng)絡見圖3。模型以1 d（24 h）為1個周期（當日18：00—次日18：00），根據(jù)不同作業(yè)時段的繁忙程度，將每個時段取1～3 h不等的時長，如時段2時長為1 h，時段9時長為3 h。周期內不產(chǎn)生作業(yè)的時段（15：00—18：00）未在圖3中顯示。

對算例中的費用參數(shù)做如下說明：配空弧費用是空車走行成本，根據(jù)發(fā)站至到站距離和時間計算得來；停留弧費用表示空車在車站的停留成本，停留費用=停留時間×貨車費率，為簡化計算，假定時空網(wǎng)絡中每條停留弧的費用相等；車種代用費用以《全國鐵路統(tǒng)計資料匯編2017》中的內容為準，算例中的空車種類有敞車、棚車和罐車這3種，規(guī)定敞車可代裝糧食；單車庫存費用=部屬貨車庫存費×貨車周轉時間。

3.2 計算結果

圖3 時空網(wǎng)絡Fig.3 Time-space network

對動態(tài)空車調配優(yōu)化模型進行求解，得到空車調配方案見圖4和表5。根據(jù)求解結果可知，05：00—08：00，紅果向柏果配送罐車20輛；05：00—08：00，紅果向威舍配送敞車30輛；20：00—次日02：00，昆明東向陸良配送敞車10輛；20：00—23：00，昆明東向中誼村配送棚車52輛；02：00—10：00，祿豐向大理東配送敞車10輛；20：00—次日02：00，昆明東向宣威配送棚車48輛；05：00—13：00，讀書鋪向宣威配送棚車12輛。

圖4 空車調配方案Fig.4 Solutions of empty-car distribution

表5 模型求解結果Tab.5 Model solutions

3.3 對比分析

3.3.1 與靜態(tài)空車調配模型對比

為了更直觀地說明動態(tài)空車調配優(yōu)化模型優(yōu)于靜態(tài)空車調配模型，筆者選取了1種靜態(tài)優(yōu)化模型，將算例中的供需情況劃分為2個階段，進行逐階段優(yōu)化求解并將成本累計求和，得到靜態(tài)多階段優(yōu)化策略結果見表6。

分析可知，與靜態(tài)空車調配方法相比，動態(tài)空車調配的方法具有以下優(yōu)勢：①動態(tài)空車調配優(yōu)化的總成本為99 560元，相較于靜態(tài)空車調配優(yōu)化的總成本有所下降。動態(tài)空車調配方法將整個周期內結果最優(yōu)作為優(yōu)化目標，得到的優(yōu)化結果滿足整個周期內的空車需求，是整體最優(yōu)。而靜態(tài)空車調配方法將1個完整周期劃分為不同幾個階段，保證了每個階段的優(yōu)化結果為最優(yōu)，但是整體未必是最優(yōu)，并且上1個階段調配過程沒有考慮對下1個階段的影響，使得得到的方案與動態(tài)優(yōu)化方案有所差異。②動態(tài)空車調配優(yōu)化不存在單輛空車無法掛運列車的情況。動態(tài)空車調配時空網(wǎng)絡中配空弧的構建是依據(jù)列車編組計劃完成的，對于不超出配空弧能力的空車都能掛運在對應列車上。而靜態(tài)空車調配在物理網(wǎng)絡中進行配空，沒有考慮列車編組計劃對調配結果的影響。

3.3.2 與既有動態(tài)空車調配模型對比

本文提出的空車調配動態(tài)優(yōu)化模型，與既有運用時空網(wǎng)絡方法解決動態(tài)空車調配問題的模型相比主要存在以下改進：①在時空網(wǎng)絡中時間段的劃分方式上進行了細分，圖3中構建的時空網(wǎng)絡將1 d（24 h）共劃分成時長為1～3 h不等的時段，且去除了不產(chǎn)生作業(yè)的時段，降低了模型求解復雜度。②提出借鑒傳統(tǒng)運輸問題的模型，將空車調配問題轉化為多商品網(wǎng)絡流問題，從而使構建的模型不僅可以獲取空車調配方案，而且能夠直觀地看出空車在時空網(wǎng)絡中所經(jīng)過的線路。例如，由圖4中的空車調配方案可知，紅果站在時段2產(chǎn)生的空車，首先在站內貯存，然后在時段6將20輛罐車調配至柏果站，同時將30輛敞車調配至威舍站，且預計均在時段7到達目的地。在實際生產(chǎn)中，為路局準確把握空車在各個時間的作業(yè)狀態(tài)提供依據(jù)。

表6 不同策略下調配結果對比Tab.6 Result comparison under different strategies

4 結束語

對鐵路局管內空車調配動態(tài)優(yōu)化問題進行了研究。對時空網(wǎng)絡中的時間段劃分方式進行改進，降低模型求解復雜度。通過改進約束將動態(tài)空車調配問題轉化為多商品網(wǎng)絡流問題，綜合考慮空車調配的特點，構建了基于時空網(wǎng)絡的鐵路空車調配動態(tài)優(yōu)化混合整數(shù)規(guī)劃模型，并利用優(yōu)化軟件求解模型。通過算例分析驗證了模型的有效性，對比分析結果表明，相較于靜態(tài)空車調配模型，本文構建的動態(tài)空車調配模型在一定程度上降低了空車調配總成本，且不存在單輛空車無法掛運列車的情況。此外，模型得出的空車調配方案能夠更加直觀的看出空車在不同時間的作業(yè)狀態(tài)。未來將進一步研究如何將空重車流協(xié)同優(yōu)化和求解全路動態(tài)空車調配問題。