基于ADMM方法的新增列車條件下靈活的列車時(shí)刻表優(yōu)化算法研究

高如虎，牛惠民

(蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州 730070)

在高速鐵路(以下簡稱高鐵)運(yùn)輸組織中，當(dāng)現(xiàn)有列車服務(wù)難以滿足突發(fā)增長的客流需求時(shí)，需要在原有運(yùn)營列車時(shí)刻表的基礎(chǔ)上，規(guī)劃新增列車的時(shí)刻表。對(duì)于新增列車條件下的時(shí)刻表優(yōu)化是“列車運(yùn)行調(diào)整”問題，但實(shí)質(zhì)也屬于列車時(shí)刻表優(yōu)化范疇。列車時(shí)刻表問題(Train Timetabling Problem, TTP)是軌道交通領(lǐng)域中的經(jīng)典問題。列車時(shí)刻表問題涉及數(shù)量眾多的車站和列車，模型中所含決策變量數(shù)目隨問題規(guī)模呈指數(shù)式增長，屬于典型的NP-hard問題，很難在多項(xiàng)式時(shí)間內(nèi)找到一種有效算法對(duì)其精確求解。尤其對(duì)于不同速度等級(jí)列車共線運(yùn)行的情況，還需要處理列車越行時(shí)間和位置選擇問題，使得問題更加復(fù)雜。如何設(shè)計(jì)可靠有效的求解方法，始終是列車時(shí)刻表問題的主要挑戰(zhàn)[1-2]。

構(gòu)建整數(shù)規(guī)劃模型并利用商業(yè)優(yōu)化軟件求解列車時(shí)刻表問題，是近年來興起的一種方法。文獻(xiàn)[3-5]構(gòu)建列車時(shí)刻表的混合整數(shù)規(guī)劃模型，并利用優(yōu)化軟件CPLEX求解。文獻(xiàn)[6]以總的乘客等待時(shí)間最少為優(yōu)化目標(biāo)，研究了時(shí)變客流需求條件下列車時(shí)刻表的優(yōu)化問題，建立了帶有線性約束的非線性整數(shù)規(guī)劃模型并利用通用優(yōu)化軟件GAMS求解模型。不同速度等級(jí)列車共線運(yùn)行情況下，還需要處理列車的越行問題，該情形改變了列車的發(fā)車順序。因此，模型中除了列車到發(fā)時(shí)刻變量外，還需要表示列車發(fā)車順序的0-1變量，這使得決策變量和約束條件的數(shù)量急劇增大[7-8]。而利用商業(yè)優(yōu)化軟件求解對(duì)數(shù)學(xué)模型要求苛刻，僅適合中小規(guī)模問題。

基于問題分解的求解方法，是解決列車時(shí)刻表問題的另一種有效思路，核心是將復(fù)雜的問題分解為容易求解的多個(gè)子問題，分別求解各子問題，然后通過集成和迭代，獲得問題的最優(yōu)解。近些年，很多文獻(xiàn)利用拉格朗日松弛算法對(duì)復(fù)雜的列車時(shí)刻表問題進(jìn)行分解并取得了顯著的求解效果。文獻(xiàn)[9]構(gòu)建了基于時(shí)空?qǐng)D的時(shí)刻表整數(shù)規(guī)劃模型，利用拉格朗日松弛算法將列車之間的耦合約束松弛，并分解為單列車在時(shí)空?qǐng)D中的最短路徑子問題。文獻(xiàn)[10]在研究城市軌道交通的列車時(shí)刻表問題時(shí)，考慮了能力和資源約束，最后利用拉格朗日松弛算法求解。文獻(xiàn)[11]提出了基于累計(jì)變量的列車時(shí)刻表整數(shù)規(guī)劃模型并設(shè)計(jì)了拉格朗日松弛算法求解。文獻(xiàn)[12]研究了新增列車條件下的列車時(shí)刻表優(yōu)化問題，并綜合考慮了車站進(jìn)路，利用拉格朗日松弛算法分解原問題。ADMM在拉格朗日松弛方法的基礎(chǔ)上，通過引入增廣項(xiàng)可快速的獲得原問題的可行解。由于ADMM方法優(yōu)越的分解性能，在大數(shù)據(jù)和機(jī)器學(xué)習(xí)領(lǐng)域[13]及分布式計(jì)算領(lǐng)域[14]被廣泛使用。最近，文獻(xiàn)[15]將ADMM方法應(yīng)用到車輛路徑優(yōu)化問題，并提出了ADMM在交通運(yùn)輸組織優(yōu)化領(lǐng)域的應(yīng)用前景。文獻(xiàn)[16]構(gòu)建了基于擴(kuò)展時(shí)空網(wǎng)絡(luò)的周期性列車時(shí)刻表模型，并提出了基于ADMM方法的分解機(jī)制。

現(xiàn)有研究大多固定了列車的區(qū)間運(yùn)行時(shí)間和列車停站方案或者為規(guī)劃列車指定相對(duì)較小的出發(fā)時(shí)間窗，又或者固定了列車的發(fā)車順序。本文以新增列車條件下的時(shí)刻表優(yōu)化問題為切入點(diǎn)，創(chuàng)新點(diǎn)為：①為獲得更高質(zhì)量和更符合實(shí)際的列車時(shí)刻表，提出了更加靈活的列車時(shí)刻表設(shè)置方法。具體地，列車可靈活的選擇區(qū)間運(yùn)行時(shí)間、停站方案、停站時(shí)間、到發(fā)順序、越行時(shí)機(jī)，此外，為規(guī)劃列車賦予以小時(shí)為出發(fā)時(shí)段的更加靈活的出發(fā)時(shí)間范圍。這種處理方法更加靈活，也更符合實(shí)際。②這種靈活的列車時(shí)刻表優(yōu)化架構(gòu)需要設(shè)計(jì)一種更加有效和更加科學(xué)的方法來解決列車對(duì)時(shí)空資源占用選擇沖突問題。為此，本文提出了一種更加緊湊的基于時(shí)空弧段的不相容約束刻畫列車的耦合約束。③分別利用標(biāo)準(zhǔn)的拉格朗日松弛方法和ADMM方法解決新增列車條件下的靈活列車時(shí)刻表優(yōu)化問題，并對(duì)兩種求解方法進(jìn)行了比較，驗(yàn)證了ADMM方法在求解該優(yōu)化問題時(shí)的優(yōu)越性。

1 問題分析及說明

1. 1 問題分析

本文研究雙線高速鐵路新增列車條件下的時(shí)刻表優(yōu)化問題。按照運(yùn)輸生產(chǎn)實(shí)際，鐵路2個(gè)方向列車相互獨(dú)立運(yùn)行，選取其中一個(gè)方向進(jìn)行研究。沿著該線路列車運(yùn)行方向：U為車站集合；Ie為原有時(shí)刻表中列車集合；Ia為新增列車集合；[0,T]為全天運(yùn)營時(shí)段，不失一般性，按照1 min為間隔對(duì)全天運(yùn)營時(shí)段進(jìn)行離散處理，以1 min的整數(shù)倍表示列車在車站的到發(fā)時(shí)刻和在區(qū)間的運(yùn)行時(shí)間。

本文提出靈活的列車時(shí)刻表優(yōu)化架構(gòu)，主要有以下幾方面的考慮：首先，鐵路運(yùn)營者往往按照小時(shí)客流需求推算運(yùn)營列車數(shù)量，靈活架構(gòu)下給定每個(gè)小時(shí)的列車數(shù)量與鐵路運(yùn)營實(shí)際相契合。其次，列車在線路區(qū)間運(yùn)行速度并不固定，這種區(qū)間運(yùn)行時(shí)間的靈活設(shè)置與鐵路運(yùn)營實(shí)際更加契合。然后，列車停站方案與列車時(shí)刻表關(guān)系密切，應(yīng)該對(duì)二者進(jìn)行綜合設(shè)計(jì)。最后，傳統(tǒng)的指定列車較小出發(fā)時(shí)刻范圍的方法，事實(shí)上限制了列車對(duì)出發(fā)時(shí)刻的選擇，并且相對(duì)固定了列車的出發(fā)順序，此外，列車的出發(fā)時(shí)刻范圍在實(shí)際中也很難確定。

事實(shí)上，在鐵路運(yùn)營實(shí)踐中，這種靈活的列車時(shí)刻表優(yōu)化架構(gòu)相對(duì)于傳統(tǒng)的列車時(shí)刻表優(yōu)化更加貼合實(shí)際。理論上，這種靈活的優(yōu)化方法相當(dāng)于傳統(tǒng)列車時(shí)刻表優(yōu)化對(duì)列車出發(fā)時(shí)間窗、停站方案、停站時(shí)間以及列車發(fā)車順序的松弛處理，此種處理能夠獲得更高質(zhì)量的列車時(shí)刻表，但也無疑增加了列車時(shí)刻表優(yōu)化的復(fù)雜度，需要設(shè)計(jì)一種更加有效的方法對(duì)其求解。

1.2 符號(hào)說明

本文通過構(gòu)建時(shí)空網(wǎng)絡(luò)描述列車時(shí)刻表問題，并據(jù)此建立基于時(shí)空弧段的0-1整數(shù)規(guī)劃模型。以下給出用于構(gòu)建網(wǎng)絡(luò)和建立模型所需要的集合、索引、參數(shù)和變量。

索引：i、j為列車索引，i、j∈I；u、u′為車站索引，u、u′∈U；t、t′、τ、τ′為時(shí)刻索引，t、t′、τ、τ′∈[0,T]；(u,t)、(u′,t′)為時(shí)空網(wǎng)絡(luò)節(jié)點(diǎn)索引，(u,t),(u′,t′)∈N；(u,t;u′,t′)為時(shí)空網(wǎng)絡(luò)中從節(jié)點(diǎn)(u,t)到(u′,t′)的弧段索引，(u,t;u′,t′)∈A。

決策變量

xi(u,t;u′,t′)=

2 時(shí)空網(wǎng)絡(luò)構(gòu)建

由于列車時(shí)刻表固有的時(shí)空特性，構(gòu)建時(shí)空網(wǎng)絡(luò)模型是解決列車時(shí)刻表問題最常用的建模方式。通過構(gòu)建時(shí)空網(wǎng)絡(luò)，可將列車時(shí)刻表信息(如始發(fā)時(shí)刻信息、停站信息等)圖形化地顯示在網(wǎng)絡(luò)結(jié)構(gòu)中。此外，這種表現(xiàn)形式還可以將時(shí)刻表問題中難以描述的約束條件，轉(zhuǎn)換為網(wǎng)絡(luò)中弧段或節(jié)點(diǎn)的制約關(guān)系(如可達(dá)性、不相容性、網(wǎng)絡(luò)流量守恒等)，將優(yōu)化目標(biāo)轉(zhuǎn)換為列車占用網(wǎng)絡(luò)弧段的最小費(fèi)用。G=(N,A)為時(shí)空網(wǎng)絡(luò)，對(duì)每一個(gè)列車，都對(duì)應(yīng)一個(gè)子網(wǎng)絡(luò)。Gi=(Ni,Ai)為列車i對(duì)應(yīng)的時(shí)空子網(wǎng)絡(luò)，其中，Ni為列車i可占用的時(shí)空節(jié)點(diǎn)集合，Ai為列車i可占用的時(shí)空弧段集合。下面以列車i為例說明時(shí)空網(wǎng)絡(luò)的構(gòu)建過程，見圖1。

圖1 時(shí)空網(wǎng)絡(luò)圖

2.1 網(wǎng)絡(luò)節(jié)點(diǎn)

為保證時(shí)空網(wǎng)絡(luò)的完整性，對(duì)列車i分別引入虛擬起點(diǎn)σi和虛擬終點(diǎn)τi。對(duì)于每個(gè)列車i∈I=Ie∪Ia，頂點(diǎn)Ni集合包含虛擬起點(diǎn)σi、車站到達(dá)節(jié)點(diǎn)集合Ru、車站出發(fā)節(jié)點(diǎn)集合Wu和虛擬終點(diǎn)τi。值得說明的是，對(duì)于原有列車i∈Ie，經(jīng)過各個(gè)車站對(duì)應(yīng)的起始節(jié)點(diǎn)和到達(dá)節(jié)點(diǎn)集合可由該列車原始時(shí)刻表、始發(fā)時(shí)刻最大偏移量、最小最大停站時(shí)間、最小最大運(yùn)行時(shí)間確定；對(duì)于新增列車i∈Ia，經(jīng)過各個(gè)車站對(duì)應(yīng)的起始節(jié)點(diǎn)和到達(dá)節(jié)點(diǎn)集合可由出發(fā)小時(shí)時(shí)段、最小最大停站時(shí)間、最小最大運(yùn)行時(shí)間確定。列車i的時(shí)空節(jié)點(diǎn)集合Ni可表示為

Ni={σi,τi}∪{Woi,Woi+1，…，Wdi}∪{Roi,Roi+1，…，Rdi}

2.2 網(wǎng)路弧段

列車占用弧段的費(fèi)用見表1，α,β分別為原有列車和新增列車的費(fèi)用權(quán)重。原有列車和新增列車對(duì)應(yīng)的優(yōu)化目標(biāo)不同，對(duì)于原有列車，期望新優(yōu)化的列車時(shí)刻表與原有時(shí)刻表的偏離程度越小越好，包括在始發(fā)站發(fā)車時(shí)刻的偏離以及區(qū)間運(yùn)行時(shí)間、車站停站時(shí)間的偏離。而對(duì)于新增列車，期望總的旅行時(shí)間最小，包括區(qū)間運(yùn)行時(shí)間以及在車站的停站時(shí)間。具體地，對(duì)于原有列車i∈Ie，起始弧的費(fèi)用表示選擇始發(fā)站的出發(fā)節(jié)點(diǎn)對(duì)應(yīng)時(shí)刻與原列車時(shí)刻表始發(fā)時(shí)刻的偏差費(fèi)用，運(yùn)行弧和停站弧費(fèi)用分別表征列車選擇該運(yùn)行弧段和停站弧段對(duì)應(yīng)的運(yùn)行時(shí)間和停站時(shí)間與原有時(shí)間的偏差費(fèi)用。而對(duì)于新增列車i∈Ia，可在出發(fā)小時(shí)時(shí)段任意時(shí)刻出發(fā)，起始弧的費(fèi)用為0。對(duì)于列車占用運(yùn)行弧和停站弧的費(fèi)用分別表征列車在區(qū)間的運(yùn)行時(shí)間和車站停站時(shí)間費(fèi)用。列車占用終止弧的費(fèi)用均設(shè)置為0。列車從虛擬起點(diǎn)到虛擬終點(diǎn)對(duì)時(shí)空網(wǎng)絡(luò)弧段的占用形成了一條時(shí)空路徑(如圖1紅色線條所示)，該時(shí)空路徑反映了列車在各站的到發(fā)時(shí)刻信息。

表1 弧段費(fèi)用

3 模型建立

3.1 優(yōu)化目標(biāo)

考慮到本文對(duì)列車區(qū)間運(yùn)行時(shí)間、車站停站時(shí)間及新增列車出發(fā)時(shí)間窗靈活的設(shè)置，容許列車自由選擇停站、越行時(shí)機(jī)、區(qū)間運(yùn)行時(shí)間。這些因素直接決定了列車的旅行時(shí)間，進(jìn)而影響鐵路服務(wù)質(zhì)量。因而，本文以新增列車的旅行時(shí)間最短為優(yōu)化目標(biāo)，同時(shí)我們希望原有列車的時(shí)刻表偏移量最小。通過時(shí)空網(wǎng)絡(luò)的構(gòu)建，列車時(shí)刻表問題轉(zhuǎn)換為列車占用時(shí)空資源費(fèi)用最小的網(wǎng)絡(luò)優(yōu)化問題，目標(biāo)函數(shù)為

(1)

3.2 約束條件

(1) 網(wǎng)絡(luò)流平衡約束

流平衡約束是網(wǎng)絡(luò)優(yōu)化問題最基本的約束。通過時(shí)空網(wǎng)絡(luò)構(gòu)建，在列車時(shí)刻表問題中，對(duì)于任意列車i，需要保證僅有一條時(shí)空路徑被列車選擇。流平衡約束為

(2)

(2) 列車停站約束

在原列車時(shí)刻表中，對(duì)于原有列車i∈Ie，若在u站停站，則在新優(yōu)化列車時(shí)刻表中也必須在u站停站，該列車在其他車站可自由選擇停站。對(duì)于新增列車i∈Ia，根據(jù)途徑車站的類型，可分為兩類情況，其中一類為必停站，此類車站一般為始發(fā)終到站及具有大客流的車站；另一類為備選停站，列車經(jīng)過此類車站時(shí)，可自由選擇是否停站及停站時(shí)間，此類車站一般為中間站及越行站。因此，列車停站約束可描述為

(3)

如果列車在某車站停站，則停站時(shí)間在最小和最大停站時(shí)間范圍內(nèi)自由選擇。通過時(shí)空網(wǎng)絡(luò)的構(gòu)建，停站時(shí)間約束已經(jīng)在時(shí)空網(wǎng)絡(luò)停站弧中得到保證，這里再無需考慮。

(3) 安全間隔及越行約束

列車在時(shí)空網(wǎng)絡(luò)中除滿足上述的流平衡約束和列車停站約束外，還需要滿足列車安全間隔約束。此類約束是多列車之間的耦合關(guān)系，為了保證列車對(duì)于時(shí)空資源占用的排它性，本文引入不相容弧集合描述。

為保證列車運(yùn)行安全，任意兩列車應(yīng)滿足安全出發(fā)間隔和安全到達(dá)間隔約束。此外，不同速度等級(jí)列車需要滿足越行約束。事實(shí)上，列車安全到達(dá)間隔約束和列車越行約束均可轉(zhuǎn)換為列車在車站應(yīng)滿足的出發(fā)間隔時(shí)間約束。為方便對(duì)列車安全間隔約束進(jìn)行統(tǒng)一處理，本文引入不相容弧集合Φ(u,t;u′,t′)，表示當(dāng)某一列車占用時(shí)空網(wǎng)絡(luò)運(yùn)行弧段(u,t;u′,t′)∈Atravel時(shí)，其他列車不能同時(shí)占用時(shí)空網(wǎng)絡(luò)中弧段的集合，即違反安全間隔的弧段。

給定某一時(shí)空弧段，則該弧段對(duì)應(yīng)的不相容弧段集合也隨之確定。具體地，對(duì)于時(shí)空運(yùn)行弧段a=(u,t;u+1,t′)∈Atravel和b=(u,τ;u+1,τ′)∈Atravel定義：

ha,b=max{hdep,(t′-t)-(τ′-τ)+harr}

(4)

表示時(shí)空弧段a和b若同時(shí)被列車占用，應(yīng)滿足的安全間隔。

對(duì)于時(shí)空弧段a，如圖2(a)所示，若t≤τ

對(duì)于時(shí)空弧段a，如圖2(b)所示，若t-hb,a<τ

圖2 不相容弧示意

綜上所示，弧段a的不相容弧集合Φ(a)為

Φ(a)={b=(u,τ;u′,τ′)∈Atravel|t-hb,a<

τ

(5)

對(duì)于任意的時(shí)空運(yùn)行弧段a，在不相容弧集合Φ(a)內(nèi)，當(dāng)有列車占用時(shí)空網(wǎng)絡(luò)弧段a時(shí)，其他任意列車不能占用不相容弧集合Φ(a)內(nèi)的其他弧段。不相容約束可描述為

?i∈Ia∈Atravel

(6)

下面分兩種情況討論不相容約束：

(4) 變量域約束

xi(u,t;u′,t′)∈{0,1} ?i∈I(u,t;u′,t′)∈Ai

(7)

4 基于拉格朗日松弛的分解

本文所建立模型中的約束條件式(6)為多列車耦合約束，下面利用拉格朗日松弛算法對(duì)列車時(shí)刻表模型進(jìn)行松弛和分解。具體地，引入非負(fù)的拉格朗日乘子λi(a)≥0,?i∈I,a∈Atravel，將模型中的耦合約束條件松弛，形成拉格朗日對(duì)偶問題。拉格朗日函數(shù)為

(8)

進(jìn)一步地，拉格朗日函數(shù)可被整理為

(9)

其中

(10)

移除式(9)中的常數(shù)項(xiàng)，原問題被分解為如下的單列車子問題

(11)

s.t. 式(2)、式(3)、式(7)。

子問題為單列車在時(shí)空網(wǎng)絡(luò)中的最短路徑問題，可利用最短路徑算法快速求解。在拉格朗日松弛方法中，通過迭代求解子問題，并更新拉格朗日乘子可獲得原問題的下界。

在迭代求解時(shí)，使用次梯度法更新拉格朗日乘子。

(12)

ηq=1/(q+1)

(13)

拉格朗日松弛算法如下所示：

Step6終止條件。如果ggap≤ε(最小gap值) 或者q>Q(最大迭代次數(shù))，則算法終止；否則，令q=q+1，返回Step2。

在求解子問題時(shí)，如式(10)所示，列車的最短路徑費(fèi)用取決于時(shí)空弧段的旅行時(shí)間費(fèi)用ci(a)和拉格朗日乘子λi(a)。在每次迭代時(shí)，僅通過列車占用弧段的拉格朗日乘子值調(diào)節(jié)列車的路徑選擇。事實(shí)上，在拉格朗日松弛方法迭代過程中，當(dāng)所有列車時(shí)空路徑選擇完成后，才統(tǒng)一更新各弧段的拉格朗日乘子值，相當(dāng)于在一次迭代時(shí)同一小時(shí)內(nèi)的同等級(jí)列車占用弧段的拉格朗日乘子也相等。這就導(dǎo)致了在每次迭代時(shí)，同一小時(shí)內(nèi)的同等級(jí)列車會(huì)選擇同樣的時(shí)空最短路徑。這種解的對(duì)稱性問題嚴(yán)重阻礙算法的效率。

5 基于ADMM的求解方法

ADMM方法適用于可分結(jié)構(gòu)的凸優(yōu)化問題，可將原問題等價(jià)的分解成易求解的子問題，交替求解子問題，以獲得原問題的最優(yōu)解或者可行解。ADMM方法是在拉格朗日松弛方法的基礎(chǔ)上引入二次懲罰項(xiàng)，構(gòu)造增廣拉格朗日函數(shù)，將原問題分解成若干個(gè)容易求解的子問題；在次梯度迭代的過程中，按照一定次序?qū)Σ煌淖兞窟M(jìn)行交替迭代求解，最終得到最優(yōu)或可行解。

5.1 基于ADMM的松弛、增廣和分解

根據(jù)ADMM原理，首先引入松弛實(shí)數(shù)變量di(a)∈[0,1]，將耦合約束不等式(6)轉(zhuǎn)化為等式

(14)

對(duì)于本文所建立數(shù)學(xué)模型，在拉格朗日松弛函數(shù)的基礎(chǔ)上，引入二次懲罰項(xiàng)ρ，構(gòu)造增廣拉格朗日函數(shù)

(15)

增廣拉格朗日函數(shù)中含有二次項(xiàng)，使得問題失去了可分解性。下面對(duì)增廣拉格朗日函數(shù)進(jìn)行線性化處理，令

(16)

[di(a)+pi(a)-1]2}

(17)

顯然，由于存在松弛變量di(a)，上式中還存在二次項(xiàng)，下面確定松弛變量di(a)的取值。將上式中除松弛變量di(a)以外的其他變量看成為參數(shù)，并將與松弛變量di(a)相關(guān)項(xiàng)組合為如下的二次函數(shù)形式

Ldi(a)=di(a)2+2×di(a)×[pi(a)-1+xi(a)+

(18)

式中：Q為與松弛變量di(a)的無關(guān)項(xiàng)。由于松弛變量di(a)為連續(xù)變量，因此，函數(shù)Ldi(a)取最小值的點(diǎn)為

(19)

下面分兩種情況進(jìn)行討論松弛變量di(a)的取值：

(1) 當(dāng)pi(a)≥1時(shí)，則di*(a)≤0，并且在[0,1]范圍內(nèi)，函數(shù)Ldi(a)為遞增函數(shù)。故最優(yōu)的d*(a)=0，帶入公式(18)，二次項(xiàng)可轉(zhuǎn)化為

xi(a)+2×[pi(a)-1]2

(20)

綜合兩種情況，增廣拉格朗日問題可進(jìn)一步分解為如下的單列車的子問題

(21)

s.t. 約束式(2)、式(3)、式(7)。

其中,

(22)

5.2 基于ADMM方法的求解過程

本文研究的列車時(shí)刻表問題含有關(guān)于多個(gè)列車的多個(gè)決策變量，將ADMM方法擴(kuò)展為多塊(multi-block)的情況。值得說明的是，標(biāo)準(zhǔn)的two-block ADMM 方法的收斂性已經(jīng)被證明[17]。而擴(kuò)展的multi-block ADMM 方法被通過反例證明并不必然收斂[18]。盡管沒有收斂性的保證，但由于multi-block ADMM 方法的可操作性及高效性，在一些實(shí)際的優(yōu)化問題中卻被廣泛應(yīng)用[19]。

通過對(duì)原問題進(jìn)行松弛、增廣、線性化和分解求解方法的設(shè)計(jì)，利用ADMM方法求解列車時(shí)刻表的具體流程如下所示。

Step2基于優(yōu)先權(quán)迭代順序產(chǎn)生ADMM解。

For 每個(gè)列車i∈I

最短路徑算法求解i列車對(duì)應(yīng)的ADMM子問題Lρ,i；

固定列車i對(duì)應(yīng)子問題的解；

Endfor

Step6終止條件。如果ggap≤ε(最小gap值) 或這q>Q(最大的迭代次數(shù))，則算法終止并令上界解作為最后輸出結(jié)果；否則，令q=q+1，返回Step2。

值得說明的是，算法中Step2拉格朗日乘子和二次懲罰項(xiàng)的更新參考了文獻(xiàn)[15]中的方法。算法中Step3的啟發(fā)式可行算法與拉格朗日松弛算法中的啟發(fā)式可行算法相同，可利用文獻(xiàn)[11]中提出的優(yōu)先權(quán)算法求解。

6 算例

以武廣高鐵線路為例，此線路包含18個(gè)車站，為方便描述，車站依次編號(hào)為1～18。在此線路上運(yùn)行兩種速度等級(jí)的列車，不同速度等級(jí)列車在區(qū)間的運(yùn)行時(shí)間見表2。高等級(jí)列車最小/最大停站時(shí)間分別為2、5 min，低等級(jí)列車最小/最大停站時(shí)間分別為2、10 min。線路上在全天規(guī)劃時(shí)段06:00—24:00內(nèi)，原有列車135列，計(jì)劃新增列車20列。為便于處理，假定原有列車均為高等級(jí)列車，新增列車均為低等級(jí)列車，假定列車在區(qū)間的運(yùn)行時(shí)間為常數(shù)。原有列車的始發(fā)站出發(fā)時(shí)間最大偏移量為10 min，關(guān)于新增列車的相關(guān)運(yùn)營參數(shù)見表3。本文所提出的算法在Visual Studio 2013平臺(tái)上使用C++語言實(shí)現(xiàn)，算法運(yùn)行環(huán)境為1臺(tái)CPU Intel Core i5-4 590 s 3.00 GHz, 4 GB內(nèi)存的個(gè)人計(jì)算機(jī)。

表2 列車在線路區(qū)間的運(yùn)行時(shí)間

表3 新增列車相關(guān)運(yùn)營參數(shù)

分別利用標(biāo)準(zhǔn)的LR和ADMM算法求解，共迭代100次，兩種算法對(duì)應(yīng)的上下界迭代過程見圖3，對(duì)應(yīng)的優(yōu)化ggap值變化情況見圖4。對(duì)于ADMM方法，最優(yōu)的上界為3 774，最優(yōu)下界為3 254，最優(yōu)ggap值為13.78%，計(jì)算時(shí)間為302.74 s；對(duì)于LR算法，最優(yōu)的上界為4 097，最優(yōu)下界為3 287.33，最優(yōu)ggap值為19.76%，計(jì)算時(shí)間為195.83 s。從兩種算法的迭代過程及計(jì)算結(jié)果中不難看出，盡管ADMM方法的計(jì)算時(shí)間略大于LR方法，但求得的最優(yōu)上界和ggap值更優(yōu)。此外，ADMM方法收斂的速度比LR算法更快。因此，對(duì)于本文優(yōu)化的新增列車條件下的靈活列車時(shí)刻表優(yōu)化問題，ADMM相比于LR具有更好的計(jì)算性能。

圖3 LR和ADMM算法的上下界迭代過程

圖4 LR和ADMM算法的ggap迭代過程

利用ADMM方法優(yōu)化的列車運(yùn)行圖見圖5。限于篇幅，對(duì)應(yīng)的列車時(shí)刻表(整數(shù)形式，如0對(duì)應(yīng)06:00，依次類推)上傳至https:∥github.com/ruhugao/Ahu。從運(yùn)行圖中可以看出，部分新增的低等級(jí)列車可被原有的高等級(jí)列車越行，如新增的從武漢站開往廣州南站的列車1分別在郴州西和韶關(guān)站被原有高等級(jí)列車越行；部分原有列車改變了原有的列車時(shí)刻表，如原有列車4在其始發(fā)站武漢站的出發(fā)時(shí)刻為07:33，優(yōu)化后的出發(fā)時(shí)刻調(diào)整為07:37。部分新增列車除了在計(jì)劃的列車車站停站外，在其他車站也可停站，可以在最小和最大停站時(shí)間之間靈活的選擇停站時(shí)間，如新增列車1在計(jì)劃之外的郴州站停站4 min。本文提出的這種靈活架構(gòu)下，利用兩種分解算法求解時(shí)，可以迅速的得到可行解。

圖5 優(yōu)化的列車運(yùn)行圖

7 結(jié)論

本文針對(duì)新增列車條件下的高速鐵路列車時(shí)刻表進(jìn)行優(yōu)化。為了獲得更高質(zhì)量的列車時(shí)刻表，提出了一種靈活的列車時(shí)刻表優(yōu)化架構(gòu)。通過構(gòu)建時(shí)空網(wǎng)絡(luò)的手段，建立了基于時(shí)空弧段的0-1整數(shù)規(guī)劃模型，提出了一種更加緊湊的不相容約束用以刻畫列車時(shí)刻表優(yōu)化問題的列車安全間隔約束。分別利用標(biāo)準(zhǔn)的拉格朗日松弛方法和交替方向乘子法對(duì)原問題進(jìn)行分解和求解，并以武廣高速鐵路線路為例進(jìn)行了實(shí)例分析。研究結(jié)果表明：

(1)相對(duì)于傳統(tǒng)的列車時(shí)刻表優(yōu)化問題，在靈活的列車時(shí)刻表優(yōu)化架構(gòu)下，更能夠快速的獲得可行的列車時(shí)刻表。

(2)本文提出的更加緊湊的基于時(shí)空弧段的不相容約束能夠更加清晰的刻畫列車之間的耦合關(guān)系，同時(shí)這種不相容約束在ADMM方法對(duì)原問題分解過程中也更加方便。

(3)通過實(shí)例驗(yàn)證，利用標(biāo)準(zhǔn)的拉格朗日松弛方法求解的最優(yōu)ggap值為19.76%，而利用ADMM方法求得的最優(yōu)ggap值為13.78%。兩種方法相比，盡管ADMM方法的計(jì)算時(shí)間略大于LR方法，但求得的最優(yōu)上界和最優(yōu)ggap值更優(yōu)。此外，ADMM方法收斂的速度比LR算法更快。