基于差分進(jìn)化算法的動車組周轉(zhuǎn)接續(xù)優(yōu)化研究

高 楊，郭紅戈

GAO Yang，GUO Hongge

（太原科技大學(xué) 電子信息工程學(xué)院，山西 太原 030024)

(College of Electronic and Information Engineering， Taiyuan University of Science and Technology， Taiyuan 030024，Shanxi， China)

0 引言

動車組周轉(zhuǎn)接續(xù)方案是指在給定高速鐵路全線列車運(yùn)行圖的背景下，基于車站行車組織原則，具體安排動車組在2條或2條以上運(yùn)行線路之間的列車運(yùn)行線接續(xù)關(guān)系[1]。因此，為提高動車組使用效率[2]，需要合理安排動車組在站的接續(xù)，縮短動車組在站的非生產(chǎn)作業(yè)時間。

目前，我國很多國內(nèi)專家以高速鐵路為背景，針對動車組周轉(zhuǎn)接續(xù)優(yōu)化問題進(jìn)行研究，研究提出適合我國國情的動車組運(yùn)用方式——不固定區(qū)段使用方式[3-4]。趙鵬等[5]首次針對動車組不固定區(qū)段使用方式進(jìn)行研究，提出利用匈牙利算法求解動車組周轉(zhuǎn)接續(xù)優(yōu)化問題。趙鵬等[6]還針對動車組運(yùn)用優(yōu)化問題，考慮檢修約束條件，提出基于概率局域搜索的貪婪算法。王瑩等[7]考慮運(yùn)行線可調(diào)的動車組周轉(zhuǎn)優(yōu)化問題，探討基于改進(jìn)廣義標(biāo)號法的分枝定價算法。王文憲等[8]運(yùn)用蟻群算法求解動車組周轉(zhuǎn)接續(xù)優(yōu)化模型，驗(yàn)證了智能優(yōu)化算法針對求解大規(guī)模動車組運(yùn)用優(yōu)化問題的有效性。陳然等[9]考慮車站行車組織人員的意圖，設(shè)計(jì)基于專家系統(tǒng)的改進(jìn)型蟻群算法求解動車組運(yùn)用優(yōu)化模型，提高了動車組的使用效率。

動車組周轉(zhuǎn)接續(xù)優(yōu)化問題是具有離散決策變量性質(zhì)的組合優(yōu)化問題，合理安排列車運(yùn)行圖任務(wù)間的接續(xù)關(guān)系，使所有動車組列車在車站周轉(zhuǎn)接續(xù)時間總和最小。動車組周轉(zhuǎn)接續(xù)優(yōu)化問題，其復(fù)雜性隨著動車組數(shù)量的增加而不斷地變大，經(jīng)過對智能優(yōu)化算法進(jìn)行大量研究后發(fā)現(xiàn)，盡管動車組列車周轉(zhuǎn)接續(xù)優(yōu)化運(yùn)算規(guī)模很大，卻能得到一個最接近可以被接受的優(yōu)化解，為這類優(yōu)化問題的求解提供較好的方法。而差分進(jìn)化算法(Differential Evolution，DE)作為一種群體智能優(yōu)化方法，采用浮點(diǎn)數(shù)編碼，具有實(shí)現(xiàn)簡單、控制參數(shù)少和優(yōu)化性能好等優(yōu)點(diǎn)[10]。在組合優(yōu)化領(lǐng)域，研究者較多地采用離散編碼的離散DE算法(Discrete DE，DDE)[11-12]，取得了較好的效果。因此，根據(jù)標(biāo)準(zhǔn)DE算法的進(jìn)化機(jī)制，利用其簡單高效的優(yōu)點(diǎn)，提出一種置換策略差分進(jìn)化算法(Differential Evolution for the Permutations space，DEP)來求解動車組周轉(zhuǎn)優(yōu)化問題，得到動車組的優(yōu)化周轉(zhuǎn)方式。

1 動車組周轉(zhuǎn)接續(xù)優(yōu)化問題的數(shù)學(xué)模型

1.1 模型假設(shè)及參數(shù)定義

以高速鐵路全線、成對列車運(yùn)行圖為前提條件，假設(shè)全線上有始發(fā)、終到動車組列車能力的樞紐站M個，動車組周轉(zhuǎn)接續(xù)在站停留時間包括設(shè)置天窗的夜間駐留時間[4]。為了更好地描述問題，首先定義以下變量：N為全線上的車站集合；Nh為全線上的樞紐車站集合，其中h為任意樞紐車站，h=1，2，…，M；C為全線上的列車運(yùn)行線集合；i，j為全線上的列車運(yùn)行線，i，j∈C；，別為列車運(yùn)行圖周期內(nèi)上行和下行終到車站h的列車運(yùn)行線數(shù)目；，分別為列車運(yùn)行圖周期內(nèi)從車站h上行始發(fā)和下行始發(fā)的列車運(yùn)行線數(shù)目分別為列車運(yùn)行圖周期內(nèi)終到車站h和從車站h始發(fā)的列車運(yùn)行線數(shù)目mhjxd分別為車站h的上行列車運(yùn)行線i和下行列車運(yùn)行線j的終到時刻，其中分別為車站h上行列車運(yùn)行線i和下行列車運(yùn)行線j的始發(fā)時刻，其中分別為上、下行列車運(yùn)行線i到達(dá)車站h的終到時刻和上、下行列車運(yùn)行線j從車站h的始發(fā)時刻分別為運(yùn)行線i的終到站和始發(fā)站，為在站動車組列車運(yùn)行線之間的接續(xù)關(guān)系集合；Xij為決策變量，定義如下。

令為動車組列車在車站h的周轉(zhuǎn)接續(xù)時間，可表示為

1.2 數(shù)學(xué)模型

針對樞紐站動車組周轉(zhuǎn)接續(xù)優(yōu)化問題，可以通過動車組擔(dān)當(dāng)列車運(yùn)行圖運(yùn)輸任務(wù)的順序來刻畫，即通過運(yùn)行圖任務(wù)間的接續(xù)關(guān)系進(jìn)行優(yōu)化，實(shí)質(zhì)是要尋找一個最短的路徑，按照列車運(yùn)行圖的要求走完運(yùn)行圖任務(wù)中的各個車站。

式中：h∈N；(i，j) ∈CL。

公式⑶是以所有動車組列車在站周轉(zhuǎn)停留時間總和最小為目標(biāo)函數(shù)。公式⑷是列車開行條件，前行列車運(yùn)行線的終到車站必須與后續(xù)列車運(yùn)行線的始發(fā)站一致，并且動車組列車最早可開行時刻應(yīng)小于接續(xù)列車運(yùn)行線的始發(fā)時刻。公式⑸是接續(xù)條件，掛線運(yùn)行的動車組列車之間的接續(xù)時間應(yīng)不小于動車組列車接續(xù)時間標(biāo)準(zhǔn)，取CT hij=15 min。公式⑹和公式⑺是惟一性條件，公式⑹表示在站同一時刻，對于終到的動車組列車只能擔(dān)任一條列車運(yùn)行線任務(wù)；公式⑺表示在站同一時刻，一條列車運(yùn)行線任務(wù)只能由一列動車組列車擔(dān)任。公式⑻是根據(jù)動車組列車運(yùn)行線之間的接續(xù)在時間及地點(diǎn)上的約束，確定列車運(yùn)行線i與j之間的接續(xù)時間是否可以滿足接續(xù)作業(yè)時長。

1.3 置換策略差分進(jìn)化算法

標(biāo)準(zhǔn)DE算法是種群個體進(jìn)化的隨機(jī)計(jì)算模型，通過設(shè)計(jì)優(yōu)化問題的適應(yīng)度函數(shù)，使對環(huán)境適應(yīng)能力較強(qiáng)的個體存活下來，對環(huán)境適應(yīng)能力較低的個體淘汰，符合適者生存的規(guī)律[13]。由于標(biāo)準(zhǔn)DE算法采用浮點(diǎn)數(shù)編碼，使變異算子的運(yùn)算對于離散域上正整數(shù)編碼不封閉。因此，為了使差分變異算子保留原來的計(jì)算方式與特點(diǎn)，針對正整數(shù)編碼的種群初始個體，DEP算法依據(jù)抽象代數(shù)置換群理論，重新定義變異算子的運(yùn)算，包括加法、減法和乘法運(yùn)算。

定義 1 ：設(shè)σ1，σ2∈Sx(n)，則置換σ1與σ2的離散加法定義如下。

定義 2 ：設(shè)σ1，σ2∈Sx(n)，由σ1σ2* (σ2-1*σ1)，則置換σ1與σ2的離散減法定義如下。

定 義 3 ： 設(shè)F∈[0，1]，σ∈Sx(n)，H?Sx(n)，由Sx(n)=，則標(biāo)量F與置換σ的離散乘法定義如下。

式中：k=「F·L?，其中數(shù)學(xué)符號「w?表示不超過w的最小整數(shù)。

在公式⑾中，F(xiàn)·σ稱為置換的截?cái)嗖僮?。而置換群σ的生成子集不惟一，則置換σ由簡單換位序列的最少表示方式不惟一，因而F·σ通常也不惟一。因此，為了設(shè)計(jì)一個切實(shí)可行的變異策略，根據(jù)文獻(xiàn)[13]生成集的產(chǎn)生方法，采用一個隨機(jī)的冒泡排序(Randomizes Bubble Sort algorithm，RandBS)算法，這樣可以得到置換σ的最短簡單換位序列，具體執(zhí)行步驟如下。

步驟1：初始化集合CC，用來保存置換的交換位置序列。

步驟 2 ：INV={z |σ(z) ＞σ(z+ 1)}，即集合INV包含置換σ到單位元的一種簡單交換排序。

步驟3：如果集合INV≠?，則執(zhí)行步驟4；否則執(zhí)行步驟9。

步驟4：從集合INV中，隨機(jī)取一個元素z并刪除。

步驟5：交換置換σ的第z個元素和第(z+ 1)個元素，得到一個新的置換σ。

步驟6：把置換的交換序列τ z,z+1保存到集合CC中。

步 驟 7： 如 果z＞ 1 并 且z- 1 ?INV， 并 且σ(z- 1) ＞σ(z)，則將 (z- 1)保存到集合INV中；否則執(zhí)行步驟8。

步驟 8：如果z＞n- 1 并且z+ 1 ?INV，并且σ(z+ 1) ＞σ(z+ 2)，則把 (z+ 1)保存到集合INV中；否則返回步驟4。

步驟9：將集合CC中的元素按逆序排列并輸出。

定義1、定義2給出非空集合A上的2種二元運(yùn)算⊕和Θ，定義3給出A上的一元運(yùn)算?，且假定運(yùn)算?的優(yōu)先級高于⊕和Θ，則標(biāo)準(zhǔn)差分變異算子重新定義為

2 基于DEP算法的動車組周轉(zhuǎn)接續(xù)優(yōu)化

2.1 解的表示與初始化

由于樞紐車站Nh的到達(dá)列車與始發(fā)列車數(shù)目相同，即，因而樞紐車站Nh的動車組周轉(zhuǎn)接續(xù)關(guān)系可以表示為D×D的矩陣；又根據(jù)公式⑹和公式⑺惟一性條件，定義動車組周轉(zhuǎn)接續(xù)關(guān)系矩陣的橫向表示車站終到動車組列車數(shù)量，縱向表示車站始發(fā)動車組列車數(shù)量；如果在車站Nh，將掛線運(yùn)行第i條到達(dá)的動車組列車運(yùn)行線接續(xù)第j條始發(fā)列車運(yùn)行線，則=1，否則

采用正整數(shù)排列的編碼方法，建立車站Nh終到車次—始發(fā)車次接續(xù)對，作為DEP算法的初始個體，正整數(shù)在排列中的位置表示終到列車，整數(shù)值表示始發(fā)列車。因此，建立正整數(shù)1 ～n的隨機(jī)排列σl(l=1，2，…，NP)，將其作為初始種群的個體。

2.2 差分進(jìn)化操作

DEP算法的差分進(jìn)化操作包括變異、交叉和選擇操作。設(shè)第l個目標(biāo)個體、變異個體和試驗(yàn)個體分別為，和。

2.2.1 變異

DE算法在個體進(jìn)化過程中，選擇合適的控制參數(shù)F對算法的優(yōu)化性能具有重要的影響作用，借鑒文獻(xiàn)[14]提到的方式對F的調(diào)節(jié)策略計(jì)算如下。

式中：fr0，fr1，fr2分別是 3 個隨機(jī)個體σr0，σr1，σr2的適應(yīng)度函數(shù)值，F(xiàn)min=0.1；Fmax=0.9。

對于目標(biāo)個體，變異個體產(chǎn)生方式具體步驟如下。

步驟3：采用RandBS算法，執(zhí)行置換δ的截?cái)嗖僮?，即S=RandBS (δ)。

步驟4：計(jì)算k=「F·L?。

步驟5：把置換賦值給。

步驟6：從l=1，……，k，對置換按位置序列Sl進(jìn)行交換排序。

步驟7：結(jié)束，得到變異個體。

2.2.2 交叉

在變異操作之后，對目標(biāo)個體和變異個體進(jìn)行交叉操作。為保留個體優(yōu)良信息及避免最優(yōu)解遭到破壞，在二項(xiàng)式交叉策略基礎(chǔ)上，在個體編碼中隨機(jī)設(shè)置交叉點(diǎn)并進(jìn)行部分基因交換，具體操作步驟如下。

步驟1：隨機(jī)設(shè)置交叉點(diǎn)p，1 ＜p＜n。

步驟3：產(chǎn)生區(qū)間(0，1)內(nèi)的隨機(jī)數(shù)rand (0，1)，如果與中的元素不重復(fù)，rand (0，1) ＜ CR，則

步驟4：將變異個體向量中不同于中剩余的元素按照隨機(jī)排列的順序依次放到中空缺的位置。

2.2.3 選擇

為了評估每個個體對于式中目標(biāo)函數(shù)值的優(yōu)劣，采用“貪婪”選擇策略，根據(jù)目標(biāo)個體和試驗(yàn)個體u gl的目標(biāo)函數(shù)值f(·)來選擇最優(yōu)個體。為了避免DEP算法搜索停滯，引入一定選擇概率的貪婪選擇策略來更新種群，具體操作方式為

式中：r是區(qū)間[0，1]隨機(jī)產(chǎn)生的數(shù)；tg=max{0，Q－△1，Q－△2}，其中Q為選擇參數(shù)，是[0，1]區(qū)間的常數(shù)，△1，△2為相對適應(yīng)度值的偏差量，即

3 仿真實(shí)驗(yàn)與結(jié)果分析

仿真實(shí)驗(yàn)分為2個部分。第一部分仿真實(shí)驗(yàn)分為4組，每組包括車站Nh到達(dá)動車組列車數(shù)目D取值不同的3個算例，確定DEP算法的控制參數(shù)。第二部分仿真實(shí)驗(yàn)以武廣客運(yùn)專線的長沙站為例，驗(yàn)證DEP算法在求解動車組周轉(zhuǎn)接續(xù)優(yōu)化問題方面的有效性。仿真實(shí)驗(yàn)在Matlab環(huán)境下編程，在2.50 GHz 的 Intel 雙核 CPU 及 Win10 操作系統(tǒng)的電腦上運(yùn)行。

3.1 DEP算法參數(shù)設(shè)置

DEP算法參數(shù)初步設(shè)置：NP取值為5D，10D；F取值為0.5；交叉率CR取值為0.9，選擇參數(shù)Q取值為0.01，0.02[15]，這樣構(gòu)成12種組合。選擇車站到達(dá)列車數(shù)目(或從車站始發(fā)的列車數(shù)目)D為20，50，100共3個算例，每個算例運(yùn)行20次，運(yùn)算迭代次數(shù)的最大數(shù)目為1 000，將車站Nh動車組周轉(zhuǎn)接續(xù)時間的平均相對偏差率(the Average Relative Percentage Deviation，ARPD)和最優(yōu)解(Best)指標(biāo)值作為響應(yīng)值，得到4×3×2=24個數(shù)據(jù)點(diǎn)，數(shù)值實(shí)驗(yàn)結(jié)果如表1所示。在表1中，ARPD和Best指標(biāo)值中的最優(yōu)解用粗體表示；指標(biāo)值A(chǔ)RPD按照以下公式計(jì)算

式中：Algi為算法獨(dú)立運(yùn)算求解第i次得到的最好結(jié)果；Best為算法獨(dú)立運(yùn)算求解20次得到的結(jié)果中的最短動車組周轉(zhuǎn)接續(xù)時間。

表1 數(shù)值實(shí)驗(yàn)結(jié)果Tab.1 Numerical experimental results

表1給出了DEP算法在車站到達(dá)列車數(shù)目的3個規(guī)模算例下獲得的Best值和ARPD值。根據(jù)指標(biāo)值A(chǔ)RPD的定義：該計(jì)算結(jié)果值越小，表明算法找到的最優(yōu)解在收斂性和多樣性上越趨向參考解?？梢?，對車站到達(dá)列車數(shù)目的3個規(guī)模算例，算法在NP取值為10D所得Best值比NP取值為5D時具有明顯的優(yōu)勢，相應(yīng)地ARPD值也較好，因而NP取值為10D較合適。同時，算法在選擇參數(shù)Q取值為0.02的情況下所得的Best值比Q取值為0.01時較好；對20組動車的較小規(guī)模，Q取值為0.02所得ARPD值較小。而對于50，100組動車組列車的較大規(guī)模算例，Q取值為0.02情況下所得的ARPD值明顯差于Q取值為0.01。

針對選擇參數(shù)Q的取值，選擇上述3個算例，比較DEP算法在NP取值為10D，Q取值為0.01，0.02情況下的收斂性能及求解質(zhì)量，獨(dú)立運(yùn)行求解20次平均最短接續(xù)時間的收斂曲線，分別如圖1—圖3所示。

圖1 車站到達(dá)列車數(shù)目D =20時的收斂曲線Fig.1 Convergence curve of the number of trains arriving at the station, D=20

圖2 車站到達(dá)列車數(shù)目D =50時的收斂曲線Fig.2 Convergence curve of the number of trains arriving at the station, D=50

圖1、圖2、圖3的結(jié)果表明，對車站到達(dá)列車數(shù)目D取值為20，100的算例，選擇參數(shù)Q取值為0.01的情況下，DEP算法僅需較少迭代次數(shù)即可達(dá)到收斂，然而不能求得最優(yōu)的動車組周轉(zhuǎn)方案，僅是一個局部最優(yōu)解；Q取值為0.02情況下，DEP算法雖說需要更多的迭代次數(shù)才能達(dá)到收斂，但卻可以獲得全局最優(yōu)解。而對50組動車組列車的規(guī)模，Q取值0.01比Q取值0.02對DEP算法的收斂速度更快，但都能取得相同的最優(yōu)值。綜上所述，在動車組周轉(zhuǎn)優(yōu)化問題中，DEP算法的選擇參數(shù)Q取值為0.02更為合適，具有更好地平衡算法快速收斂特性和全局最優(yōu)解2個特點(diǎn)。

圖3 車站到達(dá)列車數(shù)目D =100時的收斂曲線Fig.3 Convergence curve of the number of trains arriving at the station, D=100

3.2 DEP算法求解動車組周轉(zhuǎn)接續(xù)優(yōu)化問題

3.2.1 數(shù)值及收斂性

選取武廣客運(yùn)專線的長沙站為實(shí)例，2018年春運(yùn)期間長沙南站(CS)—廣州南站(GZ)區(qū)間開行36對/d動車組列車(全部為運(yùn)營列車)，各列車的到發(fā)時刻如表2所示[16]。

運(yùn)用DEP優(yōu)化算法求解動車組周轉(zhuǎn)優(yōu)化問題。通過上述初步實(shí)驗(yàn)分析，NP取值為10D較為合適；在小規(guī)模動車組周轉(zhuǎn)優(yōu)化問題中，選擇參數(shù)Q取值應(yīng)為0.02較為合適，DEP算法參數(shù)設(shè)置如表3所示。DEP算法在實(shí)例中運(yùn)行20次得到在站所有動車組列車接續(xù)時間的最大值、最小值和均值±方差，DEP數(shù)值結(jié)果如表4所示，DEP收斂性能如圖4所示。

從表4看出， DEP算法取得較好的最大值、最小值及均值，由此可說明DEP算法的可行性。

從圖4可以看出，DEP算法盡管需要更多的迭代次數(shù)才能收斂，但獲得了更好的全局最優(yōu)解。因此， DEP算法不僅能尋得車站動車組列車周轉(zhuǎn)接續(xù)最短接續(xù)時間，而且具有較好的收斂性能。

表2 長沙站(CS)動車組列車的到發(fā)情況Tab.2 Arrival and departure of Changsha Station EMUs

表3 DEP算法參數(shù)設(shè)置Tab.3 DEP algorithm parameter settings

3.2.2 CS站動車組列車的接續(xù)

根據(jù)表2中CS站動車組列車的終到、始發(fā)時刻，針對CS站的36對/d動車組列車，運(yùn)用DEP算法進(jìn)行計(jì)算，得到所有動車組列車在站最短周轉(zhuǎn)接續(xù)時間總和為14 379 min，平均動車組列車接續(xù)時間為399.42 min，CS站動車組周轉(zhuǎn)接續(xù)關(guān)系如表5所示。

由表5可知，CS站的始發(fā)列車和終到列車之間的折返接續(xù)狀況較理想， CS站始發(fā)列車和終到列車均在同一周期發(fā)生折返接續(xù)，而且接續(xù)時間相對均衡。由此證明，用DEP算法求解動車組周轉(zhuǎn)優(yōu)化問題可行，而且DEP算法能夠較好地平衡算法快速收斂性和全局最優(yōu)解2個特點(diǎn)。

表4 DEP數(shù)值結(jié)果Tab.4 Numerical result of DEP

圖4 DEP的收斂性能Fig.4 Convergence performance of DEP

表5 CS站動車組周轉(zhuǎn)接續(xù)關(guān)系Tab.5 Relation between train turnover and continuity of Changsha Station EMUs

4 結(jié)束語

為了使所有動車組在站停留時間總和最小，構(gòu)建高速鐵路動車組列車周轉(zhuǎn)接續(xù)優(yōu)化數(shù)學(xué)模型，并且運(yùn)用DEP算法進(jìn)行求解。該DEP算法采用正整數(shù)排列編碼，借鑒連續(xù)空間DE算法的基本特征，通過產(chǎn)生相鄰交換次數(shù)最佳的隨機(jī)冒泡排序算法策略來定義差分變異算子，使其能直接作用在正整數(shù)排列搜索空間，同時修正交叉策略，采用具有一定選擇概率的貪婪選擇策略來更新種群，避免個體在進(jìn)化過程基因塊的破壞，提高算法尋找動車組最優(yōu)周轉(zhuǎn)方案的有效性。最后，以武廣客運(yùn)專線的長沙站為例進(jìn)行仿真實(shí)驗(yàn)，針對長沙站動車組周轉(zhuǎn)接續(xù)優(yōu)化問題，DEP算法具有較強(qiáng)的尋優(yōu)能力和魯棒性，體現(xiàn)收斂速度和全局最優(yōu)解的折中優(yōu)勢，得到很好的效果。