鐵路編組站布局的雙層規(guī)劃方法研究

殷 勇，彭其淵

(西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 610031)

鐵路特編點(diǎn)組和站自的然合集理散布規(guī)局律是，指正在確鐵地路選網(wǎng)擇上編按組車站流的位置，經(jīng)濟(jì)合理地確定其規(guī)模[1]。由于路網(wǎng)上編組站之間的分工相互關(guān)聯(lián)，即每一處編組站的建設(shè)(新建或改擴(kuò)建)，都會(huì)對(duì)路網(wǎng)上車流改編方式產(chǎn)生影響，因此編組站布局不能就點(diǎn)論點(diǎn)，而應(yīng)該從路網(wǎng)整體優(yōu)化的角度加以考慮。長(zhǎng)期以來，由于缺乏有效的優(yōu)化方法，現(xiàn)有的編組站布局決策基本上立足于經(jīng)驗(yàn)判斷。通過分析當(dāng)前我國(guó)鐵路編組站布局存在的主要問題，結(jié)合我國(guó)鐵路車流的特點(diǎn)和變化，對(duì)未來編組站的合理布局及其發(fā)展方向進(jìn)行了探討[2-3]。近幾年，隨著車流組織研究的進(jìn)一步深入，國(guó)內(nèi)部分學(xué)者運(yùn)用現(xiàn)代優(yōu)化方法對(duì)編組站布局問題進(jìn)行了研究，如嘗試建立編組站布局規(guī)劃優(yōu)化模型[4]，研究技術(shù)站布局的雙層規(guī)劃優(yōu)化方法[5]。因此，探討運(yùn)用雙層規(guī)劃方法提出編組站布局問題，建立編組站布局雙層規(guī)劃模型及求解算法，具有積極的意義。

1 編組站布局問題的描述

隨車流量的增長(zhǎng)及車流結(jié)構(gòu)的變化，需要對(duì)路網(wǎng)編組站的位置和規(guī)模進(jìn)行必要的調(diào)整，以適應(yīng)車流不斷變化的需求。一般而言，編組站布局問題可以描述為，在有限資金投入的條件下，選擇最優(yōu)投資策略，通過改進(jìn)現(xiàn)有編組站的布局，包括新建編組站、擴(kuò)大或減小現(xiàn)有編組站規(guī)模等，使路網(wǎng)中車流組織達(dá)到最優(yōu)。編組站布局問題可以從建設(shè)投資費(fèi)用和車流組織費(fèi)用兩個(gè)方面考慮。

編組站的建設(shè)投資費(fèi)用主要取決于新建或改擴(kuò)建編組站的建設(shè)規(guī)模；路網(wǎng)車流組織費(fèi)用是對(duì)于給定的編組站布局方案，車流組織實(shí)現(xiàn)的最優(yōu)費(fèi)用。一方面，投資者通過投入大量資金，采用新建或改擴(kuò)建等措施對(duì)既有編組站布局進(jìn)行調(diào)整，以滿足車流不斷增長(zhǎng)及其組織優(yōu)化的需求；另一方面，運(yùn)營(yíng)部門通過調(diào)節(jié)路網(wǎng)上的車流組織方式，以適應(yīng)給定的編組站布局狀況。

編組站布局問題可用雙層規(guī)劃加以描述：上層規(guī)劃表示決策者為了達(dá)到車流組織最優(yōu)的目的而采取的最優(yōu)投資策略，下層規(guī)劃代表給定編組站布局方案條件下的車流組織優(yōu)化。同時(shí)假設(shè)：對(duì)于任意給定的上層決策變量 (編組站布局方案)，都可以從下層規(guī)劃中求得一個(gè)惟一的最優(yōu)車流組織方案。上層決策通過設(shè)置不同的編組站布局方案影響下層決策，因而限制了下層決策的可行約束集，而下層決策行為又會(huì)通過車流組織方案對(duì)應(yīng)的費(fèi)用影響上層的目標(biāo)函數(shù)。

2 編組站布局的雙層規(guī)劃模型

2.1 上層規(guī)劃模型

對(duì)于一個(gè)給定的路網(wǎng) (V，E)，這里 V 是所有備選編組站的集合，E 為路網(wǎng)上的邊集。設(shè) k 是路網(wǎng)上的某個(gè)備選編組站，引入 0-1 變量 xk，定義為：

首先，編組站的選擇是有條件的，主要考慮在路網(wǎng)的交匯處而且有大量車流集散。因此，處于路網(wǎng)主要干線的交匯處而且有大量到發(fā)車流的節(jié)點(diǎn)構(gòu)成備選編組站集合V，同時(shí)為減少可能的組合方案數(shù)量，可結(jié)合專家經(jīng)驗(yàn)將 V 分為兩類，即 V＝{V1，V2}。其中，V1表示必選編組站集合，相應(yīng)的約束為：

V2表示可能設(shè)為編組站的集合，相應(yīng)的約束為：

對(duì)于被選設(shè)的編組站，還需進(jìn)一步確定其新建或改擴(kuò)建方案。設(shè) k 站被選設(shè)為編組站，相應(yīng)的新建或改擴(kuò)建方案有 P (k) 個(gè) (包括維持既有編組站規(guī)模)，引入第2組 0-1 變量 xkp，定義為：

在路網(wǎng)上某個(gè)特定地點(diǎn)，若新建或改建既有編組站，可選擇的方案很有限。我國(guó)鐵路主要推薦的站型是：?jiǎn)蜗蛞患?jí)三場(chǎng)、二級(jí)四場(chǎng)、三級(jí)三場(chǎng)和雙向三級(jí)六場(chǎng)，其他站型都是在此基礎(chǔ)上派生出來的，因此 P(k) 是有限的。就 k 站而言，雖然有 P (k)個(gè)方案，但是在規(guī)劃期內(nèi)這些方案是互不相容的，且當(dāng) xk＝1 時(shí)，必有一個(gè)方案被選擇，因此可以用方案互不相容約束來表達(dá)。

以編組站建設(shè)投資費(fèi)用和路網(wǎng)上車流組織費(fèi)用之和最小為目標(biāo)函數(shù)，建立上層規(guī)劃模型為：

式中：M 為規(guī)劃年數(shù)；λ 為貼現(xiàn)率；β 為車小時(shí)的單價(jià)；Y (X ) 表示路網(wǎng)上的車流組織費(fèi)用，其值為決策變量 X 的函數(shù)，不同的編組站布局方案，對(duì)應(yīng)不同的車流組織費(fèi)用。

2.2 下層規(guī)劃模型

下層規(guī)劃是針對(duì)不同的編組站布局方案，求相應(yīng)路網(wǎng)上的車流組織優(yōu)化問題，即列車編組計(jì)劃(簡(jiǎn)稱TFP) 問題。關(guān)于 TFP 的研究，特別是技術(shù)站單組列車的編組計(jì)劃，很多學(xué)者和專家都已進(jìn)行了長(zhǎng)時(shí)間的系統(tǒng)研究和探索，得出了一些重要結(jié)論，建立了較為完善的規(guī)劃模型。其中比較著名的有混合整數(shù)規(guī)劃模型、線性 0-1 規(guī)劃模型、二次 0-1 規(guī)劃模型、網(wǎng)絡(luò)優(yōu)化模型、有利去向模型、階躍函數(shù)模型及高次 0-1 規(guī)劃模型等[6-8]。

研究車流組織優(yōu)化問題，考慮其編組站布局規(guī)劃方案是變化的，但對(duì)于給定的一組編組站布局方案，則與原 TFP 問題完全一致，借鑒TFP 的網(wǎng)絡(luò)優(yōu)化方法構(gòu)建下層規(guī)劃模型 (這里約定車流組織以給定的車流徑路為前提)。

對(duì)于某一編組站選址和規(guī)模方案 X，其中編組站集 SX＝{s(1)，s(2)，…，s(n)}，全體可能的編組去向集 AX＝{a(i,j)：s(i),s( j)∈SX}，必開編組去向集，禁開編組去向集，改編能力UX＝{u(i)：s(i)∈SX}、編組去向車流下限VX＝{v(i,j)：a(i,j)∈AX}、編組去向數(shù)上限WX＝{w(i)：s(i)∈SX}、集結(jié)車小時(shí)CX＝{c(i,j):a(i,j)∈AX}、改編車小時(shí)消耗TX＝{t(i)：s(i)∈SX}、車流量FX＝{f (i,j)：s(i)，s ( j)∈SX}，車流徑路LX＝{L(x,y)：x,y＝1,2,…, n}，編組去向集為Bx，則建立模型：

3 模型的算法研究

一般雙層規(guī)劃問題的求解都是非常復(fù)雜的，即使是很簡(jiǎn)單的雙層線性規(guī)劃問題也是NP-hard問題，不存在多項(xiàng)式求解算法[9]。求解雙層規(guī)劃問題的關(guān)鍵是找到反應(yīng)函數(shù)的具體形式，對(duì)于連續(xù)變量情況，可以通過靈敏度分析方法得出變量之間的導(dǎo)數(shù)關(guān)系，繼而可以利用泰勒展開式對(duì)反應(yīng)函數(shù)進(jìn)行近似求解[10]。本文建立的雙層規(guī)劃模型上層是一個(gè)離散變量的非線性優(yōu)化，下層是一個(gè)大規(guī)模的組合優(yōu)化，此時(shí)的雙層規(guī)劃問題更加復(fù)雜，用傳統(tǒng)的數(shù)值算法很難求解。

遺傳算法 (GA) 提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，以其具有的并行搜索能力、自適應(yīng)性和可直接應(yīng)用等優(yōu)點(diǎn)，適合于求解大規(guī)模任意目標(biāo)函數(shù)的全局優(yōu)化問題。但簡(jiǎn)單的遺傳算法在許多情況下不是十分有效，容易產(chǎn)生早熟現(xiàn)象及局部尋優(yōu)能力較差等問題，而將遺傳算法與問題的特有知識(shí)集成到一起，或者在遺傳算法中融合其他算法的思想和方法，構(gòu)成一種混合遺傳算法，則求解性能有可能達(dá)到極佳[11]。一般有兩種混合策略：①把遺傳算法和原有算法有效結(jié)合，設(shè)計(jì)一個(gè)新的混合算法；②采用原有算法的編碼或把原有算法中的一系列變換結(jié)合到混合遺傳算法中?；旌螱A 最常見的形式是在 GA 典型的重組選擇循環(huán)中嵌入一塊附加的局部?jī)?yōu)化模塊。結(jié)合本文的模型特點(diǎn)，將遺傳算法與求解車流組織優(yōu)化問題相結(jié)合，從而構(gòu)造出適合求解編組站布局雙層規(guī)劃模型的混合遺傳算法。

關(guān)于 Y (X ) 的計(jì)算，有關(guān)研究通過分析模型的不同特點(diǎn)，提出了多種有針對(duì)性的算法，除傳統(tǒng)的以手工操作為主的絕對(duì)計(jì)算法和表格分析法以外，還成功地運(yùn)用單純形算法、分枝定界算法、拉格朗日松弛算法等進(jìn)行計(jì)算機(jī)求解，并且發(fā)展了諸如有序組合樹算法、網(wǎng)絡(luò)拓?fù)渥儞Q法、二次0-1 規(guī)劃法等。值得指出的是，20 世紀(jì) 80 年代以來，國(guó)內(nèi)外學(xué)者運(yùn)用現(xiàn)代新興的智能優(yōu)化方法，如遺傳算法、模擬退火、禁忌搜索及人工神經(jīng)網(wǎng)絡(luò)等方法解決車流組織優(yōu)化問題，在實(shí)現(xiàn)大規(guī)模、多約束、非線性車流組織優(yōu)化方面表現(xiàn)了良好的性能。編組站布局雙層規(guī)劃模型的混合遺傳算法框架如圖1所示。按照模型的詳細(xì)計(jì)算過程[12]，根據(jù)計(jì)算結(jié)果并結(jié)合其他的編組站布局影響因素，提出我國(guó)鐵路編組站布局的調(diào)整方案。

4 結(jié)束語

編組站的合理布局與分工，對(duì)提高鐵路運(yùn)輸生產(chǎn)效率和水平、確保路網(wǎng)的安全暢通、加速機(jī)車車輛周轉(zhuǎn)、縮短貨物送達(dá)時(shí)間、提高經(jīng)濟(jì)效益和社會(huì)效益、促進(jìn)鐵路運(yùn)輸業(yè)協(xié)調(diào)可持續(xù)發(fā)展十分重要。通過分析建立模型，將求解車流組織費(fèi)用的計(jì)算模塊與 GA 結(jié)合，構(gòu)建了求解編組站布局雙層規(guī)劃模型的混合遺傳算法，適用于實(shí)際路網(wǎng)中的編組站布局問題決策。研究結(jié)果表明，應(yīng)用雙層規(guī)劃方法解決編組站布局問題是合適的，建立的編組站布局雙層規(guī)劃模型能夠貼切地描述編組站布局方案和車流組織優(yōu)化的關(guān)聯(lián)關(guān)系。

圖1 求解模型的混合遺傳算法框架

[1]劉其斌，馬桂貞. 鐵路站場(chǎng)及樞紐[M]. 北京：中國(guó)鐵道出版社，1999.

[2]吳家豪. 中國(guó)鐵路跨越式發(fā)展新時(shí)期的編組站分類與布局探討[J]. 鐵道經(jīng)濟(jì)研究，2005(4)：33-38.

[3]趙海寬. 基于運(yùn)力資源優(yōu)化配置和運(yùn)輸組織創(chuàng)新的鐵路編組站合理布局[J]. 鐵道運(yùn)輸與經(jīng)濟(jì)，2009，31(12)：4-7.

[4]林柏梁，徐忠義, 黃 民，等. 編組站布局規(guī)劃模型[J]. 鐵道學(xué)報(bào)，2002，24(3)：5-8.

[5]史 峰，方琪根，黎新華，等. 技術(shù)站布局的雙層規(guī)劃優(yōu)化方法[J]. 鐵道學(xué)報(bào)，2003，25(2)：74-79.

[6]胡思繼. 鐵路行車組織[M]. 北京：中國(guó)鐵道出版社，1998.

[7]林柏梁，朱松年. 路網(wǎng)上車流徑路與列車編組計(jì)劃的整體優(yōu)化[J]. 鐵道學(xué)報(bào)，1996，18(1)：1-7.

[8] 史 峰，孔慶鈐，胡安洲. 車流徑路與編組計(jì)劃綜合優(yōu)化的網(wǎng)絡(luò)方法[J]. 鐵道學(xué)報(bào)，1997，19(1)：1-6.

[9] 劉樹安，尹 新，鄭秉霖，等. 二層線性規(guī)劃問題的遺傳算法求解[J]. 系統(tǒng)工程學(xué)報(bào)，1999，14(3)：280-285.

[10] 高自友，宋一凡，四兵鋒. 城市交通連續(xù)平衡網(wǎng)絡(luò)設(shè)計(jì)一理論與方法[M]. 北京：中國(guó)鐵道出版社，2000.

[11] S·Voget. Theoretical analysis of genetic algorithms with infinite population size[J]. Complex Systems，1996(10)：167-183.

[12] 殷 勇. 鐵路編組站布局規(guī)劃方法與調(diào)整對(duì)策研究[D]. 成都：西南交通大學(xué)，2008.