高 楊，郭紅戈

GAO Yang，GUO Hongge

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

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

0 引言

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

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

動(dòng)車(chē)組周轉(zhuǎn)接續(xù)優(yōu)化問(wèn)題是具有離散決策變量性質(zhì)的組合優(yōu)化問(wèn)題，合理安排列車(chē)運(yùn)行圖任務(wù)間的接續(xù)關(guān)系，使所有動(dòng)車(chē)組列車(chē)在車(chē)站周轉(zhuǎn)接續(xù)時(shí)間總和最小。動(dòng)車(chē)組周轉(zhuǎn)接續(xù)優(yōu)化問(wèn)題，其復(fù)雜性隨著動(dòng)車(chē)組數(shù)量的增加而不斷地變大，經(jīng)過(guò)對(duì)智能優(yōu)化算法進(jìn)行大量研究后發(fā)現(xiàn)，盡管動(dòng)車(chē)組列車(chē)周轉(zhuǎn)接續(xù)優(yōu)化運(yùn)算規(guī)模很大，卻能得到一個(gè)最接近可以被接受的優(yōu)化解，為這類(lèi)優(yōu)化問(wèn)題的求解提供較好的方法。而差分進(jìn)化算法(Differential Evolution，DE)作為一種群體智能優(yōu)化方法，采用浮點(diǎn)數(shù)編碼，具有實(shí)現(xiàn)簡(jiǎ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ī)制，利用其簡(jiǎn)單高效的優(yōu)點(diǎn)，提出一種置換策略差分進(jìn)化算法(Differential Evolution for the Permutations space，DEP)來(lái)求解動(dòng)車(chē)組周轉(zhuǎn)優(yōu)化問(wèn)題，得到動(dòng)車(chē)組的優(yōu)化周轉(zhuǎn)方式。

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

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

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

令為動(dòng)車(chē)組列車(chē)在車(chē)站h的周轉(zhuǎn)接續(xù)時(shí)間，可表示為

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

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

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

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

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

標(biāo)準(zhǔn)DE算法是種群個(gè)體進(jìn)化的隨機(jī)計(jì)算模型，通過(guò)設(shè)計(jì)優(yōu)化問(wèn)題的適應(yīng)度函數(shù)，使對(duì)環(huán)境適應(yīng)能力較強(qiáng)的個(gè)體存活下來(lái)，對(duì)環(huán)境適應(yīng)能力較低的個(gè)體淘汰，符合適者生存的規(guī)律[13]。由于標(biāo)準(zhǔn)DE算法采用浮點(diǎn)數(shù)編碼，使變異算子的運(yùn)算對(duì)于離散域上正整數(shù)編碼不封閉。因此，為了使差分變異算子保留原來(lái)的計(jì)算方式與特點(diǎn)，針對(duì)正整數(shù)編碼的種群初始個(gè)體，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é)符號(hào)「w?表示不超過(guò)w的最小整數(shù)。

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

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

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

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

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

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

步驟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)先級(jí)高于⊕和Θ，則標(biāo)準(zhǔn)差分變異算子重新定義為

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

2.1 解的表示與初始化

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

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

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

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

2.2.1 變異

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

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

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

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

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

步驟5：把置換賦值給。

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

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

2.2.2 交叉

在變異操作之后，對(duì)目標(biāo)個(gè)體和變異個(gè)體進(jìn)行交叉操作。為保留個(gè)體優(yōu)良信息及避免最優(yōu)解遭到破壞，在二項(xiàng)式交叉策略基礎(chǔ)上，在個(gè)體編碼中隨機(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：將變異個(gè)體向量中不同于中剩余的元素按照隨機(jī)排列的順序依次放到中空缺的位置。

2.2.3 選擇

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

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

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

仿真實(shí)驗(yàn)分為2個(gè)部分。第一部分仿真實(shí)驗(yàn)分為4組，每組包括車(chē)站Nh到達(dá)動(dòng)車(chē)組列車(chē)數(shù)目D取值不同的3個(gè)算例，確定DEP算法的控制參數(shù)。第二部分仿真實(shí)驗(yàn)以武廣客運(yùn)專(zhuān)線(xiàn)的長(zhǎng)沙站為例，驗(yàn)證DEP算法在求解動(dòng)車(chē)組周轉(zhuǎn)接續(xù)優(yōu)化問(wèn)題方面的有效性。仿真實(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種組合。選擇車(chē)站到達(dá)列車(chē)數(shù)目(或從車(chē)站始發(fā)的列車(chē)數(shù)目)D為20，50，100共3個(gè)算例，每個(gè)算例運(yùn)行20次，運(yùn)算迭代次數(shù)的最大數(shù)目為1 000，將車(chē)站Nh動(dòng)車(chē)組周轉(zhuǎn)接續(xù)時(shí)間的平均相對(duì)偏差率(the Average Relative Percentage Deviation，ARPD)和最優(yōu)解(Best)指標(biāo)值作為響應(yīng)值，得到4×3×2=24個(gè)數(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é)果中的最短動(dòng)車(chē)組周轉(zhuǎn)接續(xù)時(shí)間。

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

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

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

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

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

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

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

3.2 DEP算法求解動(dòng)車(chē)組周轉(zhuǎn)接續(xù)優(yōu)化問(wèn)題

3.2.1 數(shù)值及收斂性

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

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

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

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

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

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

3.2.2 CS站動(dòng)車(chē)組列車(chē)的接續(xù)

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

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

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

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

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

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

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