鄭可心 宋 瑞 李光曄

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

0 引 言

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

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

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

1 時空網(wǎng)絡(luò)的構(gòu)建

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

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

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

2 模型構(gòu)建

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

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

2.1 模型假設(shè)

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

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

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

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

2.2 符號說明

1）集合定義。N為時空網(wǎng)絡(luò)中的節(jié)點集合，i，j，s，t∈N；S為時空網(wǎng)絡(luò)中的空車供給站節(jié)點集合,索引為s，s∈S且S?N；T為時空網(wǎng)絡(luò)中的空車需求站節(jié)點集合，索引為t，t∈T且T?N；K為時空網(wǎng)絡(luò)中的分界站節(jié)點集合，索引為k，k∈K且K?N；A為時空網(wǎng)絡(luò)中的有向弧段集合，包括配空弧和停留弧，(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ù)學模型

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

2.3.1 優(yōu)化目標

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

1）空車通過弧段（配空弧和停留弧）產(chǎn)生的費用。空車通過配空弧產(chǎn)生的費用為空車走行費用，空車通過停留弧產(chǎn)生的費用為空車在車站內(nèi)的單位時間停留費用。

2）空車貯存費用。對于空車供給站，若該站產(chǎn)生的空車在當天沒有進行調(diào)配，造成空車在該站的閑置而產(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ù)量應滿足分界口排空計劃中的要求，即

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

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

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

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

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

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

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

3 算例分析

3.1 算例描述

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

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

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

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

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

根據(jù)表4列車（空車和空重混編列車）編組計劃確定時空網(wǎng)絡(luò)中的配空弧，配空弧的起點和終點分別是列車發(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ù)構(gòu)建包含11個車站的時空網(wǎng)絡(luò)見圖3。模型以1 d（24 h）為1個周期（當日18：00—次日18：00），根據(jù)不同作業(yè)時段的繁忙程度，將每個時段取1～3 h不等的時長，如時段2時長為1 h，時段9時長為3 h。周期內(nèi)不產(chǎn)生作業(yè)的時段（15：00—18：00）未在圖3中顯示。

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

3.2 計算結(jié)果

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

對動態(tài)空車調(diào)配優(yōu)化模型進行求解，得到空車調(diào)配方案見圖4和表5。根據(jù)求解結(jié)果可知，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 空車調(diào)配方案Fig.4 Solutions of empty-car distribution

表5 模型求解結(jié)果Tab.5 Model solutions

3.3 對比分析

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

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

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

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

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

表6 不同策略下調(diào)配結(jié)果對比Tab.6 Result comparison under different strategies

4 結(jié)束語

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