徐長(zhǎng)安 ，李晟東 ，李斯涵 ，倪少權(quán) ,2,3

（1.西南交通大學(xué)交通運(yùn)輸與物流學(xué)院，四川 成都 610031；2.西南交通大學(xué)綜合交通運(yùn)輸智能化國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室，四川 成都 610031；3.西南交通大學(xué)綜合交通大數(shù)據(jù)應(yīng)用技術(shù)國(guó)家工程實(shí)驗(yàn)室，四川 成都 610031）

高速鐵路夕發(fā)朝至列車(chē)是我國(guó)鐵路部門(mén)為滿足部分地區(qū)間旅客的夜間出行需求，在普速鐵路夕發(fā)朝至列車(chē)基礎(chǔ)上發(fā)展而來(lái)的一種客運(yùn)產(chǎn)品，通常是指當(dāng)日19∶00—23∶00 始發(fā)，次日06∶00—10∶00 終到，總在途時(shí)間7～15 h 的高速動(dòng)車(chē)組列車(chē).由于高速鐵路夕發(fā)朝至列車(chē)的開(kāi)行需要占據(jù)運(yùn)行圖中的夜間運(yùn)行時(shí)分，會(huì)與天窗設(shè)置產(chǎn)生沖突，使得高鐵夕發(fā)朝至列車(chē)開(kāi)行計(jì)劃編制難度很大.隨著高速鐵路夕發(fā)朝至客流的不斷增長(zhǎng)，實(shí)現(xiàn)高速鐵路夕發(fā)朝至列車(chē)開(kāi)行的網(wǎng)絡(luò)化與日?；?，是順應(yīng)鐵路客運(yùn)市場(chǎng)發(fā)展的必然趨勢(shì).在這種背景下，如何選擇高速鐵路夕發(fā)朝至列車(chē)開(kāi)行模式，并實(shí)行天窗與高速鐵路夕發(fā)朝至列車(chē)的協(xié)同優(yōu)化，是今后高速鐵路夕發(fā)朝至列車(chē)品牌發(fā)展所面臨的重要問(wèn)題.

許多學(xué)者從不同視角分析和研究了高速鐵路夕發(fā)朝至列車(chē)開(kāi)行與天窗設(shè)置協(xié)調(diào)優(yōu)化問(wèn)題，并取得了許多有意義的成果.趙麗珍等[1]以京滬高速鐵路天窗方案設(shè)置為例，首次系統(tǒng)闡釋了高速鐵路列車(chē)開(kāi)行方案與天窗的協(xié)調(diào)優(yōu)化問(wèn)題.朱健梅等[2]深入研究了客運(yùn)專線夕發(fā)朝至列車(chē)合理開(kāi)行時(shí)間域與天窗方案的協(xié)調(diào)優(yōu)化問(wèn)題，并指出單向隔日矩形天窗是我國(guó)客運(yùn)專線天窗設(shè)置的較優(yōu)方案.聶磊等[3]在分析客運(yùn)專線矩形天窗開(kāi)設(shè)與夜間行車(chē)相互影響的基礎(chǔ)上，建立線性規(guī)劃模型求解最佳矩形天窗位置.楊奎等[4]通過(guò)分析高速鐵路綜合維修天窗與夜間運(yùn)行列車(chē)之間的動(dòng)態(tài)影響關(guān)系，構(gòu)建了天窗設(shè)置與夜間列車(chē)開(kāi)行的協(xié)同優(yōu)化模型.李博[5]研究了成網(wǎng)條件下高速鐵路夕發(fā)朝至列車(chē)開(kāi)行方案編制關(guān)鍵問(wèn)題，提出了等天窗模式下的高速鐵路夕發(fā)朝至列車(chē)開(kāi)行方案編制理論與方法.Zhang 等[6]基于通道型高速鐵路提出了列車(chē)運(yùn)行方案與天窗設(shè)置的一體化編制模型.徐長(zhǎng)安等[7]設(shè)計(jì)了基于優(yōu)化進(jìn)程分層的兩階段算法，求解天窗與列車(chē)運(yùn)行圖協(xié)同優(yōu)化問(wèn)題.

然而，既有研究多是基于列車(chē)開(kāi)行模式已知情況，少有研究考慮列車(chē)開(kāi)行模式未定情形下天窗設(shè)置與列車(chē)運(yùn)行圖的協(xié)同優(yōu)化.本文以通道型高速鐵路為研究對(duì)象，引入狀態(tài)變量來(lái)刻畫(huà)不同類型列車(chē)開(kāi)行模式，進(jìn)而構(gòu)建了高速鐵路夕發(fā)朝至列車(chē)開(kāi)行與天窗設(shè)置協(xié)同優(yōu)化模型，設(shè)計(jì)了基于自適應(yīng)大鄰域搜索的啟發(fā)式求解算法，最后以京廣高速鐵路夕發(fā)朝至列車(chē)開(kāi)行與天窗設(shè)置為例，驗(yàn)證了模型算法的有效性.

1 問(wèn)題描述和參數(shù)說(shuō)明

目前，我國(guó)高速鐵路夕發(fā)朝至列車(chē)主要有3 種開(kāi)行模式：等線模式、下線模式和下線-上線模式[8].等線模式是指夕發(fā)朝至列車(chē)始終在高速鐵路上運(yùn)行，遇到天窗則在車(chē)站待避，等天窗結(jié)束后繼續(xù)運(yùn)行.下線模式指夕發(fā)朝至列車(chē)在高速鐵路運(yùn)行一段距離后，為了避開(kāi)天窗，轉(zhuǎn)線至平行普速鐵路繼續(xù)運(yùn)行，直至結(jié)束.下線-上線模式是指夕發(fā)朝至列車(chē)在高速鐵路上運(yùn)行一段時(shí)間后，為了避開(kāi)天窗，轉(zhuǎn)線至平行普速鐵路運(yùn)行，等天窗結(jié)束后，又從普速鐵路轉(zhuǎn)線至高速鐵路繼續(xù)運(yùn)行的過(guò)程.圖1 給出了3 種天窗開(kāi)設(shè)模式在時(shí)空網(wǎng)絡(luò)圖中的對(duì)應(yīng)表示，圖中：s1～s7為車(chē)站；i1、i2為高鐵夕發(fā)朝至列車(chē)；圖中實(shí)線表示在高速鐵路上運(yùn)行，虛線表示在普速鐵路上運(yùn)行，陰影部分表示天窗.由于高速鐵路列車(chē)轉(zhuǎn)線至普速鐵路運(yùn)行后，運(yùn)行速度不能超過(guò)普速鐵路設(shè)計(jì)速度，因此，圖1 中虛線的斜率小于實(shí)線的斜率.

圖1 高速鐵路夕發(fā)朝至列車(chē)開(kāi)行模式Fig.1 Overnight train operation modes of high-speed railways

高速鐵路夕發(fā)朝至列車(chē)與天窗協(xié)同優(yōu)化主要解決兩個(gè)層面的問(wèn)題：一是根據(jù)線路條件與線路能力利用情況，確定選擇何種類型的高速鐵路夕發(fā)朝至列車(chē)開(kāi)行模式.二是在選定列車(chē)開(kāi)行模式后，如何安排天窗與列車(chē)在列車(chē)運(yùn)行圖中的位置，使得天窗對(duì)列車(chē)運(yùn)行的影響最小.因此，高速鐵路夕發(fā)朝至列車(chē)與天窗協(xié)同優(yōu)化本質(zhì)上是一個(gè)包含多變量多約束的組合優(yōu)化問(wèn)題.建模涉及的參數(shù)及變量定義如下：

1）常量.S為研究運(yùn)輸通道上所有車(chē)站集合，S=SG∪SP，SG和SP分別為高速鐵路車(chē)站集合和普速鐵路車(chē)站集合.在運(yùn)輸通道內(nèi)，部分高速鐵路車(chē)站和普速鐵路車(chē)站通過(guò)聯(lián)絡(luò)線相連，具備高速鐵路列車(chē)轉(zhuǎn)線的可能，定義這類車(chē)站為關(guān)鍵車(chē)站，記為SK.IG、IP分別為高速鐵路列車(chē)集合與普速鐵路列車(chē)集合.IX、IR分別為高速鐵路夕發(fā)朝至列車(chē)集合和高速鐵路日間開(kāi)行列車(chē)集合，則有IX?IG，IR?IG.ti(s,s+1)為列車(chē)i在區(qū)間 (s,s+1) 的運(yùn)行時(shí)間，s為車(chē)站.Δta,a、Δtd,d、Δta,d和 Δtd,a分別為同方向列車(chē)同時(shí)到達(dá)、同時(shí)發(fā)車(chē)、不同時(shí)到發(fā)和不同時(shí)發(fā)到最小間隔時(shí)間[7].δs為車(chē)站s的到發(fā)線數(shù)目.zi,s為列車(chē)i在車(chē)站s的最小停站時(shí)間.分別為列車(chē)i在車(chē)站s的合理出發(fā)時(shí)間范圍、合理到達(dá)時(shí)間范圍.設(shè)DG={D1,D2,···,Dn} 為高速線路的n個(gè)天窗分段的集合，當(dāng)n=1 時(shí)表示開(kāi)設(shè)全線垂直矩形天窗.天窗分段可以用車(chē)站集合表示，出現(xiàn)在相鄰兩個(gè)天窗分段中的車(chē)站稱為相鄰天窗分段的分界站，分界站必屬于關(guān)鍵車(chē)站.對(duì)任意的Dj，Dj+1∈DG，當(dāng)=1時(shí)，Dj和Dj+1為相鄰天窗分段，該車(chē)站為Dj和Dj+1的分界站.τb,j、τe,j分別為天窗分段Dj對(duì)應(yīng)的天窗最早開(kāi)始時(shí)間和最晚結(jié)束時(shí)間.Tm為天窗開(kāi)設(shè)時(shí)長(zhǎng)，ΔTm,b、ΔTm,e分別為天窗開(kāi)始前和天窗結(jié)束后安全間隔.ζ 為足夠大的正數(shù).

2）狀態(tài)變量.ρi,s表示當(dāng)列車(chē)運(yùn)行線與天窗發(fā)生沖突時(shí)，列車(chē)i在高速鐵路線路上是否從車(chē)站s運(yùn)行到車(chē)站s+1，取值1 表示是，取值0 表示否.表示當(dāng)列車(chē)運(yùn)行線與天窗發(fā)生沖突時(shí)，列車(chē)i在車(chē)站s是否等線，取值1 表示是，取值0 表示否.表示當(dāng)列車(chē)運(yùn)行線與天窗發(fā)生沖突時(shí)，列車(chē)i是否從車(chē)站s轉(zhuǎn)到普速鐵路運(yùn)行，取值1 表示是，取值0表示否.=1 表示在列車(chē)運(yùn)行線與天窗發(fā)生沖突時(shí)，列車(chē)i在車(chē)站s是否從普速鐵路轉(zhuǎn)到高速鐵路線運(yùn)行，取值1 表示是，取值0 表示否.xi,s為列車(chē)i在車(chē)站s是否停站，取值為1 表示停站，反之表示通過(guò).

3）決策變量.ti,s,c、ti,s,d分別為列車(chē)i在車(chē)站s的出發(fā)時(shí)間、到達(dá)時(shí)間.Tm,j為第j個(gè)天窗分段對(duì)應(yīng)的天窗開(kāi)設(shè)時(shí)段.tj,b，tj,e分別為第j個(gè)天窗分段對(duì)應(yīng)的天窗開(kāi)始時(shí)間和結(jié)束時(shí)間，則Tm,j=[tj,b,tj,e].vi1,i2,s表示列車(chē)i1是否比列車(chē)i2更早從車(chē)站s出發(fā)，取值1 表示是，取值0 表示否.

2 模型構(gòu)建

2.1 模型假設(shè)

本文研究基于以下前提進(jìn)行：

1）高速鐵路夕發(fā)朝至列車(chē)開(kāi)行方案、停站方案以及各類作業(yè)時(shí)間標(biāo)準(zhǔn)均已知；

2）高速鐵路在夜間00∶00—06∶00 開(kāi)設(shè)分段矩形天窗，天窗分段劃分情況視為已知條件；

3）高速鐵路線路各個(gè)天窗分段時(shí)長(zhǎng)相同，且各個(gè)天窗分段時(shí)長(zhǎng)具有整體性，不能分割；

4）由于普速鐵路天窗設(shè)置比較靈活，在夕發(fā)朝至列車(chē)下線運(yùn)行時(shí)，不考慮對(duì)普速鐵路天窗的影響；

5）相較于列車(chē)運(yùn)行時(shí)間，夕發(fā)朝至列車(chē)通過(guò)銜接站下線或者上線都時(shí)間都很短，可忽略不計(jì)；

6）考慮高速鐵路夕發(fā)朝至列車(chē)的到發(fā)時(shí)間段，設(shè)定本文研究時(shí)間范圍為[19∶00，10∶00].

2.2 約束條件

1）列車(chē)合理到發(fā)時(shí)刻約束

為給旅客出行提供最大便利，夕發(fā)朝至列車(chē)在始發(fā)站的出發(fā)時(shí)間和在終到站的到達(dá)時(shí)間，以及在中間大站的到發(fā)時(shí)間均應(yīng)處在合理時(shí)間范圍內(nèi)[7]，表示為式（1）、（2）所示.

2）區(qū)間運(yùn)行時(shí)分約束

夕發(fā)朝至列車(chē)i在車(chē)站s與車(chē)站s+1 構(gòu)成區(qū)間的運(yùn)行時(shí)分等于列車(chē)到達(dá)車(chē)站s+1 的時(shí)間與列車(chē)從車(chē)站s出發(fā)的時(shí)間之差[7]，如式（3）所示.

3）列車(chē)停站時(shí)間約束

夕發(fā)朝至列車(chē)在車(chē)站的停站時(shí)間不能小于規(guī)定的最小停站時(shí)間要求[5,7]，如式（4）所示.

4）列車(chē)間隔時(shí)間約束

夕發(fā)朝至列車(chē)在車(chē)站的到達(dá)、出發(fā)以及通過(guò)均需滿足一定的時(shí)間間隔要求[7]，如式（5）～（9）所示.

5）車(chē)站能力約束

在任意時(shí)刻t，車(chē)站被占用的到發(fā)線數(shù)量不能超過(guò)該站到發(fā)線能力[5].則車(chē)站到發(fā)線能力約束為

式中：i∈IX，s∈S；ω(ti,s,d,t) 和ω(ti,s,c,t) 為0-1 變量，分別表示車(chē)站s的到發(fā)線在時(shí)刻t是否被列車(chē) 占用，取1 表示被占用，反之表示未被占用，具體定義如式（11）、（12）所示.

6）列車(chē)運(yùn)行與天窗安全間隔約束

對(duì)天窗分段Dj，其天窗開(kāi)始時(shí)刻和結(jié)束時(shí)刻均需與列車(chē)運(yùn)行保持一定的安全間隔[7]，以確保行車(chē)安全，如式（13）、（14）所示.

式（13）、（14）中：i∈IX,j∈{1,2,···,n} ,s∈SG.

7）天窗時(shí)間范圍約束

天窗開(kāi)設(shè)需滿足一定的時(shí)間范圍要求[7]，如式（15）、（16）所示.

式（15）、（16）中：j∈{1,2,···,n}，s∈SG.

式（15）表示天窗分段Dj的開(kāi)設(shè)需在規(guī)定的天窗最早開(kāi)始時(shí)間和最晚結(jié)束時(shí)間內(nèi).式（16）表示天窗結(jié)束時(shí)間等于天窗開(kāi)始時(shí)間與天窗時(shí)長(zhǎng)之和.

8）關(guān)鍵車(chē)站等價(jià)約束

由于本文假定列車(chē)在關(guān)鍵車(chē)站的轉(zhuǎn)線時(shí)間忽略不計(jì)，因此，列車(chē)在關(guān)鍵車(chē)站的到發(fā)時(shí)刻滿足式（17）、（18）所示等價(jià)約束.

式（17）、（18）中：i∈IX,s1∈(SG∪SK),s2∈ (SP∪SK).

9）列車(chē)開(kāi)行模式選擇約束

當(dāng)夕發(fā)朝至列車(chē)在高速鐵路運(yùn)行，若在某個(gè)備選關(guān)鍵節(jié)點(diǎn)對(duì)應(yīng)的天窗區(qū)段，其到發(fā)時(shí)間與天窗時(shí)間存在潛在沖突時(shí)，夕發(fā)朝至列車(chē)可選擇等線模式或者下線模式運(yùn)行.圖2 表示夕發(fā)朝至列車(chē)i與天窗分段Dj存在潛在的時(shí)間沖突，列車(chē)i可以選擇等線或者下線運(yùn)行，分別對(duì)應(yīng)或者.則對(duì)應(yīng)如式（19）所示的列車(chē)開(kāi)行模式選擇約束.

圖2 沖突情形下列車(chē)模式選擇Fig.2 Mode selection of train in case of conflict

式中：φ (Tm,j,Ti) 為夕發(fā)朝至列車(chē)到發(fā)時(shí)間與天窗時(shí)間沖突判斷函數(shù)，取值為1 表示存在沖突，取值為0 表示不存在沖突，其中：Ti=[ti,s,c,ti,s+1,d].

同理，當(dāng)高速鐵路夕發(fā)朝至列車(chē)在普速鐵路運(yùn)行，若在某個(gè)關(guān)鍵車(chē)站對(duì)應(yīng)的天窗區(qū)段，其列車(chē)運(yùn)行時(shí)間與高速鐵路天窗沒(méi)有沖突，則夕發(fā)朝至列車(chē)可由普速鐵路上線至高速鐵路運(yùn)行，對(duì)應(yīng)約束如式（20）所示.

10）狀態(tài)變量約束

當(dāng)高速鐵路夕發(fā)朝至列車(chē)在備選關(guān)鍵節(jié)點(diǎn)選擇不同的開(kāi)行模式時(shí)，列車(chē)對(duì)應(yīng)的開(kāi)行狀態(tài)會(huì)發(fā)生變化，本文跟列車(chē)開(kāi)行狀態(tài)相關(guān)的變量包括和 ρi,s，它們對(duì)應(yīng)的約束如式（21）～（27）所示.

式（21）～（27）中：ρi,s∈{0,1}，i∈IX，s∈SK.

式（21）表示在每個(gè)備選關(guān)鍵車(chē)站，至多選擇一種列車(chē)開(kāi)行模式.式（22）表示在備選關(guān)鍵車(chē)站，只有在 ρi,s-1=1 與 ρi,s=1 同時(shí)滿足的情況下，高速鐵路夕發(fā)朝至列車(chē)才會(huì)選擇等線模式.式（23）表示只有在 ρi,s-1=0 的情況下，高速鐵路夕發(fā)朝至列車(chē)才會(huì)選擇上線模式.式（24）、（25）表示高速鐵路夕發(fā)朝至列車(chē)如果選擇轉(zhuǎn)線開(kāi)行模式，則在轉(zhuǎn)線前后車(chē)站的狀態(tài)變量是不同的.式（26）表示高速鐵路夕發(fā)朝至列車(chē)如果選擇轉(zhuǎn)線模式，則有 ρi,s=0.式（27）表示高速鐵路夕發(fā)朝至列車(chē)如果選擇上線模式，則有 ρi,s=1.

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

本文主要從以下兩個(gè)方面對(duì)高速鐵路夕發(fā)朝至列車(chē)與天窗協(xié)調(diào)優(yōu)化的目標(biāo)進(jìn)行考慮：

1）總的旅行時(shí)間最少

高速鐵路夕發(fā)朝至列車(chē)的開(kāi)行要最大程度滿足旅客出行需求，除了列車(chē)到發(fā)時(shí)間需處在合理范圍以內(nèi)，列車(chē)總的旅行時(shí)間也要盡可能短，以提升客運(yùn)產(chǎn)品競(jìng)爭(zhēng)力和吸引力.高速鐵路夕發(fā)朝至列車(chē)總的旅行時(shí)間可表示為

2）對(duì)既有列車(chē)運(yùn)行圖的影響最小

高速鐵路夕發(fā)朝至列車(chē)的開(kāi)行對(duì)既有列車(chē)運(yùn)行圖的影響主要體現(xiàn)在兩個(gè)方面，一是對(duì)高速鐵路日間開(kāi)行列車(chē)的影響，二是在高速鐵路列車(chē)下線情況下，對(duì)普速鐵路列車(chē)的影響.本文以受影響列車(chē)運(yùn)行線數(shù)量來(lái)刻畫(huà)高速鐵路夕發(fā)朝至列車(chē)開(kāi)行對(duì)既有列車(chē)運(yùn)行圖的影響，則高速鐵路夕發(fā)朝至列車(chē)的開(kāi)行對(duì)既有列車(chē)運(yùn)行圖的影響可表示為

式（29）～（32）中：X、R、P分別為高速鐵路夕發(fā)朝至列車(chē)運(yùn)行線集合、高速鐵路日間列車(chē)運(yùn)行線集合和普速鐵路列車(chē)運(yùn)行線集合；φ1(X,R) 與 φ2(X,P)用來(lái)判定不同類型列車(chē)運(yùn)行線集合之間的影響關(guān)系，若運(yùn)行線集合相交，說(shuō)明存在影響，反之，則不受影響.

綜上，本文模型可表示為

3 求解算法

本文建立的高速鐵路夕發(fā)朝至列車(chē)與天窗協(xié)同優(yōu)化模型是一個(gè)雙目標(biāo)、非線性混合整數(shù)規(guī)劃模型，模型中變量、約束眾多，求解十分復(fù)雜.隨著問(wèn)題規(guī)模的擴(kuò)大，計(jì)算難度呈現(xiàn)指數(shù)增長(zhǎng)，假定某高速鐵路線路備選的轉(zhuǎn)線車(chē)站數(shù)量為nS，則對(duì)任意一趟夕發(fā)朝至列車(chē)而言，對(duì)應(yīng)的列車(chē)開(kāi)行模式至多有 22nS-1種，若夕發(fā)朝至列車(chē)的開(kāi)行數(shù)量為nI，則對(duì)應(yīng)的列車(chē)開(kāi)行與天窗設(shè)置方案共有種.可以看出，若對(duì)式（33）直接求解，難度很大.因此，本文首先采取雙目標(biāo)轉(zhuǎn)換[9]、約束線性化處理、無(wú)約束處理、模型約簡(jiǎn)等策略[10]（具體過(guò)程見(jiàn)附加材料1～4）來(lái)降低模型復(fù)雜度，再結(jié)合高速鐵路夕發(fā)朝至列車(chē)與天窗協(xié)同優(yōu)化問(wèn)題的雙層循環(huán)特性，設(shè)計(jì)了一種基于自適應(yīng)大鄰域搜索（adaptive large neighborhood search algorithm，ALNS）的啟發(fā)式求解算法，算法包括內(nèi)外兩重循環(huán)：內(nèi)循環(huán)由破壞鄰域和修復(fù)鄰域組成，用于進(jìn)行局部搜索；外循環(huán)通過(guò)模擬退火機(jī)制控制，用于解的更新，并能夠根據(jù)算子表現(xiàn)自適應(yīng)調(diào)整算子權(quán)重.基于ALNS 的啟發(fā)式求解算法主要內(nèi)容包括鄰域算子設(shè)計(jì)、自適應(yīng)策略設(shè)計(jì)以及算法終止條件確定等幾個(gè)方面（見(jiàn)附加材料5）.具體求解流程如下：

步驟1初始化算法參數(shù).以現(xiàn)圖中的高速鐵路夕發(fā)朝至列車(chē)與天窗方案作為初始解e0，對(duì)應(yīng)目標(biāo)函數(shù)值為f(e0)，并令初始解為當(dāng)前解e和最優(yōu)解ebest：e0賦予e，e0賦予ebest，f(e0) 賦予f(e)，f(e0)賦予f(ebest).

步驟2初始化全部算子的分?jǐn)?shù)與權(quán)重.將所有算子權(quán)重設(shè)為1，所有算子分?jǐn)?shù)設(shè)為0.

步驟3根據(jù)式（34），從破壞鄰域中選擇一個(gè)刪除算子，得到破壞解，并將從當(dāng)前解中刪除的列車(chē)置于設(shè)定的存儲(chǔ)集合中.該存儲(chǔ)集合包含了所有未安排的列車(chē).

式中：pu為算子u被選中的概率；ωu為算子u的權(quán)重；H為算子的數(shù)量.

步驟4根據(jù)式（34）選擇修復(fù)鄰域中的一個(gè)插入算子，從設(shè)定的存儲(chǔ)集合中選出部分列車(chē)，插入被破壞的解中，得到新解e’.

步驟5計(jì)算新解e’ 的目標(biāo)函數(shù)值并與當(dāng)前解e對(duì)應(yīng)的目標(biāo)函數(shù)值進(jìn)行比較.如果e’ 對(duì)應(yīng)的目標(biāo)函數(shù)值f(e’) 優(yōu)于e對(duì)應(yīng)的目標(biāo)函數(shù)值f(e)，則令e’ 為e，f(e’) 為f(e)；否則，使用模擬退火準(zhǔn)則決定是否接受e’，同時(shí)相應(yīng)更新e和f(e).

步驟6更新全部所選擇算子的分?jǐn)?shù)與權(quán)重.結(jié)合步驟5 中計(jì)算的新解的目標(biāo)函數(shù)值，自適應(yīng)策略部分給出的算子分?jǐn)?shù)計(jì)算規(guī)則進(jìn)行更新[11]，并根據(jù)式（35）更新算子的權(quán)重.

式中：θu為算子u的分?jǐn)?shù)；λ ∈[0,1] 為算子權(quán)重更新參數(shù).

步驟7判斷是否滿足算法終止條件.如果滿足，轉(zhuǎn)步驟8，如果不滿足，轉(zhuǎn)步驟3.

步驟8輸出最優(yōu)解ebest和最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值f(ebest)，算法結(jié)束.

4 算例分析

以京廣高速鐵路夕發(fā)朝至列車(chē)與天窗設(shè)置為例驗(yàn)證本文模型與算法的有效性.京廣高速鐵路全長(zhǎng)2 298 km，包含36 個(gè)車(chē)站，從北京南站開(kāi)始，依次編號(hào)為1～36，與京廣高速鐵路平行的京廣線全長(zhǎng)2 342 km，包含248 個(gè)車(chē)站，京廣高速鐵路與京廣線共同構(gòu)成京廣運(yùn)輸通道.京廣高速鐵路夕發(fā)朝至列車(chē)始發(fā)時(shí)間域?yàn)?8∶00—22∶00，終到時(shí)間域06∶30—09∶30，列車(chē)追蹤間隔為5 min，車(chē)站到達(dá)和出發(fā)間隔均取5 min，最小停站時(shí)間為2 min，起停附加時(shí)分為2 min，同方向列車(chē)不同時(shí)到發(fā)間隔時(shí)間與發(fā)到間隔時(shí)間均為3 min；在京廣普速鐵路上，列車(chē)追蹤間隔為5 min，車(chē)站到達(dá)和出發(fā)間隔均取5 min，最小停站時(shí)間為3 min，起停附加時(shí)分為2 min.天窗合理開(kāi)設(shè)時(shí)間范圍為00∶00—06∶00，天窗時(shí)長(zhǎng)為240 min，天窗安全間隔時(shí)間為5 min.考慮車(chē)站能力及客流特點(diǎn)，選取石家莊、鄭州東、武漢、長(zhǎng)沙南、郴州西5 個(gè)大站作為備選的轉(zhuǎn)線車(chē)站集合，對(duì)應(yīng)的到發(fā)線總數(shù)分別為11、16、24、16、6 條.

京廣通道內(nèi)高速鐵路和普速鐵路區(qū)段距離和運(yùn)行時(shí)間如附加材料6 中表S1 所示，由于上、下行方向信息基本一致，僅以下行方向?yàn)槔o出.根據(jù)2018 年年底列車(chē)運(yùn)行圖數(shù)據(jù)[12]，京廣高速鐵路總共開(kāi)行14 列夕發(fā)朝至列車(chē)，其中上行與下行方向各7 列.京廣高速鐵路夕發(fā)朝至列車(chē)，具體開(kāi)行信息如附加材料6 中表S2 所示，包括列車(chē)始發(fā)、終到車(chē)站、運(yùn)行方向、開(kāi)行距離、旅行時(shí)間、合理出發(fā)、到達(dá)時(shí)間范圍以及列車(chē)停站方案.

以2018 年年底列車(chē)運(yùn)行圖[12]為基準(zhǔn)，根據(jù)本文提出的模型方法，將14 列高速鐵路夕發(fā)朝至列車(chē)插入既有列車(chē)運(yùn)行圖框架.在19∶00—10∶00 這個(gè)時(shí)間段內(nèi)，共包含73 列下行高速鐵路日間列車(chē)，58 列上行高速鐵路日間列車(chē)，在平行的普速鐵路上，這個(gè)時(shí)間段共開(kāi)行32 列下行普速列車(chē)，23 列上行普速列車(chē).列車(chē)開(kāi)行統(tǒng)計(jì)信息見(jiàn)附加材料6 中表S3.

采用MATLAB 7.0 編程實(shí)現(xiàn)設(shè)計(jì)的啟發(fā)式求解算法，設(shè)最大迭代次數(shù)為200，ALNS 算法大約平均經(jīng)過(guò)40 次便可收斂至最優(yōu)解.在目標(biāo)函數(shù)分別賦權(quán)0.5 的情況下，無(wú)量綱目標(biāo)函數(shù)最小值為0.21，對(duì)應(yīng)求解時(shí)間為784 s.目標(biāo)函數(shù)最小值對(duì)應(yīng)的最佳天窗設(shè)置方案和夕發(fā)朝至列車(chē)到發(fā)時(shí)刻表分別如表1和表2 所示.表2 中“/”兩側(cè)分別表示車(chē)站到達(dá)和出 發(fā)時(shí)刻.

表1 最優(yōu)天窗方案Tab.1 Optimal maintenance window scheme

表2 京廣高鐵夕發(fā)朝至列車(chē)最優(yōu)解對(duì)應(yīng)的到發(fā)時(shí)刻表Tab.2 Optimal arrival and departure time table of Beijing-Guangzhou high-speed railways

為進(jìn)一步分析不同列車(chē)開(kāi)行模式對(duì)夕發(fā)朝至列車(chē)開(kāi)行和天窗設(shè)置的影響，分別限定列車(chē)開(kāi)行模式對(duì)目標(biāo)函數(shù)進(jìn)行求解，結(jié)果如表3 所示，表中第3 列中“/”左、右兩側(cè)分別表示在研究時(shí)間段內(nèi)受影響的高速鐵路列車(chē)數(shù)、普速列車(chē)數(shù).對(duì)比可知，在不同列車(chē)開(kāi)行模式下，高速鐵路夕發(fā)朝至列車(chē)總的旅行時(shí)間、高速鐵路夕發(fā)朝至列車(chē)對(duì)既有列車(chē)運(yùn)行圖的影響以及對(duì)應(yīng)的計(jì)算時(shí)間均存在差異.

表3 不同列車(chē)開(kāi)行模式下的目標(biāo)函數(shù)值Tab.3 Objective function values under different overnight train operation modes

圖3 給出了限定不同列車(chē)開(kāi)行模式對(duì)應(yīng)的最優(yōu)天窗設(shè)置方案和夕發(fā)朝至列車(chē)運(yùn)行方案，圖中紅線、藍(lán)線分別表示列車(chē)在高速鐵路、普速鐵路運(yùn)行.可以發(fā)現(xiàn)：不同列車(chē)開(kāi)行模式下天窗較優(yōu)方案均為分段矩形天窗，這是由于分段矩形天窗要比垂直矩形天窗設(shè)置更為靈活；上行方向列車(chē)轉(zhuǎn)線運(yùn)行通常是在鄭州東站，而下行方向列車(chē)轉(zhuǎn)線運(yùn)行通常是在長(zhǎng)沙南站，主要是因?yàn)檫@些車(chē)站能力相對(duì)充裕，且具備組織列車(chē)跨線運(yùn)輸條件.

圖3 不同高速鐵路夕發(fā)朝至列車(chē)開(kāi)行模式下的天窗設(shè)置方案Fig.3 Maintenance window setting scheme under different overnight train operation modes of high-speed railways

5 結(jié) 論

1）通過(guò)引入狀態(tài)變量，有效刻畫(huà)了高速鐵路夕發(fā)朝至列車(chē)的3 種開(kāi)行模式，并據(jù)此建立了列車(chē)開(kāi)行模式未定情形下高速鐵路夕發(fā)朝至列車(chē)開(kāi)行與天窗設(shè)置協(xié)同優(yōu)化模型；

2）考慮構(gòu)建模型特征，提出了雙目標(biāo)轉(zhuǎn)化、約束線性化處理等模型約簡(jiǎn)策略，并結(jié)合優(yōu)化問(wèn)題的雙層循環(huán)特性，設(shè)計(jì)了基于自適應(yīng)大鄰域搜索的啟發(fā)式求解算法.

3）算例結(jié)果表明：本文算法大約平均經(jīng)過(guò)40 次便可收斂至最優(yōu)解，耗時(shí)784 s，具備較好的實(shí)用性.

4）未來(lái)研究可進(jìn)一步考慮天窗設(shè)置與維修計(jì)劃一體化編制，以提高天窗方案的可實(shí)施性.

備注：附加材料在中國(guó)知網(wǎng)本文的詳情頁(yè)中獲取.