基于點-弧結構的路網單組列車編組計劃優化線性0-1規劃模型

陳崇雙，趙 軍，薛 鋒，郭孜政，左大杰2,

(1.西南交通大學 數學學院，四川 成都 611756；2.西南交通大學 綜合交通大數據應用技術國家工程實驗室，四川 成都 611756； 3.西南交通大學 交通運輸與物流學院，四川 成都 611756；4.西南交通大學 綜合交通智能化國家地方聯合工程實驗室，四川 成都 611756)

貨物列車編組計劃簡稱編組計劃(Train formation Plan, TFP)，研究如何將車流組合編掛到各種不同到站和種類的列車之中，其合理編制是提高鐵路網車流組織效率和提供優質運輸服務的重要保證。

我國車流組織工作根據車流的性質進行分階段考慮，先確定裝車地、空車、班列等直達列車編組計劃，然后對未被其吸收的車流向就近的技術站集中，進而編制技術站列車編組計劃，最后再確定剩余車流的區段管內列車編組計劃[1]。在技術站列車編組計劃中，單組列車即列車僅編掛一個編組去向，相比分組列車其構成較為簡單。由于我國鐵路車站改編能力和調車線不足，以及現場車流組織工作的簡便性等因素，貨物列車中單組列車的比例較高。

路網單組列車編組計劃需確定兩類決策：①網絡中開行哪些列流，即確定每支列流的始發終到站；②每支列流吸收哪些車流，從車流的角度來說，即確定每支車流在其徑路上每個車站的改編情況。單組列車編組計劃編制問題中，每支車流的徑路事先已知(如采用最短徑路、特定徑路等)，只需要考慮如何經濟可行地將車流組合成列流。其中，經濟性體現在列流的集結費用和車輛的改編費用；可行性體現在滿足車站的改編能力、調車線數限制，以及運輸組織上的車流不拆散原則和接續歸并原則[1]。值得注意的是，車流徑路是編組計劃問題的輸入參數，在其確定過程中已經考慮了線路區間的通過能力。車流不拆散原則要求同一只車流作為一個整體進行運輸，使編組計劃問題有別于經典的實數型網絡流，而是整數型網絡流；接續歸并原則要求相同終點車流一旦在同一車站改編之后，它們合而不分，采用相同的改編方案輸送至共同的終點站，即同終點車流的改編方案具有樹形結構。

目前，國內外許多專家學者就鐵路網上單組列車編組計劃編制進行長期探索，提出了比較合理的數學模型和有效的求解算法[2]。其中的代表文獻大致可以歸納為如下兩大類：

其一是采用數學規劃理論建模。曹家明等[3]設置車流的直達方案、一次改編和多次改編方案為0-1型決策變量，考慮每支車流的方案唯一性約束，建立二次0-1規劃模型；同時，巧妙引入獨立作業方式來減少變量數目，并利用系數矩陣的稀疏性和分塊特點進行線性松弛求解。林柏梁等[4]和Lin等[5]都以車流改編方案和列流方案為0-1型決策變量，考慮方案唯一性約束、改編能力約束、調車線數量約束，構建非線性雙層規劃模型，上層確定列車始發終到站，下層基于流量平衡思想確定車流改編方案。兩者在決策車流改編方案時略有差異，文獻[4]基于車流接續最遠站法則，即將車流編入車流在始發站的最遠去向，以實現無改編運行距離最遠；文獻[5]是由優化模型計算確定。兩者都針對大規模問題設計模擬退火算法。Chen等[6]設置直達列流方案和車流可能的改編方案為0-1型決策變量，考慮方案唯一性約束、改編能力約束、調車線數量約束和接續歸并原則，建立線性0-1規劃模型，并設計基于樹分解的求解算法。

其二是采用網絡流思想建模或者求解，即將車流視為流，列流視為弧，列車集結耗費視為弧的固定耗費，改編中轉額外耗費視為該弧的長度。李致中等[7]就小規模路網情形建立無約束的網絡流模型。史峰等[8]考慮車站改編能力和編組去向數目限制情形建模，并給出逐步添加編組去向的貪婪算法。史峰等[9]提出合并式編組方案的概念，在給定每個站的編組去向方案集的條件下將原問題轉化為以各站為終點的普通最短路問題。查偉雄等[10]設置決策變量類似文獻[5]，考慮車站編組去向數目約束和車流接續歸并，建立了非線性(目標函數是高階多項式)0-1規劃模型。該文獻將開行直達列車視為新建一個服務，由此將原問題轉化為服務系統選址問題，給出逐步減少直達列流方案(即保留有利的編組去向)的啟發式算法。

從既有研究可見，鐵路網絡單組列車編組計劃問題，雖然具有多商品網絡流問題的特點，但是車流接續歸并原則這一獨特約束所蘊含的樹形結構，使得對其不易建立線性模型和設計有效算法。例如，文獻[4-5]采用遞推方式設置車流改編變量，導致模型具有非線性結構。史峰等[8-9]刻畫接續歸并關系也依賴于遞推地確定車流改編序列。這兩種思路都不便應用強大的商業優化軟件以及經典的精確整數規劃算法，例如前兩者運用模擬退火算法，后兩者設計加弧減弧的啟發式方法等。同時，Chen等[6]雖然建立了線性0-1規劃模型，但是其模型規模隨網絡擴大呈指數增長，而且樹分解算法對于大規模問題的最優間隔(Gap)仍不算很理想。

本文將路網單組列車編組計劃優化視為1類具有樹形結構的多商品網絡流問題，在多商品網絡流的點-弧模型的建模框架下，將車流視為商品，引入一組0-1變量刻畫每支車流如何選擇列流；將直達列流視為服務，引入一組0-1變量刻畫網絡中開行哪些列流；再引入一類輔助變量保證車流接續歸并。基于此，以列流集結耗費和車流改編耗費總和最小為目標，同時考慮車站改編能力和調車線數約束，建立基于多商品網絡流點-弧結構的線性0-1規劃模型。在合理的求解時間范圍內，該模型能夠得到高質量的可行解以及緊致的下界。最后采取演示算例和大規模算例，對所構建模型的正確性和有效性進行驗證。

1 參數和符號說明

參數及其符號說明見表1。

表1 參數和符號說明

單組列車編組計劃建模，涉及一個有向網絡G=(V,E)，其中節點集合V即車站集合，其元素為技術站和線路交匯的支點站等，有向弧集合E是直接相連的線路區間集合，線路的上下行方向分別對應一條有向邊。每支車流(o,d)的徑路已知，可以表示為從其始發站o至終到站d沿途經過車站的有序集合。在單組列車編組計劃問題中，由于各列流〈i,j〉的編組內容僅為一個組的車流，該列車的運行徑路可以視為相同始發終到站的車流(i,j)的徑路。

由于車流徑路的限制，并非每支車流都可以編組到所有的列流當中。對于車流(o,d)來說，其實際能夠編組到的列流可以表示為集合

(1)

圖1 包含8個站的簡單路網

表2 決策變量

2 數學模型

2.1 目標函數

單組列車編組計劃問題的目標函數包括兩項。第一項為列流的集結耗費，僅與列流設計變量有關，相當于固定費用；另一項是車流在途中車站(不包括始發站和終到站)的改編耗費，與車流改編變量有關，相當于變動費用。目標函數為

(2)

2.2 約束條件

2.2.1 車流流量守恒約束

每支車流都需滿足以下的流量守恒約束，即每支車流都沿著其給定徑路從其始發站被輸送至其終點站。與一般多商品網絡流的流量守恒稍有區別的是，該組約束僅考慮各支車流在其給定徑路上每個站的流量平衡，而不需要考慮徑路之外的車站。其原因在于，車流徑路已經事先給定，各支車流只能在其給定徑路上沿著從其始發站至其終到站的方向和軌跡流動。

2.2.2 車站改編能力約束

到達某站的車流，包括終到該站的計劃車流和在該站進行途中改編的車流，都需要消耗該站的改編能力。在某站改編的總車流量不能超過其可用改編能力，即

(4)

2.2.3 車站調車線數約束

從某站出發的車流，包括從該站始發的計劃車流和在該站進行途中改編的車流，都需要占用該站的調車線。從某站出發的總車流量與該站單條調車線的平均容納能力之比，視為這些車流實際占用的調車線數，不能超過該站可用調車線數的限制，即

(5)

注意，文獻[4-5]采用分段線性函數刻畫車流占用的調車線數，本文采用線性度量策略。

2.2.4 車流接續歸并約束

車流接續歸并要求到達相同終點的車流，一旦在同一個站改編之后，必須采用相同的改編方案從改編站輸送至終點站，即同終點車流的改編方案具有樹形結構。本文用約束式(6)、式(7)共同刻畫車流接續歸并要求。

(6)

(7)

2.2.5 變量關聯約束

(8)

約束式(8)包含兩種情形：

2.3 優化模型

綜上，從多商品網絡流角度將路網單組列車編組計劃問題構建為

?o,d∈Vi∈Po,d

yi,j∈{0，1} ?i,j∈V

其二，同樣由于車流徑路的原因，車流流量守恒約束式(3)只要求每支車流在其給定徑路上每個車站成立，而非要求在網絡中的全部車站；同時，變量關聯約束式(8)確保每支車流的徑路與其選擇列流的徑路具有一致性。

其三，為滿足特殊的車流接續歸并要求，本文所構建的模型額外引入了約束式(6)和式(7)，保證同終點車流的改編方案具有樹形結構。可見，本文模型中的車流改編變量比一般的多商品網絡流模型具有更嚴格的要求。

3 與既有模型的對比分析

文獻[5-6]是最近路網單組列車編組計劃優化領域的兩篇典型文獻，二者的建模思路和求解算法也各具特點。本節從決策變量表達形式、模型規模和模型特點3個方面，將這兩篇文獻的模型與本文模型進行較為詳細的對比分析。

3.1 決策變量對比

車流改編變量的3種表達形式可以相互轉化，下表3以直線單方向上4個車站為例進行說明。表3中，第1列是車流改編方案的序號，第2列是對應的列流方案，第3～5列分別是3種表達方式的車流改編變量的取值。注意，表中省略了直達車流的改編變量。例如，第10種方案中，每支車流都是直達，沒有車流采用改編，故非直達車流的改編變量為空。

表3 3種車流改編變量表達形式的相互轉化

3.2 模型規模對比

3種模型的規模估計見表4。可以看出，本文模型的決策變量和約束條件的階數都為O(N4)，多于文獻[5]，但是遠少于文獻[6]，后者呈指數增長。主要原因在于文獻[6]采用全枚舉的方式設置車流改編變量，同時對每個車流改編變量提供一個約束保證接續歸并。此外，雖然文獻[5]的模型規模最小，但是由遞推的車流改編變量顯式表達車站的改編負荷和改編費用時，將出現決策變量的乘積項。即使可以引入新的變量和約束消除乘積項進行線性化，然而一方面網絡情形的表達將會非常復雜，另一方面也導致模型規模迅速增長。

表4 模型規模估計

3.3 模型特點對比

三種模型的特點總結見表5。可見，在車流改編變量設置上，文獻[5]采用隱式遞推方式，使得模型具有非線性的結構。盡管文獻[6]和本文都建立了線性的0-1規劃模型，但結構也有差異。文獻[6]的車流改編變量，列舉了車流從始發站至終到站全過程的所有可能改編方案，而本文的車流改編變量僅確定車流對單支列流編掛與否。因而前者構建的是多商品網絡流的弧-路模型，而本文建立的是點-弧模型。其次，在車流接續歸并實現手段上，三者迥異。文獻[5]基于遞推方式設置的車流改編變量，每支車流改編方案的唯一性實現了接續歸并。文獻[6]以全枚舉方式呈現每支車流的全部改編方案，直接比較同終點車流的改編方案的一致性，以判斷接續歸并原則是否滿足。而本文通過巧妙引入輔助變量和線性約束條件，正確刻畫車流改編方案之間的樹形關系。

表5 模型特點對比

4 算例分析

采用1個演示算例和1組大規模算例，對所構建模型的正確性和有效性進行分析。采用Matab 2016a編程，并調用CPLEX 12.6求解優化模型。為了公平比較，所有計算都在CPU為E5-2620 2.10 GHz、內存為128 GB的64位GPU上運行。如果沒有特別說明，CPLEX的參數都為默認配置。

4.1 演示算例

以文獻[5]中的小規模算例，測試本文模型的正確性。該算例的路網是我國哈爾濱局路網的簡化，共包含19個支點站，23條邊，314支車流。所有車流的徑路都按最短徑路設置。文獻[5]中車站的可用改編能力，是已經扣除了終到車流消耗的結果。為了讓本文的計算結果具有可比性，這里將約束式(4)調整為

(9)

對于這個算例，本文的點-弧模型式(2)、式(3)和式(5)～式(9)包含5 066個決策變量，8 926個約束。設置CPLEX的收斂mipgap為0時，0.59 s獲得最優解，最優目標值為45 421車·h，與文獻[5]以及文獻[6]弧-路模型的最優目標值完全相同。

每支車流的最優改編策略見表6，構成19×19的矩陣。在該表中，第i行第j列的單元格中元素k表示車流(i,j)在站k首次改編。特別地當k=j時，表示開行直達列流〈i,j〉。車流的完整改編方案可以由該表遞推得出。以車流(7,2)為例進行說明，由表6，該車流先在站5改編后編組到列流〈5，3〉，在站3再次改編后編組到列流〈3，2〉運送至終點站，因而車流(7,2)的改編站為5和3。該表與文獻[6]的弧-路模型的最優解并不完全相同，表7列出了改編方案不相同的三支車流。由于它們的車流量均是0，故對于目標函數值不影響。

表6 最優車流改編方案

表7 點-弧模型與弧-路模型最優解的不同

接下來分析本文點-弧模型對于車流接續歸并原則的正確性。由問題定義，車流接續歸并原則規定，如果同終點的兩支車流都在某站改編，那么從該改編站至終點站的輸送過程中，它們將采用相同的改編方案。本質上，車流接續歸并原則強制約束同終點車流的改編方案具有樹形結構。為了直觀反映這種特殊關系，以終點為站2的18支車流為例進行說明。車流的徑路見圖2(a)。注意，本算例設定所有車流的徑路都取為其最短路，因此，由最短性原則，終點為站2的車流的最短路構成一顆無向樹，根節點即為站2。車流的最優改編方案，見圖2(b)。可見，除了站2之外，其他站都只有唯一一條出弧，即最優改編方案是以站2為根節點的一棵有向樹。對比圖2(a)和圖2(b)可知，如果車流采用直達方案，無所謂改編；如果采用改編方案，則改編站都限制在其給定車流徑路上。例如，對于車流(6，2)，其車流徑路P6，2={6，5，4，3，2}，途中改編車站為5和4均在其車流徑路上。

圖2 終點為站2的18支車流

圖3 松弛接續歸并約束后車流(5,2)和(6,2)的改編方案

4.2 大規模算例

以文獻[6]中的10個大規模算例，驗證所提出方法的有效性。這些算例的路網是我國鐵路貨運網絡的簡化，包括83個車站，158條邊，平均約5 700支車流，所有車流的徑路都給定為最短徑路。由于文獻[5]采用分段線性函數刻畫車站調車線數約束，而且具有非線性結構，故本文點-弧模型僅與文獻[6]的弧-路模型以及樹分解算法進行對比。

文獻[6]的弧-路模型和本文的點-弧模型，規模對比見表8。本文模型的決策變量數和約束條件數都僅相當于文獻[6]的3%，而且系數矩陣非常稀疏，非零元僅占1.39×10-5。

表8 大規模算例模型規模對比

對比弧-路模型和點-弧模型的解質量，設置CPLEX最長運行時間為3 h，結果對比見表9。由表9可得，在3 h限制時間下，一方面，弧-路模型的下界都比點-弧模型小，甚至該模型對算例1、4、5和6的下界為0。另一方面，弧-路模型的上界都比點弧模型大。由于這兩方面的原因，弧-路模型的平均最優間隔(Gap)高達63.65%，而點-弧模型平均Gap為9.03%。由于點-弧模型對于算例9和10的Gap較高，為此延長CPLEX最長運行時間為10 h，兩個模型的結果對比見表10。延長運行時間后，弧-路模型的下界和上界稍有改善，但平均Gap仍高達60.79%。然而點-弧模型的平均Gap為1.55%，全部Gap低于5%。

對比表9和表10還可發現，當計算時間從3 h延長至10 h，點-弧模型對于算例9和算例10的Gap顯著減少。為此，進一步分別設置運行時間為4、5、7 h，應用點-弧模型再次求解這兩個算例。算例9和算例10的求解質量與計算時間的關系見圖4，觀察可知，這兩個算例的下界隨著計算時間的變化不明顯，但其上界在計算時間為3～4 h范圍存在陡降，從而使得Gap顯著減小，隨著計算時間的繼續增加，上界和Gap均趨于穩定。可見，計算時間對于點-弧模型的求解性能具有影響，在實際應用時，可取多組不同的計算時間進行嘗試，從而對點-弧模型獲得求解質量和計算時間的有效折中。

表9 弧-路模型與點-弧模型對比(運行3 h)

表10 弧-路模型與點-弧模型對比(運行10 h)

考察弧-路模型和點-弧模型線性松弛的定界效果。將模型中所有決策變量松弛為[0,1]的實數，限定運行時間為3 h。表11對比兩個模型線性松弛的目標函數值和求解時間。結果表明，相比弧-路模型，點-弧模型線性松弛的目標函數值平均提高3.15%，最高達7.92%(第9個算例)。同時結合表9，兩個模型在分支定界過程中的最優下界，相比它們的線性松弛改善都不明顯，分別僅增加3.99%和0.10%。在求解時間方面，點-弧模型線性松弛平均14 min就能求到最優，但弧-路模型線性松弛在3 h內都不能求出最優解。可見，相比于弧-路模型，點-弧模型能夠在較短時間內提供更緊的下界。

表11 弧-路模型與點-弧模型線性松弛對比

現將文獻[6]的樹分解算法和本文的點-弧模型進行對比。為了對比的公平性，將點-弧模型的求解時間限制為樹分解算法的運行時間。表12列出了兩種方法的上界、Gap和運行時間。可看出，樹分解算法平均需要1.05 h，最長運行2.15 h，平均Gap為12.51%。而點-弧模型在相同運行時間下，平均Gap為51.98%，其中有3個算例的Gap低于樹分解算法。同時結合表10可知，當點-弧模型運行時間延長至10 h時，Gap都將顯著降低(全部低于5%)。

表12 樹分解算法與點-弧模型對比

5 結論

本文基于多商品網絡流理論研究了鐵路網上單組列車編組計劃優化問題，借助于多商品網絡流點-弧模型的建模框架，建立一個新的線性0-1規劃模型。得到如下結論：

(1)將車流視為商品、列流視為服務、車流的改編耗費作為商品的變動費用、列流的集結耗費作為服務的固定費用，同時將車流不拆散和接續歸并原則、車站改編能力和調車線限制視為邊界約束，則路網單組列車編組計劃問題可轉換為1類多商品網絡流問題。

(2)采用點-弧方式設置車流改編變量，盡管不同于既有模型，但可以相互轉化。本文的模型在形式上更緊湊，模型的決策變量數和約束條件數都比文獻[6]的弧-路模型顯著減少，盡管該模型的規模比文獻[5]的模型稍多，但后者是一個非線性模型。

(3)車流接續歸并要求使得同終點車流的改編方案具有樹形結構，利用這一特點，在多商品網絡流的建模框架下，通過引入輔助變量和約束可巧妙刻畫這一要求。小規模算例的計算結果表明，本文所提出的基于輔助變量的建模策略，能夠精確表達車流接續歸并原則。

(4)大規模算例的測試結果表明，本文的點-弧模型相較于文獻[6]的弧-路模型在相同時間限制下均可得到質量更高的解。同時，點-弧模型的線性松弛容易求到最優(約14 min)，而弧-路模型的線性松弛求解仍很困難。

(5)在相同的時間限制下，本文點-弧模型的可行解遜于文獻[6]的樹分解算法，但仍有3/10個算例的Gap優于樹分解算法。適當延長運行時間(至10 h)，點-弧模型的可行解將顯著提高(全部小于5%)，均優于文獻[6]的樹分解算法。

本文研究可作進一步拓展。首先，下一步可利用所構建點-弧模型的較優良的數學性質和較高效計算性能，開發有效求解算法，以更好地求解更大規模問題。其次，單組列車編組計劃的質量受給定車流徑路的影響，未來有價值研究兩者綜合優化問題，考慮車流不拆散和接續歸并兩大原則，建立多項式規模的線性模型并設計求解算法。另外，列流設計方案與車流改編方案受到車流量、車站的集結與改編時間參數、改編能力及調車線數等參數的影響，后者的波動性將會影響到鐵路貨物運輸服務的質量與效率，因而研究車站集結與改編時間參數等不確定性下的路網單組列車編組計劃優化問題，也將是下一階段的方向。