基于拉格朗日的高速鐵路車站作業(yè)優(yōu)化

白紫熙，周磊山，王勁，郭彬

（北京交通大學(xué)交通運(yùn)輸學(xué)院，北京100044）

基于拉格朗日的高速鐵路車站作業(yè)優(yōu)化

白紫熙，周磊山＊，王勁，郭彬

（北京交通大學(xué)交通運(yùn)輸學(xué)院，北京100044）

本文從Job-Shop調(diào)度角度出發(fā)，以列車為待加工的“工件”，將車站接車進(jìn)路、到發(fā)線和發(fā)車進(jìn)路看作“加工機(jī)器”，列車在車站的走行與停站看做不同的“作業(yè)工序”，把高速鐵路車站作業(yè)問題抽象成Job-Shop車間調(diào)度優(yōu)化，以設(shè)備能力、沖突進(jìn)路、停站時(shí)間為空間和時(shí)間約束，以最小化到發(fā)線的占用時(shí)間為優(yōu)化目標(biāo)，建立高速鐵路車站作業(yè)優(yōu)化模型.采用拉格朗日方法松弛原模型的約束條件，建立車站技術(shù)作業(yè)問題的拉格朗日對(duì)偶松弛問題，設(shè)計(jì)了高速鐵路車站作業(yè)優(yōu)化模型算法.并以高速鐵路的某一車站為實(shí)例進(jìn)行驗(yàn)證，實(shí)例表明，該算法可以有效地化解車站作業(yè)進(jìn)路沖突和實(shí)現(xiàn)到發(fā)線運(yùn)用時(shí)間的最小化.

鐵路運(yùn)輸；車站作業(yè)優(yōu)化；Job-Shop；拉格朗日松弛；次梯度算法

1 引言

高速鐵路車站作業(yè)計(jì)劃包含接發(fā)車作業(yè)進(jìn)路、到發(fā)線運(yùn)用計(jì)劃、動(dòng)車組出入段及轉(zhuǎn)線調(diào)車作業(yè)，也就是為列車安排進(jìn)路占用方案和到發(fā)線運(yùn)用方案.對(duì)車站而言，到發(fā)線和咽喉進(jìn)路屬于具有時(shí)空約束的固定設(shè)備，因此對(duì)車站作業(yè)進(jìn)行合理優(yōu)化具有很重要的意義.在現(xiàn)實(shí)行車組織作業(yè)中，由于一些不可避免的因素，列車不可能完全按圖行車，當(dāng)列車出現(xiàn)與列車運(yùn)行圖不符時(shí)，車站作業(yè)的合理安排有利于減小列車的晚點(diǎn)傳播的影響.

車站作業(yè)問題屬于NP-hard問題，在多項(xiàng)式事件范圍內(nèi)很難求到最優(yōu)解，國(guó)內(nèi)學(xué)者大多將車站作業(yè)問題抽象成圖論問題[1]、0-1規(guī)劃問題[2]及排序問題[3]，采用分枝定界法[4]或啟發(fā)式算法求解車站作業(yè)問題，主要有蟻群算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)算法和模擬退火算法等.國(guó)外學(xué)者的研究比較有代表性的有：Malachy設(shè)計(jì)了基于沖突檢測(cè)的股道分配算法，并應(yīng)用于一系列有多種類型和速度的列車到發(fā)的復(fù)雜車站[5]；Partha假設(shè)列車不一定都能夠按照列車運(yùn)行圖的規(guī)定時(shí)刻到來，建立了混合整數(shù)規(guī)劃來描述車站的進(jìn)路分配問題[6]；Joaqu?′n Rodriguez提出了一個(gè)約束規(guī)劃模型來解決列車在樞紐站的進(jìn)站路徑和時(shí)間安排問題[7]；Richard Freling等人提出了一種改進(jìn)的列生成算法來解決旅客列車進(jìn)路選擇問題[8].

綜上，國(guó)內(nèi)外學(xué)者的研究大都集中在到發(fā)線運(yùn)用或進(jìn)路選排兩個(gè)方面，但是對(duì)于高速鐵路車站作業(yè)的整體綜合優(yōu)化卻鮮有研究.本文從Job-Shop調(diào)度角度出發(fā)，將車站作業(yè)問題抽象成“機(jī)器、作業(yè)與工序”的優(yōu)化問題，將車站接車（出段）進(jìn)路、到發(fā)線和發(fā)車（入段）進(jìn)路看作機(jī)器，列車在車站的走行與停站看做不同的工序，列車作業(yè)的彼此與獨(dú)立之間具有一定的時(shí)間和空間限制，在此基礎(chǔ)上建模.由于拉格朗日是一種求極值的強(qiáng)有力的經(jīng)典方法，對(duì)于最優(yōu)化問題有著很好的適用性，在各學(xué)科領(lǐng)域都得到了廣泛的應(yīng)用，而在鐵路運(yùn)輸組織中卻很少涉及，本文采用拉格朗日次梯度算法最終求解模型.

2 高速鐵路車站作業(yè)計(jì)劃模型建立

車站作業(yè)計(jì)劃是在時(shí)間與空間的雙重約束下，為列車安排走行進(jìn)路與到發(fā)線.以列車為準(zhǔn)備加工的“工件”，咽喉進(jìn)路與到發(fā)線為“加工機(jī)器”，則車站作業(yè)計(jì)劃可以歸結(jié)為一類特殊的Job-Shop調(diào)度問題.圖1為列車車站作業(yè)的Job-Shop抽象，全站所有的技術(shù)作業(yè)類型的工序圖可劃分成若干個(gè)作業(yè)串聯(lián)起來的工序圖.分析列車在車站的作業(yè)流程，可概括為三道作業(yè)工序：

（1）列車經(jīng)由接車進(jìn)路，準(zhǔn)備進(jìn)入到發(fā)線，對(duì)于始發(fā)列車來說為出段作業(yè)；

（2）列車占用到發(fā)線，供旅客上下車或其它列車準(zhǔn)備工作；

（3）列車轉(zhuǎn)出到發(fā)線，進(jìn)入出站進(jìn)路，對(duì)于終到列車來說為入段作業(yè).

本文假設(shè)一旦確定了列車占用的到發(fā)線，則其所對(duì)應(yīng)的接車（出段）進(jìn)路和發(fā)車（入段）進(jìn)路也是固定的.

圖1 列車車站作業(yè)的Job-Shop抽象Fig.1 Illustration of train operation at a station

2.1 模型基礎(chǔ)

（1）列車開行方案已知，每次列車的種類、到發(fā)時(shí)刻、運(yùn)行方向?yàn)榇_定值（可通過查定列車運(yùn)行圖獲得）.

（2）不同車場(chǎng)的到發(fā)線使用方案已知，列車技術(shù)作業(yè)內(nèi)容、作業(yè)順序，以及每項(xiàng)作業(yè)的最短時(shí)間及最長(zhǎng)時(shí)間為確定值（可通過查定《站細(xì)》獲得）.

（3）各個(gè)進(jìn)路與到發(fā)線之間的關(guān)系已知，可以通過查定車站平面圖，建立進(jìn)路與到發(fā)線之間的連通關(guān)系.

2.2 模型設(shè)計(jì)

首先根據(jù)列車時(shí)刻表，將列車i的車站作業(yè)形式化為活動(dòng)時(shí)間鏈對(duì)于始發(fā)、終到和通過列車只有其唯一對(duì)應(yīng)的作業(yè)時(shí)間鏈，需要強(qiáng)調(diào)兩種特殊情況：

（1）對(duì)于轉(zhuǎn)線折返列車，按兩個(gè)作業(yè)活動(dòng)時(shí)間鏈分別計(jì)算；

（2）對(duì)于立折列車，可將兩個(gè)列車合并成一個(gè)作業(yè)時(shí)間鏈考慮.

2.2.1 參數(shù)定義

l——到發(fā)線索引；

T(k)——車站k內(nèi)部的股道集合；

i,j——列車索引，j表示列車i的后續(xù)列車；

θi——列車i所占用的到發(fā)線的編號(hào)；

(i,m)——列車i的第m道工序；

jobi——列車i的車站作業(yè)表示列車經(jīng)由咽喉準(zhǔn)備進(jìn)入到發(fā)線，即m=1；表示列車占用到發(fā)線作業(yè)，即m=2表示列車轉(zhuǎn)出到發(fā)線進(jìn)入咽喉，即m=3；

Si,m——列車i的第m道工序的開始時(shí)間；

Ei,m——列車i的第m道工序的結(jié)束時(shí)間；

Til——列車i占用到發(fā)線l的時(shí)間；

2.2.2 決策變量

（1）二進(jìn)制變量.

（2）連續(xù)變量. ail——列車i進(jìn)入到發(fā)線l的時(shí)間，l∈T(k)；dil——列車i離開到發(fā)線l的時(shí)間，l∈T(k).

2.2.3 目標(biāo)函數(shù)

最小化列車在車站的停站時(shí)間，一般情況下，客運(yùn)站在滿足技術(shù)作業(yè)要求的前提下應(yīng)盡快騰空到發(fā)線.函數(shù)式（1）表示某方案下列車在車站的停站時(shí)間總和，函數(shù)式（2）為本模型的目標(biāo)函數(shù)，最小化列車在車站的停站時(shí)間.

2.2.4 約束條件

安排列車作業(yè)時(shí)需滿足以下約束：

（1）設(shè)備能力約束.在t時(shí)刻，到發(fā)線l只會(huì)被一個(gè)列車占用，

（2）列車作業(yè)分配約束.一列車只能占用一條到發(fā)線，

（3）停站時(shí)間約束.

（4）運(yùn)動(dòng)的連續(xù)性約束.

（5）沖突進(jìn)路約束.

將車站的拓?fù)浣Y(jié)構(gòu)用連接車站各方向邊界和股道的接發(fā)車進(jìn)路表示.任意兩條進(jìn)路間可能會(huì)因?yàn)楣灿靡粋€(gè)道岔或軌道單元而存在空間上的重疊，因此對(duì)于作業(yè)進(jìn)路上存在交叉干擾的作業(yè)，需保證一定的安全間隔時(shí)間.h1表示兩接車進(jìn)路的安全間隔時(shí)間，h2表示兩發(fā)車進(jìn)路的安全間隔時(shí)間，h3表示到發(fā)進(jìn)路沖突的間隔時(shí)間，h4表示發(fā)到進(jìn)路沖突的安全間隔時(shí)間，如圖2—圖4所示.對(duì)于分配在不同到發(fā)線的列車i和j，如果作業(yè)進(jìn)路上存在交叉干擾，也必須保有一定的安全間隔時(shí)間，這里我們認(rèn)為列車i比列車j具有優(yōu)先權(quán).

圖2 敵對(duì)進(jìn)路Fig.2 The confliction between two receiving routes

圖3 到發(fā)、發(fā)到進(jìn)路沖突Fig.3 The confliction between a departure route and a

圖4 發(fā)發(fā)進(jìn)路沖突Fig.4 The confliction between two departure routes

3 基于拉格朗日松弛的車站作業(yè)模型

3.1 車站技術(shù)作業(yè)問題的拉格朗日對(duì)偶松弛問題

將約束（3）松弛，則原問題變成了不考慮設(shè)備能力約束的簡(jiǎn)單問題.拉格朗日乘子法是一種求極值的強(qiáng)有力的方法，本文給定一個(gè)非負(fù)的拉格朗日乘子 λtl，記車站技術(shù)作業(yè)問題的拉格朗日松弛問題為ZLR，描述如下：

原問題的拉格朗日松弛對(duì)偶問題形式如下，記為ZLD：

將拉格朗日松弛對(duì)偶問題（12）分解為兩部分，非正則子問題（14）和正則子問題（15）.當(dāng)給定一組拉格朗日乘子 λtl時(shí)，式（14）為定值.正則子問題可基于不同列車的技術(shù)作業(yè)進(jìn)行分解.

正則子問題可以基于列車分解：

λtl反映了t時(shí)刻占用到發(fā)線l所需要付出的代價(jià)，占用不同的到發(fā)線需要付出相應(yīng)的代價(jià).式（16）的目標(biāo)是確定列車占用的到發(fā)線及其占用時(shí)間，使其占用到發(fā)線所付出的代價(jià)和停站時(shí)間的總和達(dá)到最小.

3.2 次梯度算法優(yōu)化拉格朗日乘子

對(duì)于拉格朗日求解的算法設(shè)計(jì)，Kibardin認(rèn)為部分的最優(yōu)解與整體的最優(yōu)解是基本一致的，提出次梯度算法是求解拉格朗日問題的有效方法[9].可以通過子問題的求解過程得到.

式中 拉格朗日乘子 λtl的初始值為0，上標(biāo)n表示迭代次數(shù).Stl表示拉格朗日乘子 λtl的次梯度方向，如式（18）所示；ηn表示第n次迭代的步長(zhǎng)，可以通過式（19）求出，其中Zˉ表示原問題的期望值，Z表示第n次迭代的結(jié)果，β是步長(zhǎng)調(diào)節(jié)因子.

Stl＞0則說明有多輛列車同時(shí)占用同一條到發(fā)線，價(jià)格上升，下一次迭代的時(shí)候便會(huì)繞開該沖突.

4 高速鐵路車站作業(yè)優(yōu)化算法

step1初始化.

讀取t0時(shí)刻車站到發(fā)線及進(jìn)路占用數(shù)據(jù).構(gòu)建t×l階矩陣 λTL和CTL，矩陣 λTL中元素 λtl表示t時(shí)刻編號(hào)為l股道的拉格朗日乘子值，初始值全部取零.矩陣CTL表示股道被占用的時(shí)間信息，其中ctl表示t時(shí)刻占用編號(hào)為l的股道的列車數(shù)量.

step2安排時(shí)間窗長(zhǎng)度內(nèi)的列車作業(yè).

定義時(shí)間窗長(zhǎng)度為K，根據(jù)時(shí)刻表讀取K時(shí)間內(nèi)需要安排到發(fā)線的列車的信息，確定列車作業(yè)的時(shí)間鏈

step2.1安排通過列車作業(yè).

根據(jù)進(jìn)入車站的先后順序，為通過列車安排進(jìn)路，確定通過列車占用股道的時(shí)間信息，并更新矩陣CTL.

step2.2安排其他列車作業(yè).

根據(jù)列車進(jìn)出車站的先后順序及沖突進(jìn)路約束，搜索列車的所有可行進(jìn)路，在列車i的所有可行進(jìn)路鏈表中，尋找其占用到發(fā)線時(shí)間Til與拉格朗日乘子值之和的最小值Li，確定列車占用股道

的時(shí)間信息，更新矩陣CTL.

step3根據(jù)2.2節(jié)介紹的次梯度算法更新拉格朗日乘子λtl.

step4判斷迭代是否終止.

通常在循環(huán)開始時(shí)β=2，并在循環(huán)過程中逐步減小.在連續(xù)20次的迭代過程中，如果解的質(zhì)量都沒有提高，則令βn+1=0.8βn，n=n+1，進(jìn)入2.2；若連續(xù)100次迭代仍未改善，則終止迭代，獲得初始解（參數(shù)選取參考文獻(xiàn)10）.

step5初始解的可行化.

求解Lagrangean對(duì)偶問題，通過松弛復(fù)雜約束的辦法，相當(dāng)于擴(kuò)大了原問題的可行域，故所得的解不一定是可行解，是一個(gè)好的初始序列.尤其是當(dāng)能力比較緊的時(shí)候，為得到原問題的可行解，這個(gè)時(shí)候需要對(duì)這個(gè)不可行解做可行化處理，例如采用順延沖突任務(wù)的方法，此時(shí)原問題將轉(zhuǎn)化為一個(gè)簡(jiǎn)單的純線性規(guī)劃問題.至此完成了時(shí)間窗內(nèi)所有列車的作業(yè)安排，算法結(jié)束.

5 實(shí)例分析

本文以高速鐵路某一車站為例，以下稱為A站.安排其8：00-9：00的車站技術(shù)作業(yè)，本文規(guī)定所有列車在A站的作業(yè)時(shí)間鏈為

表1 A站8：00-9：00時(shí)刻表Table 1 Train schedule of station A during 8 am-9 am

圖5 A站站場(chǎng)平面圖Fig.5 The planar graph of station A

表2 8:00時(shí)分到發(fā)線占用表 Table 2 The occupancy on arrival and departure tracks at 8 am

采用matlab進(jìn)行求解，求解結(jié)果如表3-表4所示.其中表3代表下行列車的車站技術(shù)作業(yè)，表4表示上行列車的車站技術(shù)作業(yè).對(duì)表1進(jìn)行分析可知，若列車都以最小停站時(shí)間停車，則列車的發(fā)車進(jìn)路會(huì)產(chǎn)生沖突，而本文的模型和算法通過延長(zhǎng)停站時(shí)間，完全疏解了進(jìn)路在空間上的沖突，說明了本文的模型和算法能有效地避免進(jìn)路沖突的問題.

表3 A站8:00—9:00下行列車車站技術(shù)作業(yè)計(jì)劃方案Table 3 Station operation plan for down trains during 8 am-9 am

表4 A站8:00—9:00上行列車車站技術(shù)作業(yè)計(jì)劃方案Table 4 Station operation plan for up trains during 8 am-9am

6 研究結(jié)論

（1）從Job-Shop調(diào)度角度出發(fā)，以列車為待加工的“工件”，將車站接車進(jìn)路、到發(fā)線和發(fā)車進(jìn)路看作“加工機(jī)器”，列車在車站的走行與停站看做不同的“作業(yè)工序”，列車作業(yè)的彼此與獨(dú)立之間具有一定的時(shí)間和空間限制，將車站作業(yè)問題抽象成“機(jī)器、作業(yè)與工序”的優(yōu)化問題.

（2）分析了不同種類列車的車站技術(shù)作業(yè)，以此為基礎(chǔ)建立了車站技術(shù)作業(yè)問題的通用數(shù)學(xué)模型，采用拉格朗日和次梯度理論簡(jiǎn)化該通用模型，并設(shè)計(jì)了車站作業(yè)優(yōu)化模型的求解算法.

（3）以高速鐵路的某一車站為實(shí)例進(jìn)行研究，結(jié)果表明，本文的模型和算法可以有效地避免進(jìn)路沖突問題，并可求得到發(fā)線占用時(shí)間最短的車站作業(yè)方案.本文的研究為高速鐵路車站作業(yè)優(yōu)化問題提供了一種新的思路和途徑.

（4）此外，可將車站作業(yè)優(yōu)化問題作為時(shí)刻表優(yōu)化問題的驗(yàn)算問題，則車站作業(yè)計(jì)劃中關(guān)于列車在站停留時(shí)間最小可作為反饋，重新優(yōu)化時(shí)刻表，如在車站作業(yè)計(jì)劃優(yōu)化條件下得到時(shí)刻表優(yōu)化方案則為整體列車運(yùn)行計(jì)劃的全局優(yōu)化方案.如固定列車時(shí)刻表，則本文的研究可以用于大站到發(fā)線運(yùn)用和調(diào)車作業(yè)相結(jié)合的車站作業(yè)計(jì)劃優(yōu)化方法，得到到發(fā)線占用時(shí)間最小和列車作業(yè)干擾最小的作業(yè)計(jì)劃.

[1]徐杰,杜文.基于遺傳算法的區(qū)段站到發(fā)線運(yùn)用優(yōu)化安排[J].中國(guó)鐵道科學(xué),2003,24(2):109-114.[XU J, DU W.The genetic based algorithms optimization plan of using the arrival and departure track at railway sec?tional station[J].China Railway Science,2003,24(2): 109-114.]

[2]陳彥,史峰.旅客列車過站徑路優(yōu)化模型與算法[J].中國(guó)鐵道科學(xué),2010,31(2):101-106.[CHEN Y,SHI F. Optimization model and algorithm for routing passenger trains through a railway station[J].China Railway Sci?ence,2010,31(2):101-106.]

[3]張英貴,雷定猷.鐵路客運(yùn)站股道運(yùn)用窗時(shí)排序模型與算法[J].鐵道學(xué)報(bào),2011,33(1):1-7.[ZHANG Y G, LEI D Y.Due windows scheduling model and algorithm of track utilization in railway passenger stations[J].Jour?nal of the China Railway Society,2011,33(1):1-7.]

[4]謝楚農(nóng),黎新華.鐵路客運(yùn)站到發(fā)線運(yùn)用優(yōu)化研究[J].中國(guó)鐵道科學(xué),2004,25(5):130-133.[XIE C N,LI X H.Optimization research for utilization of arrival and de?parture tracks in railroad passenger station[J].China Railway Science,2004,25(5):130-133.]

[5]Malachy Carey,Sinead Carville.Scheduling and plat?forming trains at busy complex stations[J].Transportation Research Part A,2003,37：195-224.

[6]Partha Chakroborty,Durgesh Vikram.Optimum assign?ment of trains to platforms under partial schedule com?pliance[J].Transportation Science,2008,42:169-184.

[7]Joaqu?'n Rodriguez.A constraint programming model for real-time trains scheduling at junctions[J].Transporta?tion Science 37:213-222.

[8]Richard Freling,Ramon M Lentink,Leo G Kroon,et al. Shunting of passenger train unitsin a railway station[J]. Transportation Science,2005,39(2):261-272.

[9]Kibardin V M.Decomposition into functions in the mini?mization problem[J].Automation and Remote Control，1980，40(8)：1311-1323.

[10]Diaby M,Bahl H C,Karwan M H,et a1.A Lagrangean relaxation approach for very-large-scale capacitated lot-sizing[J].Management Science,1992，38(2):1329-1340.

A Lagrangian Relaxation Model for High-speed Railway Station Operation Optimization

BAI Zi-xi,ZHOU Lei-shan,WANG Jin,GUO Bin
(School of Traffic and Transportation,Beijing Jiaotong University,Beijing 100044,China)

ract:This paper applies the Job-Shop scheduling theory to station operation optimization of highspeed railway.In this study,trains are regarded as workpieces,the arrival-departure tracks,inbound and outbound road are regarded as machines,trains’operations at a station are treated as different works.In this way,the station operation optimization problem can be transformed into a special kind of job-shop problem. The study takes the station equipment capacity,conflicts in inbound road and outbound road,station dwell time as the space and time constraints.The optimization goal is to minimize dwell time of trains.,Then,the paper develops the high-speed railway station operation optimization model and the corresponding Lagrangian relaxation model of station operation.The optimization algorithm is also proposed for high-speed railway station technique operation.A real high-speed railway station case shows that the model and algorithm are able to generate the optimization plan for high-speed railway station operation and they can effectively eliminate the conflicts in inbound road and outbound road.

railway transportation;station operation optimization;Job-Shop;lagrangian relaxation;subgradient

1009-6744（2014）04-0120-06

U292.1

A

2013-11-25

2014-03-11錄用日期：2014-03-18

國(guó)家科技支撐計(jì)劃(2009BAG12A10-7)；鐵道部科技司項(xiàng)目（2012X011-C）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助（2013YJS046）.

白紫熙（1988-），女，山西晉城人，博士生. *

lshzhou@bjtu.edu.cn