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

（北京交通大學交通運輸學院，北京100044）

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

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

（北京交通大學交通運輸學院，北京100044）

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

2.1 模型基礎

（1）列車開行方案已知，每次列車的種類、到發(fā)時刻、運行方向為確定值（可通過查定列車運行圖獲得）.

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

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

2.2 模型設計

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

（1）對于轉線折返列車，按兩個作業(yè)活動時間鏈分別計算；

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

2.2.1 參數(shù)定義

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

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

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

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

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

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

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

Ei,m——列車i的第m道工序的結束時間；

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

2.2.2 決策變量

（1）二進制變量.

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

2.2.3 目標函數(shù)

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

2.2.4 約束條件

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

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

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

（3）停站時間約束.

（4）運動的連續(xù)性約束.

（5）沖突進路約束.

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

圖2 敵對進路Fig.2 The confliction between two receiving routes

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

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

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

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

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

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

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

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

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

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

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

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

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

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

step1初始化.

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

step2安排時間窗長度內的列車作業(yè).

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

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

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

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

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

的時間信息，更新矩陣CTL.

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

step4判斷迭代是否終止.

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

step5初始解的可行化.

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

5 實例分析

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

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

圖5 A站站場平面圖Fig.5 The planar graph of station A

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

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

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

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

6 研究結論

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

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

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

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

[1]徐杰,杜文.基于遺傳算法的區(qū)段站到發(fā)線運用優(yōu)化安排[J].中國鐵道科學,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].中國鐵道科學,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]張英貴,雷定猷.鐵路客運站股道運用窗時排序模型與算法[J].鐵道學報,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]謝楚農,黎新華.鐵路客運站到發(fā)線運用優(yōu)化研究[J].中國鐵道科學,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

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

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

lshzhou@bjtu.edu.cn