高速鐵路列車(chē)運(yùn)行圖與動(dòng)車(chē)組運(yùn)用一體化優(yōu)化模型與算法研究

王 超，王淑姍，王 鵬，王小京，陳 磊

（1.中國(guó)鐵路總公司 運(yùn)輸統(tǒng)籌監(jiān)督局，北京 100844；2.北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京100044；3.中國(guó)鐵路呼和浩特局集團(tuán)有限公司 概預(yù)算審查所，內(nèi)蒙古 呼和浩特 010057；4.中國(guó)鐵路呼和浩特局集團(tuán)有限公司 調(diào)度所，內(nèi)蒙古 呼和浩特 010057)

高速鐵路列車(chē)運(yùn)行圖和動(dòng)車(chē)組交路計(jì)劃是高速鐵路運(yùn)輸組織的重要組成，是鐵路組織列車(chē)開(kāi)行的基礎(chǔ)。高速鐵路列車(chē)運(yùn)行圖規(guī)定了列車(chē)開(kāi)行計(jì)劃，動(dòng)車(chē)組運(yùn)用規(guī)定了動(dòng)車(chē)組交路計(jì)劃，因而應(yīng)統(tǒng)籌考慮列車(chē)開(kāi)行計(jì)劃和動(dòng)車(chē)組交路計(jì)劃，以最少的動(dòng)車(chē)組運(yùn)用，達(dá)到列車(chē)開(kāi)行數(shù)量的最大化，實(shí)現(xiàn)列車(chē)運(yùn)行圖和動(dòng)車(chē)組運(yùn)用的一體化優(yōu)化。從目前研究情況看，列車(chē)運(yùn)行圖與動(dòng)車(chē)組交路計(jì)劃都是分別優(yōu)化，即：列車(chē)運(yùn)行圖的優(yōu)化，一般不考慮動(dòng)車(chē)組交路計(jì)劃的編制；而動(dòng)車(chē)組交路計(jì)劃的優(yōu)化，一般將運(yùn)行圖作為已知輸入條件，很少有研究將兩者同步考慮、同步優(yōu)化[1-2]。在動(dòng)車(chē)組不固定運(yùn)用的條件下，一旦遇到突發(fā)情況，高速鐵路列車(chē)運(yùn)行圖結(jié)構(gòu)將發(fā)生較大變化，可能會(huì)導(dǎo)致該運(yùn)行圖對(duì)應(yīng)的最優(yōu)動(dòng)車(chē)組運(yùn)用計(jì)劃隨之改變，最終會(huì)影響動(dòng)車(chē)組的使用數(shù)量和運(yùn)用效率。如果能夠科學(xué)運(yùn)用優(yōu)化方法，及時(shí)調(diào)整動(dòng)車(chē)組交路計(jì)劃，可以節(jié)省動(dòng)車(chē)組運(yùn)用，有效提升運(yùn)輸效率效益。通過(guò)對(duì)列車(chē)運(yùn)行圖優(yōu)化與動(dòng)車(chē)組運(yùn)用優(yōu)化進(jìn)行一體化考慮，研究在列車(chē)開(kāi)行對(duì)數(shù)一定的條件下，如何實(shí)現(xiàn)車(chē)底運(yùn)用數(shù)量最小這一目標(biāo)[3]。

1 高速鐵路列車(chē)運(yùn)行圖與動(dòng)車(chē)組運(yùn)用一體化優(yōu)化模型

1.1 理論基礎(chǔ)

車(chē)輛路線問(wèn)題(VRP問(wèn)題)最早是由Dantzig和Ramser于1959年首次提出，它是指一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求，配送中心向客戶提供貨物，由一個(gè)車(chē)隊(duì)負(fù)責(zé)分送貨物，組織適當(dāng)?shù)男熊?chē)路線，目標(biāo)是使得客戶的需求得到滿足，并能在一定的約束下，達(dá)到例如路程最短、成本最小、耗費(fèi)時(shí)間最少等目標(biāo)。隨后VRP問(wèn)題由貨物運(yùn)輸擴(kuò)展到旅客運(yùn)輸，最典型的案例是單位巴士接送本單位員工上下班，員工居住于不同地點(diǎn)，需要對(duì)巴士進(jìn)行徑路規(guī)劃。實(shí)際上，動(dòng)車(chē)組在鐵路網(wǎng)的運(yùn)行過(guò)程中，將旅客從O運(yùn)輸?shù)紻，完全可以轉(zhuǎn)化為VRP問(wèn)題。列車(chē)運(yùn)行圖的本質(zhì)是動(dòng)車(chē)組運(yùn)行后留下的軌跡[4]。因此，構(gòu)建高速鐵路列車(chē)運(yùn)行圖與動(dòng)車(chē)組運(yùn)用一體化優(yōu)化模型研究是典型的VRP問(wèn)題[5]。

1.2 符號(hào)說(shuō)明

首先，將列車(chē)運(yùn)行圖與動(dòng)車(chē)組運(yùn)用一體化優(yōu)化模型中需要使用的變量定義如下。

（1）運(yùn)行圖指標(biāo)：A為高速鐵路線路上所有車(chē)站的集合；i，j，k為該線路上的任一車(chē)站，即有i，j，k∈A；t，t'為時(shí)間索引；Bj為列車(chē)在車(chē)站j的總停站次數(shù)，次/d；B為列車(chē)在該線路上的總停站次數(shù)，次/d；C為高速鐵路線路上終點(diǎn)站的集合；D為列車(chē)在中間站的停站時(shí)間標(biāo)準(zhǔn)，min；E為列車(chē)在終點(diǎn)站折返的時(shí)間標(biāo)準(zhǔn)，min；I發(fā)為該線路上列車(chē)的出發(fā)時(shí)間間隔，min；T運(yùn)為列車(chē)在區(qū)間中的純運(yùn)行時(shí)間，min；I到發(fā)為列車(chē)到達(dá)車(chē)站至從車(chē)站出發(fā)的時(shí)間間隔，min；mi-j為車(chē)站i與車(chē)站j在該線路上的實(shí)際距離，km。

（2）動(dòng)車(chē)組運(yùn)用指標(biāo)：N為動(dòng)車(chē)組車(chē)底的最大取值；n為動(dòng)車(chē)組車(chē)底索引，n∈N；ti(n)為編號(hào)為n的動(dòng)車(chē)組車(chē)底從車(chē)站i出發(fā)的時(shí)刻；tj'(n)為編號(hào)為n的動(dòng)車(chē)組車(chē)底到達(dá)車(chē)站j站的時(shí)刻表示動(dòng)車(chē)組車(chē)底n ti(n)時(shí)刻從i站出發(fā)，在tj'(n)時(shí)刻到達(dá)j站；yi表示動(dòng)車(chē)組是否在j站停車(chē)。

1.3 高速鐵路列車(chē)運(yùn)行圖與動(dòng)車(chē)組運(yùn)用一體化模型

動(dòng)車(chē)組運(yùn)用的首要任務(wù)就是能完成給定的運(yùn)行任務(wù)，在此基礎(chǔ)上，區(qū)間運(yùn)行線數(shù)量越多，高速鐵路列車(chē)運(yùn)行圖與動(dòng)車(chē)組運(yùn)用一體化優(yōu)化程度越優(yōu)[6]。因此，在一體化優(yōu)化模型中，通常采用區(qū)間線路數(shù)量最大為優(yōu)化目標(biāo)，即

公式 ⑵ 表示所有的列車(chē)在j站的停站總次數(shù)不大于參數(shù)Bj，其中參數(shù)Bj隨著j車(chē)站的不同而改變。公式 ⑶ 表示所有的列車(chē)在所有車(chē)站的停站總次數(shù)不大于參數(shù)B，其中參數(shù)B隨著車(chē)站集的不同而變化。公式 ⑷ 表示列車(chē)在j站的停站時(shí)間，包括4種情況，即列車(chē)在終點(diǎn)站是否折返(折返時(shí)間標(biāo)準(zhǔn)是E)，以及列車(chē)在中間站是否停車(chē)(停站時(shí)間標(biāo)準(zhǔn)是D)，其中參數(shù)D，E隨著車(chē)站的不同而發(fā)生變化。公式 ⑸ 表示避免列車(chē)的車(chē)站間隔時(shí)間小于最小間隔時(shí)間，即當(dāng)列車(chē)的時(shí)空路徑經(jīng)過(guò)一個(gè)點(diǎn)時(shí)，與該點(diǎn)的間隔時(shí)間不滿足最小間隔時(shí)間的相鄰點(diǎn)都不能被其他的列車(chē)時(shí)空路徑所占用[7]。公式 ⑹ 表示動(dòng)車(chē)組車(chē)底n在車(chē)站間的純運(yùn)行時(shí)間之和。公式 ⑺ 表示動(dòng)車(chē)組車(chē)底n的停站時(shí)間之和。公式 ⑻ 表示動(dòng)車(chē)組車(chē)底n的總運(yùn)行時(shí)間不可超過(guò)48 h。公式 ⑼ 表示動(dòng)車(chē)組車(chē)底n的總運(yùn)行公里數(shù)不超過(guò)4 000 km。此外，規(guī)定動(dòng)車(chē)組在線路上運(yùn)行的時(shí)間是6 : 00—24 : 00。

2 高速鐵路列車(chē)運(yùn)行圖與動(dòng)車(chē)組運(yùn)用一體化優(yōu)化模型求解

由于研究模型是單目標(biāo)模型，包括多個(gè)車(chē)站，具有一定規(guī)模，為了驗(yàn)證高速鐵路列車(chē)運(yùn)行圖與動(dòng)車(chē)組運(yùn)用一體化優(yōu)化模型及求解方法的正確性和適應(yīng)性，通過(guò)構(gòu)建案例，運(yùn)用GAMS軟件對(duì)模型進(jìn)行求解。

2.1 基礎(chǔ)數(shù)據(jù)

假設(shè)線路i-j-k為雙線鐵路，專門(mén)用于高速鐵路旅客列車(chē)運(yùn)行。其中i表示動(dòng)車(chē)段所所在站，j，k為普通高速鐵路車(chē)站，線路i-j-k簡(jiǎn)化示意圖如圖1所示。

圖1 線路i-j-k簡(jiǎn)化示意圖Fig.1 Simplified schematic diagram of route i-j-k

動(dòng)車(chē)組在中間站j站的停站時(shí)間標(biāo)準(zhǔn)為1 min；運(yùn)用動(dòng)車(chē)組數(shù)量為2組，i站共發(fā)送13列動(dòng)車(chē)組，j站共發(fā)送10列動(dòng)車(chē)組，k站共發(fā)送13列動(dòng)車(chē)組；第1列動(dòng)車(chē)組的發(fā)車(chē)時(shí)間為6 : 11；最后一列動(dòng)車(chē)組的到達(dá)時(shí)間為23 : 57；列車(chē)的最小追蹤間隔時(shí)間為80 min；動(dòng)車(chē)組在終點(diǎn)站的最小停站時(shí)間為20 min。列車(chē)在區(qū)間的純運(yùn)行時(shí)間T運(yùn)如表1所示。

表1 列車(chē)在區(qū)間之間的運(yùn)行時(shí)間T運(yùn) minTab.1 Train running time TYun in the section

滿足上述要求的前提下，考慮實(shí)際旅客的出行需求，可以得出一個(gè)列車(chē)時(shí)刻表。根據(jù)列車(chē)時(shí)刻表可以編制出列車(chē)運(yùn)行圖，線路i-j-k的列車(chē)運(yùn)行圖如圖2所示。根據(jù)圖2給定的列車(chē)運(yùn)行圖，以及只能在車(chē)站i進(jìn)行日常檢修和定期檢修的已知條件，得到動(dòng)車(chē)組周轉(zhuǎn)計(jì)劃如圖3所示。直接在列車(chē)運(yùn)行圖上勾畫(huà)動(dòng)車(chē)組運(yùn)用方案如圖4所示。

統(tǒng)計(jì)線路i-j-k上各車(chē)站的停站次數(shù)，i站為13次/d，j站為10次/d，k站為13次/d。

2.2 算例說(shuō)明

根據(jù)實(shí)際情況，假設(shè)動(dòng)車(chē)組在終點(diǎn)站的停站時(shí)間標(biāo)準(zhǔn)為15 min，即E= 15 min；動(dòng)車(chē)組在中間站j站的停站時(shí)間標(biāo)準(zhǔn)為1 min，即D= 1 min；列車(chē)的追蹤間隔時(shí)間為60 min，即I發(fā)= 60 min；第一列動(dòng)車(chē)組的出發(fā)時(shí)間為6 : 11，即ti(1) = 6 : 11；考慮每天的天窗時(shí)間，僅以6 : 00—24 : 00時(shí)間段為例，用GAMS求解出線路i-j-k的列車(chē)時(shí)刻表。首次輸入運(yùn)用的動(dòng)車(chē)組數(shù)量為2組；列車(chē)在該線路上車(chē)站i與車(chē)站j之間的距離mi-j為70 km，mi-k為40 km；列車(chē)在區(qū)間之間的運(yùn)行時(shí)間T運(yùn)如表1所示；設(shè)定列車(chē)在每個(gè)車(chē)站的總停站次數(shù)最大值i站為16次/d，j站為12次/d，k站為16次/d。

圖2 線路i-j-k的列車(chē)運(yùn)行圖Fig.2 Train working diagram of route i-j-k

圖4 動(dòng)車(chē)組運(yùn)用方案Fig.4 EMU operation plan

2.3 模型求解

編寫(xiě)GAMS程序代碼，在GAMS軟件運(yùn)行以上模型，可求解得到結(jié)果。根據(jù)上述數(shù)據(jù)，可知運(yùn)用動(dòng)車(chē)組數(shù)量為2組，i站共發(fā)送16列動(dòng)車(chē)組，j站共發(fā)送12列動(dòng)車(chē)組，k站共發(fā)送13列動(dòng)車(chē)組，可以滿足實(shí)際情況。

當(dāng)動(dòng)車(chē)組數(shù)量減少為1組時(shí)，i站共發(fā)送10列動(dòng)車(chē)組，j站共發(fā)送10列動(dòng)車(chē)組，k站共發(fā)送10列動(dòng)車(chē)組，其動(dòng)車(chē)組運(yùn)用方案(運(yùn)用動(dòng)車(chē)組數(shù)量為1組)如圖5所示，不符合實(shí)際情況，即不可以滿足i站共發(fā)送13列動(dòng)車(chē)組，k站共發(fā)送13列動(dòng)車(chē)組的實(shí)際情況。

由此輸出當(dāng)動(dòng)車(chē)組為2組時(shí)的數(shù)據(jù)，即運(yùn)用動(dòng)車(chē)組數(shù)量為2組時(shí)，線路i-j-k的列車(chē)時(shí)刻表。將GMAS輸出的表格鋪畫(huà)到十分格運(yùn)行圖上，得到動(dòng)車(chē)組運(yùn)用方案(運(yùn)用動(dòng)車(chē)組數(shù)量為2組)如圖6所示。其中的動(dòng)車(chē)組運(yùn)行軌跡可構(gòu)成高速鐵路列車(chē)運(yùn)行圖(運(yùn)用動(dòng)車(chē)組數(shù)量為2組)如圖7所示。

上述案例說(shuō)明，可以運(yùn)用GAMS軟件編寫(xiě)代碼[8]，求解線路i-j-k的高速鐵路列車(chē)運(yùn)行圖與動(dòng)車(chē)組運(yùn)用一體化優(yōu)化模型，并得到最優(yōu)化方案[9]。

2.4 算例分析

京津城際全長(zhǎng)120 km，共5個(gè)站，包括北京南、亦莊(未開(kāi)通)、永樂(lè)(未開(kāi)通)、武清及天津站。由于上述5個(gè)車(chē)站中亦莊和永樂(lè)站還未開(kāi)通，因而在研究動(dòng)車(chē)組運(yùn)用時(shí)不予考慮，只考慮有列車(chē)到發(fā)作業(yè)的車(chē)站。北京南站有北京動(dòng)車(chē)段、天津站有天津曹莊動(dòng)車(chē)運(yùn)用所，在此基礎(chǔ)上，可以將京津城際進(jìn)行簡(jiǎn)化，京津城際簡(jiǎn)化線路示意圖如圖8所示。

圖5 動(dòng)車(chē)組運(yùn)用方案(運(yùn)用動(dòng)車(chē)組數(shù)量為1組)Fig.5 EMU operation plan (the number of EMU is 1 unit)

圖6 動(dòng)車(chē)組運(yùn)用方案(運(yùn)用動(dòng)車(chē)組數(shù)量為2組)Fig.6 EMU operation plan (the number of EMU is 2 units)

圖7 高速鐵路列車(chē)運(yùn)行圖(運(yùn)用動(dòng)車(chē)組數(shù)量為2組)Fig.7 High speed train working diagram (the number of EMU is 2 units)

圖8 京津城際簡(jiǎn)化線路示意圖Fig.8 Simplified route schematic diagram of Beijing-Tianjin intercity railway

以京津城際為研究對(duì)象，可用動(dòng)車(chē)組數(shù)量為9組，編寫(xiě)GAMS程序代碼，并運(yùn)行以上模型，可求解得到結(jié)果，即京津城際動(dòng)車(chē)組運(yùn)用方案(運(yùn)用動(dòng)車(chē)組數(shù)量為9組)如圖9所示。北京南站共發(fā)送80列動(dòng)車(chē)組，武清站共發(fā)送48列動(dòng)車(chē)組，天津站共發(fā)送78列動(dòng)車(chē)組。

比較目前京津城際實(shí)際列車(chē)運(yùn)行圖，在運(yùn)用相同動(dòng)車(chē)組數(shù)量的前提下，一體化優(yōu)化方案可多發(fā)6列車(chē)，從而為實(shí)際列車(chē)運(yùn)行圖鋪畫(huà)提供一定參考。

3 結(jié)束語(yǔ)

隨著我國(guó)社會(huì)經(jīng)濟(jì)快速發(fā)展，旅客出行需求逐年增加。目前，我國(guó)京滬(北京南—上海虹橋)、京廣(北京西—廣州南)等高速鐵路繁忙干線運(yùn)輸能力逐步趨于飽和，同時(shí)每年需要投入大量資金增加動(dòng)車(chē)組采購(gòu)數(shù)量，對(duì)列車(chē)開(kāi)行和動(dòng)車(chē)組運(yùn)用兩者進(jìn)行同步優(yōu)化，以最少的動(dòng)車(chē)組實(shí)現(xiàn)列車(chē)開(kāi)行數(shù)量的最大化，對(duì)于提高運(yùn)輸能力、節(jié)約動(dòng)車(chē)組運(yùn)用、提升運(yùn)輸效率效益，具有重要的實(shí)用價(jià)值和社會(huì)經(jīng)濟(jì)效益。研究雖然構(gòu)建了一體化模型，但受數(shù)據(jù)搜集、運(yùn)算工具等條件限制，僅以京津城際為例進(jìn)行了算例驗(yàn)證，后續(xù)一方面需要結(jié)合不同的路網(wǎng)規(guī)模、列車(chē)開(kāi)行需求、客流需求、動(dòng)車(chē)組類(lèi)型等條件對(duì)模型進(jìn)一步補(bǔ)充和完善，使之更加貼近高速鐵路運(yùn)營(yíng)實(shí)際。另一方面，隨著路網(wǎng)規(guī)模的擴(kuò)大，計(jì)算過(guò)程將變得更加復(fù)雜，需要對(duì)算法進(jìn)一步簡(jiǎn)化和深度優(yōu)化，以取得較優(yōu)的運(yùn)算結(jié)果[10]。

圖9 京津城際動(dòng)車(chē)組運(yùn)用方案(運(yùn)用動(dòng)車(chē)組數(shù)量為9組)Fig.9 EMU operation plan of Beijing-Tianjin intercity railway (the number of EMU is 9 units)