耿令乾

（沈陽鐵路局 運輸處，遼寧 沈陽 110001）

貨物列車編組計劃與編組站負荷分工聯(lián)合優(yōu)化模型

耿令乾

（沈陽鐵路局 運輸處，遼寧 沈陽 110001）

提出編組站解編負荷狀態(tài)評價函數(shù)及曲線，以車流組織費用最小化和編組站解編負荷狀態(tài)最佳化為目標，構建貨物列車編組計劃與編組站負荷分工聯(lián)合優(yōu)化模型，并考慮編組方案惟一性、解編能力和調(diào)車線數(shù)量等約束條件。利用目標規(guī)劃法(GP)將模型由多目標轉(zhuǎn)化為單目標，設計了相應的搜索生成方法并編程予以實現(xiàn)。最后基于實際路網(wǎng)案例，使用LINGO數(shù)學軟件完成模型的求解和對比分析，驗證了模型的合理性和有效性。

鐵路；編組站；編組計劃；優(yōu)化模型

1 研究背景

隨著我國高速鐵路的建設，既有線貨運能力得到釋放，鐵路大貨運量時代即將到來。鐵路編組站是運輸生產(chǎn)的核心部門，其負荷狀態(tài)對全路運輸組織效率和效益產(chǎn)生影響，如何充分利用編組站的有效能力、降低車流組織成本是亟待研究解決的重要問題之一。貨物列車編組計劃決定了車流的解編作業(yè)地點，與編組站的負荷分工有密切的關系，同時編組站的負荷程度又會影響編組計劃的編制和實施，因此有必要將兩者聯(lián)系起來共同研究，以實現(xiàn)車流組織和編組站負荷分工的雙贏局面。

一些專家和學者在車流組織和編組站布局方面進行了深入研究[1-5]，并取得了豐碩的理論成果。但是，尚未有研究對貨物列車編組計劃與編組站負荷分工進行聯(lián)合優(yōu)化。本文提出編組站解編負荷狀態(tài)評價函數(shù)，以車流組織費用最小化和編組站負荷狀態(tài)最佳化為目標，構建貨物列車編組計劃與編組站負荷分工聯(lián)合優(yōu)化模型 (A)，采用目標規(guī)劃法 (GP)將其轉(zhuǎn)化為單目標模型，設計了車流組合變量fij的搜索生成方法，并利用 LINGO 數(shù)學軟件實現(xiàn)了模型的求解和對比分析。

2 編組站解編負荷狀態(tài)評價函數(shù)及曲線

每個編組站都存在最佳的解編負荷狀態(tài)，當解編負荷量較小時，其設備能力未充分利用，致使單位車輛的解編成本相對增加；反之，若解編負荷量過大，則易造成車流等候，加速設備折舊，削弱特殊事件的應對能力等。為此，提出編組站解編負荷狀態(tài)評價函數(shù)S(Wi)，用以描述負荷需求與能力供給之間的匹配程度，其中Wi表示i站的實際解編負荷量。定義編組站i的解編設計能力為，對應的解編負荷量為，有：

假設存在某個最佳的解編負荷量，既可以充分發(fā)揮編組站的有效能力，又能保證站內(nèi)車流作業(yè)有序、壓縮解編成本，使編組站處于最佳負荷狀態(tài)。與編組站的眾多復雜因素有關，通常需要預留一部分能力以應對特殊情況 (如車流波動等)。若編組站的實際解編負荷量與有效能力相匹配，則在理論上可認為其已達到最佳負荷狀態(tài)。定義i站的彈性扣除系數(shù)為αi，有：

利用Smax表示編組站解編負荷狀態(tài)的最佳值，對應的關系曲線如圖1所示。

圖1 編組站解編負荷狀態(tài)曲線

當解編負荷量Wi未達到時，編組站處于欠負荷狀態(tài)，隨著解編負荷量的增加，負荷狀態(tài)曲線單調(diào)上升，斜率為k欠負荷，即在區(qū)間 (0，) 上編組站的負荷狀態(tài)逐漸提高。當解編負荷量達到時，編組站處于最佳負荷狀態(tài)。當解編負荷量超過后，雖然未突破編組站的設計能力，但已經(jīng)開始占用預留能力，編組站處于超負荷運轉(zhuǎn)狀態(tài)，車流等待和設備損耗成本逐漸顯現(xiàn)，因此編組站解編負荷狀態(tài)曲線在區(qū)間 () 上呈遞減趨勢，斜率為k超負荷。k超負荷的效果近似于懲罰系數(shù)，涉及因素較為復雜，不妨暫設k超負荷＝－k欠負荷，以便于后續(xù)的計算和分析。

綜上所述，編組站解編負荷狀態(tài)評價函數(shù)可表述為：

3 貨物列車編組計劃與編組站負荷分工聯(lián)合優(yōu)化模型

3.1 參數(shù)和變量說明

設路網(wǎng)結構N＝(P,E)，其中P為技術站集合(含編組站)，P＝{1,2,…,n}，E為路段集合，E＝{eij|i，j∈P}；lij表示i→j徑路上的途經(jīng)技術站集合(設OD車流徑路已知且惟一)，lij?P；Ci為i站的集結系數(shù) (h)；mij為i→j去向的平均編成輛數(shù)，與途經(jīng)區(qū)段的牽引定數(shù)有關(車)；ti為單位車輛在i站的解編作業(yè)時間消耗 (h)；Hi為i站調(diào)車場線路總數(shù)(條)；fij為i→j的車流總量 (車)。

定義直達去向決策變量：

3.2 目標函數(shù)

（1）車流組織費用最小化。從優(yōu)化貨物列車編組計劃的角度出發(fā)，以組織直達去向的集結車小時消耗和車流在途中解編車小時消耗最小化作為模型的目標函數(shù)：

（2）編組站解編負荷狀態(tài)最佳化。采用編組站解編負荷狀態(tài)評價函數(shù)即公式⑶描述各編組站的負荷狀態(tài)，以路網(wǎng)上所有編組站的解編負荷狀態(tài)最佳化為目標：

公式⑺促使負荷不足的編組站吸引車流，負荷過量的編組站轉(zhuǎn)移車流，直接影響列車編組計劃的生成?？紤]到公式⑶中S(Wi) 為分段多項函數(shù)，在計算求解的過程中效率較低，因此將其簡化為：

式中：可理解為編組站負荷程度的期望值，實際解編負荷與期望值的偏差越小，表明編組站的負荷狀態(tài)越理想。

3.3 約束條件

（1）編組方案惟一性約束。對于任意車流fij，只能選擇一種組織方案，編開直達列車或并入近程去向在k站進行解編作業(yè)，即：

（2）車站解編能力約束。無論是編組站還是技術站，都存在解編能力上限，實際的解編作業(yè)量不得超過車站的最大解編能力，即：

（3）調(diào)車線使用數(shù)量約束。編組列車所使用的調(diào)車線數(shù)量應小于上限，每個編組去向至少占用一條調(diào)車線。設調(diào)車線的單位容量為ω車，有：

（4）車流合并、解編的前提條件約束。若車流fij選擇在途中k站進行解編作業(yè)，則前提是存在i→k的近程直達去向。換言之，當i→k直達決策變量yik＝0 時，必有＝0；反之，若yik＝1，此時＝0 或 1，線性不等式可表述為：

根據(jù)0-1變量的特性，同一近程去向的約束條件相互疊加形成：

式中：N為一個足夠大的正數(shù)。

（5）變量類型約束。決策變量yij、均為 0-1變量：

3.4 構建模型

綜上所述，以車流組織總費用最小化作為第一目標，以編組站解編負荷最佳化作為第二目標，構建貨物列車編組計劃與編組站負荷分工聯(lián)合優(yōu)化模型 (A) minZ1，Z2′。模型(A)屬于多目標 0-1 整數(shù)規(guī)劃模型。

4 求解流程及相關方法說明

4.1 模型求解流程

首先利用 VC++ 程序?qū)ij表述為車流 OD 和決策變量x?k的組合形式，然后基于目標規(guī)劃法 (GP)將模型 (A) 的多目標函數(shù)轉(zhuǎn)為化單目標函數(shù)，并使用 LINGO 軟件結合具體案例對模型 (B) 求解，優(yōu)化確定列車編組計劃和編組站解編負荷分工方案。

4.2 基于車流徑路的 fij 搜索生成方法

鐵路車流屬于一種強可控交通流，運輸過程中呈現(xiàn)出樹形徑路、不可拆分等特點[6]。在技術站完成解編作業(yè)后的車流，如果有相同的前方到站，即視為同一支車流，在送往目的地的過程中不能被拆散。由i→j的總車流fij的表達式為：

不難看出fij的表達式涉及組合嵌套，其復雜程度呈級數(shù)增長，難以直接表述。因此，通過設計基于車流徑路的fij搜索生成方法，結合VC++ 程序設計予以實現(xiàn)。其步驟扼要說明如下。

步驟 1：已知集合N＝{nij|i，j∈P}中各OD對應的惟一徑路，車流n00的徑路可描述為l＝{O，

ODOD k1，k2，…，km，D}，其中O、D分別為起訖點，k1，k2，…，km為途經(jīng)技術站，依次類推生成全體OD 的徑路集L。

步驟 2：欲確定車流fij的表達式，若i∈PS，直接有fij＝nij，流程結束；若i∈PI，在L中搜索終點 D＝j且途經(jīng)i站的徑路，形成子集LOj＝{…}，LOj中的任意元素均滿足i∈，如{Om,k1,k2,…,kr,i,…,j}，如圖2所示。

圖2 搜索過程示意圖

步驟 3：中Om、i兩站間的元素 (包括i站)k1,k2,…,kr，i即為車流解編備選站點，可據(jù)此生成各 OD 的解編接續(xù)備選方案，表述為決策變量的組合形式。其中i屬于必經(jīng)站，根據(jù)排列組合的方法枚舉車流組織方案，利用決策變量聯(lián)乘描述前后接續(xù)的車流改編鏈，如表1所示。在研究中發(fā)現(xiàn)，解編站點的搜索、選擇過程遵循固定的規(guī)律，因此可在程序設計時將組合形式預置，依次套用即可。

表1 決策變量組合形式示例

4.3 目標規(guī)劃法(GP)

目標規(guī)劃法 (GP) 的核心思想是為每個目標函數(shù)設定一個標準值Fi，引入偏差變量和描述目標函數(shù)與標準值的近似程度，從而將原有的多目標函數(shù)轉(zhuǎn)化為總偏差量最小的單目標函數(shù)，進而求得多目標模型的優(yōu)化解。目標規(guī)劃法的優(yōu)勢主要體現(xiàn)在以下兩個方面。

（1）通過設定權重因子ωi來平衡和調(diào)整不同目標函數(shù)的數(shù)量級和優(yōu)先級。

利用目標規(guī)劃法 (GP) 將模型 (A) 轉(zhuǎn)化為模型(B)：

模型 (B) 屬于單目標 0-1 混合規(guī)劃模型。在模型 (A) 中，目標函數(shù)Z1和Z2′均取最小值，因此在預設標準值時應保證F1

5 案例分析

以我國東北部分路網(wǎng)為例，對貨物列車編組計劃及編組站負荷分工進行聯(lián)合優(yōu)化。案例路網(wǎng)共包含 13 個技術站，其中沈陽西、山海關、四平和通遼為編組站，如圖3所示?；A數(shù)據(jù)部分來源于有關項目：OD 共計 210 股，車流徑路和技術站相關參數(shù)已知 (略)。共預設了4種不同的情形用于對比分析，使用 LINGO8.0 數(shù)學軟件 (設置為全局最優(yōu)解選項 ) 分別計算求解。

圖3 案例路網(wǎng)結構示意圖

情形①：不考慮編組站解編負荷狀態(tài)最佳化的編組計劃獨立優(yōu)化模型 (忽略模型 (A) 中的目標函數(shù)Z2或Z2′)。情形②：采用模型(B)，令＝0.8×＝2,4,12,14)，權重系數(shù)ω1＝ω2。情形

表2 LINGO 計算過程和結果的各項指標

表2中以 (i＝2,4,12,14) 表示i站的解編負荷量，β可解釋為i站的負荷程度。情形①僅考慮列車編組計劃的最優(yōu)化，因此車流組織費用最低，然而沈陽西、四平、山海關3個編組站處于超負荷狀態(tài)，通遼站的解編負荷量不足。情形②對貨物列車編組計劃和編組站負荷分工進行聯(lián)合優(yōu)化，沈陽西和通遼站的負荷狀態(tài)明顯好轉(zhuǎn)，車流組織費用略有增加，但是四平和山海關站的負荷狀態(tài)依舊不理想。情形③通過調(diào)整權重系數(shù)，使4個編組站的負荷均達到理想狀態(tài)，但是車流組織費用顯著增加。情形④的計算結果與情形③一致。通過分析可歸納得出以下結論。

（1）利用模型 (B )能夠成功實現(xiàn)貨物列車編組計劃和編組站負荷分工的聯(lián)合優(yōu)化。

（2）目標規(guī)劃法中權重系數(shù)的取值直接影響多目標模型的優(yōu)化效果。在本案例中有nω1＝ω2，隨著n值的增大，目標函數(shù)Z2或Z2′的優(yōu)先性逐漸增強，Z1的優(yōu)先性逐漸減弱，反之同理。這種優(yōu)先性是存在極限的，如案例中情形③已達到極限效果，盡管情形④繼續(xù)上調(diào)ω2的值，然而結果未發(fā)生變化。

（3）模型 (B) 中兩個目標函數(shù)之間屬于博弈關系，此消彼長，可以通過調(diào)整權重系數(shù)的方法進行均衡，但是最終方案需要人工決策。例如，案例中ω2的理論區(qū)間為 [ω1，2ω2]，其取值須根據(jù)試驗效果和實際需求綜合確定。

6 結束語

編組站解編負荷狀態(tài)評價函數(shù)和曲線，構建了貨物列車編組計劃與編組站負荷分工聯(lián)合優(yōu)化模型 (A)，利用目標規(guī)劃法 (GP) 轉(zhuǎn)化為單目標模型(B)，并且設計了基于車流徑路的fij搜索生成方法。案例結果表明，模型 (B) 實現(xiàn)了預期效果，對提高貨物列車編組計劃質(zhì)量和優(yōu)化編組站的分工布局具有重要的意義。在此過程中發(fā)現(xiàn)，參數(shù)Wibest與k超負荷與鐵路現(xiàn)場的復雜因素有關，有待進一步研究和探索。

[1] 曹家明，朱松年. 鐵路網(wǎng)上技術站直達列車編組計劃優(yōu)化的二次0-1規(guī)劃法[J]. 鐵道學報，1993，15(2)：62-69.

[2] 林柏梁，朱松年，趙 強. 技術直達列車編組計劃的階躍函數(shù)模型及同構變換[J]. 西南交通大學學報，1994，29(1)：91-96.

[3] 林柏梁. 機車長交路條件下的技術站列車編組計劃無調(diào)作業(yè)參數(shù)模型[J]. 鐵道學報，1999，21(6)：6-9.

[4] 許 紅，馬建軍，龍 昭，等. 技術站單組列車編組方案模型與計算方法的研究[J]. 鐵道學報，2006，28(3)：12-17.

[5] 林柏梁，徐忠義. 編組站布局規(guī)劃模型[J]. 鐵道學報，2002，24(3)：5-8.

[6] 曹學明，王喜富，林柏梁. 重空車流徑路及多車種空車調(diào)配協(xié)同優(yōu)化模型[J]. 中國鐵道科學，2009，30(6)：114-118.

Optimization Model of Freight Car Marshalling Scheme and Load Dividing & Combining in Marshalling Station

GENG Ling-qian

(Freight Transportation, Shenyang Railway Administration, Shenyang 110001, Liaoning, China)

This paper puts forward the evaluation function and curve of uncoupling load status in marshalling station. With the target of minimum cost of train f ow organization and optimization of uncoupling load status in marshalling station, the optimization model of freight car marshalling plan and load dividing & combining in marshalling station is established, and the restriction condition, such as uniqueness of marshalling scheme, uncoupling capacity and shunting track number, were all considered. By using the GP method, the model was transferred from multi-goal into single goal, and corresponding search generating method was designed which programme had realized. In the end, based on the examples of actual railway network, the paper completes the model’s solution and contrastive analysis by using the LINGO mathematic software, and validates the rationality and validity of the model.

Railway; Marshalling Station; Marshalling Scheme; Optimization Model

1003-1421(2011)06-0059-05

U292.8；U291.4+12

A

2011-04-26

林 欣