閆 璐，張 琦，丁舒忻，王榮笙,

（1. 中國鐵道科學(xué)研究院研究生部，北京 100081；2. 中國鐵道科學(xué)研究院集團(tuán)有限公司通信信號研究所，北京 100081；3. 中國鐵道科學(xué)研究院集團(tuán)有限公司國家鐵路智能運(yùn)輸系統(tǒng)工程技術(shù)研究中心，北京 100081）

高速鐵路列車運(yùn)行存在“高密度”的特征［1］，一旦受到突發(fā)事件影響，往往會引發(fā)列車晚點(diǎn)，并在線路和路網(wǎng)中傳播，情況嚴(yán)重時會給運(yùn)輸組織和旅客正常出行造成極大影響。根據(jù)晚點(diǎn)的原因和程度，可將引發(fā)晚點(diǎn)的內(nèi)外界擾動分為2 種類型：一種是一般干擾，如旅客乘降作業(yè)超時等；另一種是嚴(yán)重干擾，如因風(fēng)、雨、雪等自然災(zāi)害或設(shè)備故障產(chǎn)生的長時間封鎖等［2］。無論哪種干擾，均將導(dǎo)致列車運(yùn)行在一定程度上偏離既定計(jì)劃的后果，此時就需要進(jìn)行列車運(yùn)行調(diào)整。列車運(yùn)行調(diào)整是實(shí)現(xiàn)“按圖行車”的關(guān)鍵，也是高速鐵路列車安全、高效、有序、正點(diǎn)運(yùn)行的基礎(chǔ)［3］。

國內(nèi)外眾多學(xué)者已對列車運(yùn)行調(diào)整問題開展了大量研究［4-7］。現(xiàn)階段的研究通?？紤]多個優(yōu)化目標(biāo)，其中減少列車總晚點(diǎn)時間多為主要目標(biāo)，其他優(yōu)化目標(biāo)包括提高旅客滿意度、減少取消列車數(shù)量等。這些需要優(yōu)化的目標(biāo)之間往往互相沖突，需要權(quán)衡決策者對不同優(yōu)化目標(biāo)的偏好程度，從而得到不同的帕累托（Pareto）最優(yōu)解。目前大部分研究采用前決策（a priori）的方式［8-14］，考慮決策者已經(jīng)提供了全局偏好信息，在此基礎(chǔ)上搜尋該偏好下的一個Pareto 最優(yōu)解。LI 等［8］針對車站股道封鎖不確定恢復(fù)時間，考慮最小化晚點(diǎn)成本和股道調(diào)整成本，建立混合整數(shù)非線性規(guī)劃模型，采用2 階段法求解，第1階段通過貪心算法求解列車調(diào)整后的到發(fā)時間和次序，并在該決策方案下采用遺傳算法調(diào)整車站股道，完成第2 階段求解。文獻(xiàn)［9—13］均考慮最小化取消列車趟數(shù)和總晚點(diǎn)時間，通過商用求解器CPLEX 或GUROBI 求解。WANG 等［14］針對初始晚點(diǎn)，以最小化列車總晚點(diǎn)時間和嚴(yán)重晚點(diǎn)列車趟數(shù)為優(yōu)化目標(biāo)，建立混合整數(shù)規(guī)劃模型，并提出遺傳算法結(jié)合粒子群算法的求解方法。目前大部分文獻(xiàn)都采用對不同優(yōu)化目標(biāo)線性加權(quán)的形式確定決策者偏好信息，這樣雖然不需要大量計(jì)算，但決策者的全局偏好信息并不能準(zhǔn)確獲得。

還有部分研究采用后決策（a posteriori）方式，即先搜索整個Pareto前沿，再在該前沿中選擇最偏好的解。該方法并不需要知道決策者的全局偏好信息，而且可找到整個Pareto 前沿的近似解集，但需要很大的計(jì)算代價(jià)。SHAKIBAYIFAR 等［15］針對區(qū)間封鎖，以最小化列車終點(diǎn)站晚點(diǎn)時間和最小化列車發(fā)車運(yùn)行偏差建立雙目標(biāo)優(yōu)化模型，采用多目標(biāo)鄰域搜索算法求解。BINDER 等［16］針對車站存在多個股道封鎖，考慮最小化旅客不滿意度（換乘時間）、運(yùn)營成本和調(diào)整成本，建立整數(shù)規(guī)劃模型，通過CPLEX 結(jié)合ε-約束法進(jìn)行求解。ALTAZIN 等［17］針對列車晚點(diǎn)，考慮最小化恢復(fù)時間、旅客不滿意度（等待時間和車內(nèi)時間）、調(diào)整操作（如取消車次、列車折返、增加停站、跳停等）總數(shù)、總晚點(diǎn)時間和晚點(diǎn)事件個數(shù)，采用啟發(fā)式方法求解并通過仿真進(jìn)行評價(jià)。然而上述研究并未計(jì)算整個Pareto前沿，缺失了部分非支配解。

針對高速鐵路列車運(yùn)行中的晚點(diǎn)情況，綜合考慮區(qū)間運(yùn)行干擾和車站停車作業(yè)干擾，通過調(diào)整列車到發(fā)時刻和列車次序，以最小化列車總晚點(diǎn)時間和列車到發(fā)時刻調(diào)整次數(shù)為雙優(yōu)化目標(biāo)，建立高速鐵路列車運(yùn)行調(diào)整的混合整數(shù)非線性規(guī)劃模型，并通過定義輔助矩陣將其轉(zhuǎn)化為線性規(guī)劃模型；提出改進(jìn)的ε-約束法求解模型。通過算例以及加權(quán)法和先到先服務(wù)方法對比，驗(yàn)證模型和求解算法。

1 優(yōu)化模型

以最小化列車總晚點(diǎn)時間和最小化列車到發(fā)時刻調(diào)整次數(shù)為雙優(yōu)化目標(biāo)，以車站作業(yè)、區(qū)間運(yùn)行、追蹤間隔等時間條件為約束條件，構(gòu)建高速鐵路列車運(yùn)行調(diào)整的雙目標(biāo)優(yōu)化模型。

1.1 模型假設(shè)

結(jié)合實(shí)際情況首先做如下假設(shè)：

（1）列車運(yùn)行調(diào)整的方式包括調(diào)整列車到發(fā)時刻和列車次序；

（2）突發(fā)事件最終表征為列車在區(qū)間運(yùn)行時和在車站停車作業(yè)時受到的干擾；

（3）車站均滿足接發(fā)車能力限制。

1.2 模型參數(shù)和決策變量定義

定義模型參數(shù)：i，l為列車編號；N為列車總數(shù)；j為車站編號；J為車站總數(shù)；k為區(qū)間編號；K為區(qū)間總數(shù)；τsij為列車i在車站j的圖定到站時刻；τeij為列車i在車站j的圖定發(fā)車時刻；αi為列車i的始發(fā)站車站編號；βi為列車i的終到或交出站車站編號；為列車i在車站j的最小作業(yè)時間（停站時間）；為列車i在區(qū)間k的最小運(yùn)行時間；Ik為區(qū)間k的最小追蹤間隔時間；M為足夠大的正整數(shù)；為列車i在區(qū)間k受到干擾時增加的區(qū)間運(yùn)行時間（區(qū)間運(yùn)行干擾時間）；為列車i在車站j受到干擾時增加的車站停車作業(yè)時間（車站停車作業(yè)干擾時間）；為含有區(qū)間運(yùn)行干擾的列車及對應(yīng)的區(qū)間集合；為含有車站停車作業(yè)干擾的列車及對應(yīng)的車站集合。

定義決策變量：xsij為列車i在車站j的實(shí)際到站時刻；xeij為列車i在車站j的實(shí)際發(fā)車時刻；qilk為0-1 決策變量，表示列車i和列車l在區(qū)間k的實(shí)際次序，當(dāng)列車i先于列車l進(jìn)入?yún)^(qū)間k時取值為1，否則取值為0。

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

受到晚點(diǎn)影響后調(diào)度部門需要進(jìn)行列車運(yùn)行調(diào)整，使列車盡快恢復(fù)正點(diǎn)運(yùn)行。對于受到影響的列車來說，在不同車站調(diào)整到發(fā)時間，會影響車站當(dāng)前作業(yè)，增加相關(guān)作業(yè)人員負(fù)擔(dān)。因此，以最小化列車總晚點(diǎn)時間和最小化列車到發(fā)時刻調(diào)整次數(shù)為目標(biāo)函數(shù)。

1）列車總晚點(diǎn)時間最少

定義列車總晚點(diǎn)時間等于運(yùn)行調(diào)整之后所有列車到站時刻與圖定到站時刻的差值加上列車發(fā)車時刻與圖定發(fā)車時刻的差值，則列車總晚點(diǎn)時間最少的目標(biāo)函數(shù)f1(x)可表示為

其中，

式中：x為實(shí)際到站時刻和實(shí)際發(fā)車時刻。

2）列車到發(fā)時刻調(diào)整次數(shù)最少

定義列車到發(fā)時刻調(diào)整次數(shù)等于所有列車到站和發(fā)車的總晚點(diǎn)次數(shù)，即晚點(diǎn)1次就需要調(diào)整1次，則列車到發(fā)時刻調(diào)整次數(shù)最少的目標(biāo)函數(shù)f2(x)可表示為

式中：sgn（·）為符號函數(shù)，返回對應(yīng)參數(shù)的正負(fù)號（參數(shù)為0 則返回值為0），由于調(diào)整之后列車到站或發(fā)車時刻不允許早于圖定時刻，返回值不為負(fù)數(shù)，若調(diào)整后列車到站或發(fā)車時刻晚于圖定時刻，則返回值為1，記錄晚點(diǎn)1 次；若等于圖定時刻，則返回值為0，不記錄晚點(diǎn)次數(shù)。

1.4 約束條件

為了保證列車運(yùn)行安全，合理利用接發(fā)列車能力、車站通過能力以及區(qū)間通過能力，建立的模型應(yīng)滿足如下約束條件。

1）車站停站時間約束

列車i在車站j存在停車作業(yè)干擾時對運(yùn)行圖的影響如圖1所示。圖中：黑色實(shí)線表示計(jì)劃運(yùn)行線，對應(yīng)停站時間為圖定停站時間；紅色虛線表示最小停站時間下的運(yùn)行線；藍(lán)色虛線表示含有車站停車作業(yè)干擾時間下的運(yùn)行線，此時列車停站時間在圖定停站時間基礎(chǔ)上增加干擾時間，該干擾時間為車站停站緩沖時間吸收之后的干擾時間。

圖1 車站停車作業(yè)存在干擾時對運(yùn)行圖的影響

對于含有車站停車作業(yè)干擾的列車，調(diào)整之后的列車停站時間必須不小于該列車在該站的圖定停站時間與車站停車作業(yè)干擾時間之和；對于不含車站停車作業(yè)干擾的列車，調(diào)整之后的列車停站時間必須不小于該列車在該站的最小停站時間，即

式中：(i，j)∈Tdwell，dis和(i，j)?Tdwell，dis分別為含有、不含車站停車作業(yè)干擾的列車及對應(yīng)的車站。

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

列車i在區(qū)間k存在區(qū)間運(yùn)行干擾時對運(yùn)行圖的影響如圖2所示。圖中：黑色實(shí)線表示計(jì)劃運(yùn)行線，對應(yīng)區(qū)間運(yùn)行時間為圖定運(yùn)行時間；紅色虛線表示最小區(qū)間運(yùn)行時間下的運(yùn)行線；藍(lán)色虛線表示含有區(qū)間運(yùn)行干擾時間下的運(yùn)行線，此時列車區(qū)間運(yùn)行時間在圖定運(yùn)行時間基礎(chǔ)上增加的干擾時間，即為區(qū)間運(yùn)行緩沖時間吸收之后的干擾時間。

圖2 區(qū)間運(yùn)行時間存在干擾時對運(yùn)行圖的影響

對于含有區(qū)間運(yùn)行干擾的列車，調(diào)整之后的列車區(qū)間運(yùn)行時間必須不小于該列車在該區(qū)間的圖定運(yùn)行時間與區(qū)間運(yùn)行干擾時間之和；對于不含區(qū)間運(yùn)行干擾的列車，調(diào)整之后的列車區(qū)間運(yùn)行時間必須不小于該區(qū)間的最小運(yùn)行時間，即

式中：(i，k)∈Trun，dis和(i，k)?Trun，dis分別指含有、不含區(qū)間運(yùn)行干擾的列車及對應(yīng)的區(qū)間。

3）列車到發(fā)間隔時間約束

對于在同一區(qū)間內(nèi)運(yùn)行的相鄰列車，其到站和發(fā)車間隔時間必須不小于最小追蹤間隔時間，即

式中：∨和∧分別表示“或”和“且”，用于計(jì)算相鄰列車始發(fā)車站編號最大值和相鄰列車終到或交出車站編號最小值；qilk與qlik均為列車在區(qū)間次序的決策變量，二者取值不同，即qilk=1 時qlik=0，qilk=0時qlik=1。

4）列車到發(fā)時刻約束

列車在車站實(shí)際發(fā)車時刻必須不小于圖定發(fā)車時刻與停車作業(yè)干擾時間之和，實(shí)際到站時刻必須不小于圖定到站時刻與區(qū)間運(yùn)行干擾時間之和，即

5）決策變量約束

列車實(shí)際到發(fā)時刻決策變量必須為非負(fù)變量，列車在區(qū)間的次序決策變量必須為0-1變量，即

1.5 模型處理

式（2）中存在sgn（·）符號函數(shù)，因此需要將其轉(zhuǎn)換為線性模型再進(jìn)行處理。定義輔助矩陣c1=[c1，ij]N×J和c2=[c2，ij]N×J，賦值為

通過式（11）將式（2）中的參數(shù)替換，使后者轉(zhuǎn)換為式（12）所示的混合整數(shù)線性規(guī)劃模型。由此建立的列車運(yùn)行調(diào)整雙目標(biāo)優(yōu)化模型P0為

該模型屬于NP-hard問題［3］，無法在多項(xiàng)式時間內(nèi)找到整個Pareto前沿，需要將其轉(zhuǎn)換為單目標(biāo)優(yōu)化模型（例如加權(quán)法或ε-約束法），通過商用求解器（如CPLEX，GUROBI 等）對一定規(guī)模下的問題在合理時間內(nèi)得到Pareto前沿。

1.6 相關(guān)定義

參考文獻(xiàn)［18］，針對本文基于雙目標(biāo)優(yōu)化的高速鐵路列車運(yùn)行調(diào)整問題，引入如下定義。

定義1（Pareto 支配）：目標(biāo)向量u和v為2 個可行解集對應(yīng)的優(yōu)化目標(biāo)，目標(biāo)向量u支配v（記作u?v），當(dāng)且僅當(dāng)ub≤vb，?b∈{1，2，…，B}（B為目標(biāo)個數(shù)），且u≠v。

定義2（Pareto 有效性）：對于可行解x，不存在其他可行解y，其目標(biāo)函數(shù)值構(gòu)成的目標(biāo)向量f(x)和f(y)滿足Pareto支配關(guān)系f(y)?f(x)，則說明解x為Pareto有效性解，又稱為非支配解。

定義3（Pareto 解集，Pareto Set）：所有滿足Pareto 有效性的解的集合稱為Pareto 解集，又稱為非支配解集，記為APS。

定義4（Pareto 前沿，Pareto Front）：所有Pa?reto 最優(yōu)目標(biāo)向量的集合稱為Pareto 前沿，記為APF={f(x)|x∈APS}。

定義5（理想點(diǎn)，Ideal Point）：向量zIdeal=(zIdeal1，…，zIdealB)中每個元素都為每個目標(biāo)函數(shù)fb(x)的最優(yōu)解，可以通過zIdealb=minfb(x)求得理想點(diǎn)。

定義6（最差點(diǎn)，Nadir Point）：向量zNadir=(zNadir1，…，zNadirB)中的每個元素都為每個目標(biāo)函數(shù)fb(x)在Pareto 前沿上的最大值。其中每個元素zNadirb定義為zNadirb=max {fb(x)|x∈APF}。

2 模型求解

求解多目標(biāo)優(yōu)化問題的方法包括ε-約束法和線性加權(quán)法，其原理都是通過將原問題轉(zhuǎn)換為多個不同的單目標(biāo)優(yōu)化問題，從而得到整個Pareto 前沿。其中，ε-約束法是通過將原有多個優(yōu)化目標(biāo)分為主目標(biāo)和其他的次目標(biāo)，并將其他的次目標(biāo)作為約束進(jìn)行單目標(biāo)優(yōu)化求解。相比于線性加權(quán)法，ε-約束法不需要設(shè)置權(quán)重，無需對目標(biāo)函數(shù)進(jìn)行歸一化處理，并能夠得到非凸前沿。

對模型P0，定義ε2∈[zIdeal2，zNadir2]為次目標(biāo)優(yōu)化上界，采用ε-約束法將目標(biāo)函數(shù)f2(x)轉(zhuǎn)化為約束條件，則可將其轉(zhuǎn)化為模型P1，即

通過修改約束右邊的上限ε2，可以得到對應(yīng)的Pareto前沿。

然而ε-約束法還存在以下3 個缺陷［19］：①在Pareto 前沿之外存在一些不必要的計(jì)算；②無法保證得到所有位于Pareto前沿上的解；③當(dāng)優(yōu)化目標(biāo)超過2個時會顯著增加求解時間。因此，需要對ε-約束法進(jìn)行改進(jìn)。目前主流的改進(jìn)方法如增廣ε-約束法（包括AUGMECON［19］和AUGMECON2［20］），雖然通過引入松弛變量、確定理想點(diǎn)和最差點(diǎn)等形式確定了約束范圍，但求解時增加了額外變量，從求解效率來看優(yōu)勢不足。有必要進(jìn)一步改進(jìn)ε-約束法，在克服上述3個缺陷的基礎(chǔ)上實(shí)現(xiàn)高效求解。

分析式（2）可知，優(yōu)化目標(biāo)f2(x)均為整數(shù)情況，可利用理想點(diǎn)和最差點(diǎn)估計(jì)出Pareto前沿的最大個數(shù)。利用每次求解約束優(yōu)化問題得到對應(yīng)的次優(yōu)化目標(biāo)值f2(x?)，便能夠得到下一次優(yōu)化的約束上界。相比于傳統(tǒng)ε-約束法固定約束增量下的求解，這種方法能夠減少不必要的重復(fù)非支配解的計(jì)算；相比于增廣ε-約束法，這種方法不僅可減少對輔助變量的使用，還能夠在無須為設(shè)置均勻分布的格點(diǎn)的基礎(chǔ)上保證求解到整個Pareto前沿。

采用改進(jìn)ε-約束法求解模型P1的步驟如下。

步驟1：計(jì)算理想點(diǎn)，求解不含式（12）的優(yōu)化模型P0，得到zIdeal1；求解不含式（1）的優(yōu)化模型P0，得到zIdeal2。

步驟2：計(jì)算最差點(diǎn)，求解不含式（12）的優(yōu)化模型P0，求解時增加額外約束f2(x)=zIdeal2，得到zNadir1；求解不含式（1）的優(yōu)化模型P0，求解時增加額外約束f1(x)=zIdeal1，得到zNadir2。

步驟3：確定次優(yōu)化目標(biāo)取值范圍，設(shè)定約束為次優(yōu)化目標(biāo)最大值；根據(jù)理想點(diǎn)和最差點(diǎn)得到目標(biāo)函數(shù)f2(x)的范圍為[zIdeal2，zNadir2]，求解最多（zNadir2-zIdeal2+1）個約束單目標(biāo)模型P1 得到對應(yīng)Pareto前沿，并令ε2=zNadir2，得到對應(yīng)的模型P1。

步驟4：在設(shè)置的約束下計(jì)算調(diào)整方案，求解模型P1 得到當(dāng)前最優(yōu)解x?，記錄解[f1(x?)，f2(x?)]。

步驟5：更新約束值，令ε2=f2(x?)-1。

步驟6：判斷約束值是否為次優(yōu)化目標(biāo)最小值，如果ε2≠zIdeal2，則轉(zhuǎn)步驟4；如果ε2=zIdeal2，則繼續(xù)步驟7。

步驟7：輸出Pareto 前沿，將步驟4 中不同約束下求解模型P1 得到的解合并，去除其中的支配解，最終構(gòu)成了模型P0對應(yīng)的Pareto前沿。

此外，若決策者僅對部分Pareto 前沿感興趣，可以在目標(biāo)函數(shù)f2(x)的范圍[zIdeal2，zNadir2]內(nèi)選擇優(yōu)化求解部分模型P1，得到部分感興趣的非支配解。

3 算例分析

選取京滬高鐵北京南—泰安區(qū)段為例，設(shè)置3 種干擾場景，采用本文模型和改進(jìn)ε-約束求解算法進(jìn)行列車運(yùn)行優(yōu)化調(diào)整；并與同樣采用本文模型但模型求解時分別采用加權(quán)法和先到先服務(wù)（First-Come-First-Served，F(xiàn)CFS）的啟發(fā)式策略（簡稱為FCFS 法）得到的結(jié)果進(jìn)行比較，驗(yàn)證本文模型和改進(jìn)ε-約束法的合理性、有效性。

3.1 算例及參數(shù)說明

北京南—泰安區(qū)段共有7 個車站，自北京南開始依次編號為1，2，…，7。6 個區(qū)間的最小運(yùn)行時間見表1。車站最小停站時間為2 min，相鄰列車最小追蹤間隔為4 min，M取值為1 000。下行開行列車40趟。

表1 區(qū)間最小運(yùn)行時間tmin，run ik

根據(jù)不同的干擾情況（區(qū)間運(yùn)行干擾、車站停車作業(yè)干擾），設(shè)置以下3個場景。

場景1：僅由車站停車作業(yè)干擾組成。設(shè)置列車2在北京南停車作業(yè)干擾時間為20 min，列車20在廊坊停車作業(yè)干擾時間為20 min，列車30 在北京南停車作業(yè)干擾時間20 min。

場景2：僅由區(qū)間運(yùn)行干擾組成。設(shè)置列車4在北京南—廊坊區(qū)間運(yùn)行干擾時間為15 min，列車18在廊坊—天津南區(qū)間運(yùn)行干擾時間為20 min，列車32在北京南—廊坊區(qū)間運(yùn)行干擾時間為20 min。

場景3：由上述2種干擾共同組成。設(shè)置列車3在北京南停車作業(yè)干擾時間20 min，列車25在廊坊停車作業(yè)干擾時間10 min，列車33在北京南停車作業(yè)干擾時間15 min；列車6 在北京南—廊坊區(qū)間運(yùn)行干擾時間為15 min，列車15在廊坊—天津南區(qū)間運(yùn)行干擾時間為20 min，列車28在北京南—廊坊區(qū)間運(yùn)行干擾時間為20 min。

對于上述場景中未提及的列車及其途經(jīng)區(qū)間和車站，均為正常場景，即其對應(yīng)的區(qū)間運(yùn)行干擾時間和車站停車作業(yè)干擾時間均為0。

3.2 多目標(biāo)優(yōu)化性能指標(biāo)

為了驗(yàn)證本文提出的改進(jìn)ε-約束法的性能，采用了下面經(jīng)典的多目標(biāo)優(yōu)化性能指標(biāo)。

非支配解個數(shù)（Number of non-dominated so?lutions，NNS）：該性能指標(biāo)描述了算法得到的近似Pareto前沿，NNS值越大說明該算法求解能力越強(qiáng)。

逆代距（Inverted generational distance，IGD）［21］：該指標(biāo)綜合評價(jià)了非支配解集的收斂性和多樣性，IGD值越小，說明非支配解集A的質(zhì)量越好。假設(shè)Ψ?為1個均勻分布在Pareto真實(shí)前沿的集合，Ψ為1個非支配解集，則Ψ的IGD值IIGD定義為

式中：v為解集Ψ?中的1 個解；d(v，Ψ)為v和Ψ中所有點(diǎn)的最短歐氏距離；|Ψ?|為集合Ψ?的勢。

超體積（Hypervolume，HV）［21］：該指標(biāo)通過非支配解和參考點(diǎn)，計(jì)算出超體積。該性能指標(biāo)同時評價(jià)了非支配解集的收斂性和多樣性。HV 的值越大，對應(yīng)算法的性能越好。對于雙目標(biāo)優(yōu)化問題中的一個非支配解集A，其HV值IHV計(jì)算如下

式中：xi為非支配解集A中的1個解；Vi為解xi對應(yīng)的目標(biāo)值f(xi)和參考點(diǎn)為邊界構(gòu)成的矩形體積。

3.3 計(jì)算結(jié)果

針對3.1 節(jié)中給出的3 種干擾場景，在Intel Core i5-8265U CPU 1.60GHz，8GB 內(nèi)存，操作系統(tǒng)Windows 10，64 位主機(jī)上分別采用改進(jìn)ε-約束法、加權(quán)法和FCFS 法求解本文模型。其中改進(jìn)ε-約束法和加權(quán)法均采用商用求解器GUROBI 9.1.0，通過YALMIP 工具包［22］在Matlab R2018b進(jìn)行仿真求解。GUROBI 各參數(shù)采用默認(rèn)值。加權(quán)法以w1f1(x)+(1-w1)f2(x)為優(yōu)化目標(biāo)，其中w1取范圍［0，1］之間的均勻間隔0.02 為權(quán)重，權(quán)重組合個數(shù)為51。

3.3.1 求解得到的Pareto前沿和解

3 種方法得到3 種場景下的Pareto 前沿和解如圖3所示。由圖3可以得到如下結(jié)論。

圖3 不同場景下的非支配解的分布

（1）采用改進(jìn)ε-約束法求解，得到了3 種場景下的全部Pareto前沿。

（2）采用加權(quán)法求解，在場景1 中的前沿為Pareto 前沿的一部分（共7 個解），但無法得到對應(yīng)的非凸前沿（共12 個解），即調(diào)整次數(shù)為77，64，63，60，57，52，51，50，49，43，42 和40的解。而在場景2 和場景3 中，僅得到了左上角的部分Pareto前沿，而右下角得到的是支配解。這些實(shí)驗(yàn)結(jié)果說明處理多目標(biāo)優(yōu)化問題中，加權(quán)法存在一些缺點(diǎn)。分別為：無法得到非凸前沿；受不同優(yōu)化目標(biāo)函數(shù)值的范圍影響，需要對目標(biāo)函數(shù)進(jìn)行歸一化來避免加權(quán)后的單目標(biāo)優(yōu)化問題過于偏向優(yōu)化某1 個目標(biāo)函數(shù)，造成重復(fù)計(jì)算；加權(quán)法在邊界值時由于僅優(yōu)化單個目標(biāo)，沒有辦法保證另1個優(yōu)化目標(biāo)同時最小，會出現(xiàn)支配解。而本文提出的改進(jìn)ε-約束法能夠克服這些缺點(diǎn)。

（3）采用FCFS 法求解，該策略以先到先服務(wù)的啟發(fā)式規(guī)則完成運(yùn)行計(jì)劃調(diào)整，沒有專門對不同的優(yōu)化目標(biāo)進(jìn)行處理，因此僅能得到1個解。對于場景1 中干擾類型均為車站停車作業(yè)干擾的情況，F(xiàn)CFS 法得到的解并不理想，與Pareto 前沿的差距較大。而對于場景2 和場景3 中含有區(qū)間運(yùn)行干擾的情況，F(xiàn)CFS法相對效果有所提升。

3.3.2 調(diào)整后的列車運(yùn)行圖

1）場景1

該場景下的列車計(jì)劃運(yùn)行圖如圖4所示，不同車次的運(yùn)行線通過粗細(xì)不同區(qū)分。運(yùn)用改進(jìn)ε-約束法（優(yōu)化目標(biāo)為（629，67））和FCFS 法（優(yōu)化目標(biāo)為（927，76））進(jìn)行列車運(yùn)行調(diào)整后，得到的運(yùn)行圖分別如圖5和圖6所示，圖中紅色虛線表示運(yùn)行調(diào)整后與原計(jì)劃運(yùn)行圖不一致的列車運(yùn)行線。由于加權(quán)法得到的結(jié)果大部分和改進(jìn)ε-約束法相同，這里不做具體分析。由圖4—圖6可以看出：對于車站停車作業(yè)干擾的情況，改進(jìn)ε-約束法會更多地通過調(diào)整受影響的列車次序完成調(diào)整，而FCFS 法依然按照干擾之后的列車次序調(diào)整到發(fā)時刻；針對第1 個優(yōu)化目標(biāo)，F(xiàn)CFS 法得到的結(jié)果是改進(jìn)ε-約束法的1.47 倍，總晚點(diǎn)時間多298 min；在終點(diǎn)站時，改進(jìn)ε-約束法下僅有1 趟列車存在晚點(diǎn)，其他受影響的列車在到達(dá)終點(diǎn)站之前均通過調(diào)整實(shí)現(xiàn)了恢復(fù)，而FCFS 法下還存在6 趟車到達(dá)終點(diǎn)站晚點(diǎn)情況。

圖5 場景1下運(yùn)用改進(jìn)ε-約束法按優(yōu)化目標(biāo)（629，67）調(diào)整后的列車運(yùn)行圖

圖6 場景1下運(yùn)用FCFS法按優(yōu)化目標(biāo)（927，76）調(diào)整后的列車運(yùn)行圖

2）場景2

該場景下，運(yùn)用改進(jìn)ε-約束法（優(yōu)化目標(biāo)為（843，86））和FCFS 法（優(yōu)化目標(biāo)為（857，87））進(jìn)行列車運(yùn)行調(diào)整后，得到的運(yùn)行圖分別如圖7和圖8所示。由圖7和圖8可以看出：改進(jìn)ε-約束法和FCFS 法對于場景2 前2 個干擾影響到的車次，均未調(diào)整發(fā)車次序，而是仍按原有次序依次調(diào)整到發(fā)時刻，僅在第3個干擾下分別對列車次序進(jìn)行了調(diào)整，這是因?yàn)閳鼍? 中的干擾均屬于區(qū)間運(yùn)行干擾的緣故；對于第1 個優(yōu)化目標(biāo)列車總晚點(diǎn)時間，F(xiàn)CFS法得到的結(jié)果是改進(jìn)ε-約束法的1.02倍，總晚點(diǎn)時間比后者多14 min；對于運(yùn)行至終點(diǎn)站仍存在晚點(diǎn)的列車數(shù)量，改進(jìn)ε-約束法下為2 列，而FCFS法為3列。

圖7 場景2下運(yùn)用改進(jìn)ε-約束法按優(yōu)化目標(biāo)（843，86）調(diào)整后的列車運(yùn)行圖

圖8 場景2下運(yùn)用FCFS法按優(yōu)化目標(biāo)（857，87）調(diào)整后的列車運(yùn)行圖

3）場景3

該場景下，運(yùn)用改進(jìn)ε-約束法（優(yōu)化目標(biāo)為（1 180，115））和FCFS 法（優(yōu)化目標(biāo)為（1 415，115））進(jìn)行列車運(yùn)行調(diào)整后，得到的運(yùn)行圖分別入圖9和圖10所示。從圖9和圖10可以看出：在存在多種類型干擾的場景3 下，盡管對于區(qū)間運(yùn)行干擾下FCFS 法和改進(jìn)ε-約束法的調(diào)整方案相似，但由于FCFS 法沒有調(diào)整次序的能力，其無法得到全局最優(yōu)解；在相同的第2 個優(yōu)化目標(biāo)下，對于第1 個優(yōu)化目標(biāo)列車總晚點(diǎn)時間，F(xiàn)CFS 法是改進(jìn)ε-約束法的1.20 倍，總晚點(diǎn)時間比后者多235 min；對于運(yùn)行至終點(diǎn)站仍存在晚點(diǎn)的列車數(shù)量，改進(jìn)ε-約束法為4列，而FCFS法為7列。

圖9 場景3下運(yùn)用改進(jìn)ε-約束法按優(yōu)化目標(biāo)（1 180，115）調(diào)整后的列車運(yùn)行圖

圖10 場景3下運(yùn)用FCFS法按優(yōu)化目標(biāo)（1 415，115）調(diào)整后的列車運(yùn)行圖

3.3.3 3種求解算法的性能指標(biāo)比較

3 種場景下3 種求解算法的性能指標(biāo)見表2。此外，表中還給出了算法的總計(jì)算時間和對應(yīng)得到非支配解的平均計(jì)算時間，其中加粗?jǐn)?shù)據(jù)表示該算法對應(yīng)性能指標(biāo)最優(yōu)。從表2中可以看出：改進(jìn)ε-約束法在NNS，IGD 和HV 這3 種性能指標(biāo)中均優(yōu)于加權(quán)法和FCFS 法，且得到了整個Pareto 前沿，但由于算出了所有的非支配解，所以其總計(jì)算時間較長，即在場景2 和場景3 中大于加權(quán)法和FCFS法；加權(quán)法并沒有算得全部Pareto前沿，還存在一些不必要的計(jì)算，在場景1中總時間最長；對于非支配解的平均計(jì)算時間，加權(quán)法同樣大于改進(jìn)ε-約束法；FCFS 法作為一種啟發(fā)式策略，其計(jì)算時間會明顯優(yōu)于其他基于求解器的精確算法，但其計(jì)算結(jié)果并不能保證最優(yōu)。

表2 不同場景下的算法性能

綜上，本文提出的改進(jìn)ε-約束法，能夠有效求解提出的基于雙目標(biāo)優(yōu)化的高速鐵路列車運(yùn)行調(diào)整模型的整個Pareto前沿。對于其計(jì)算時間在部分場景中較長的問題，實(shí)際中調(diào)度員可以有選擇的控制改進(jìn)ε-約束法中的次優(yōu)化目標(biāo)對應(yīng)的約束范圍，控制得到的非支配解的數(shù)量和偏好，降低調(diào)度員對不感興趣區(qū)域搜索所需要的時間。

4 結(jié) 論

（1）以列車運(yùn)行調(diào)整的列車總晚點(diǎn)時間和列車到發(fā)時刻調(diào)整次數(shù)2 個優(yōu)化目標(biāo)，以車站作業(yè)、區(qū)間運(yùn)行、追蹤間隔等時間為約束條件，構(gòu)建高速鐵路列車運(yùn)行調(diào)整的雙目標(biāo)優(yōu)化模型；對模型中的非線性項(xiàng)進(jìn)行線性化處理；提出的改進(jìn)ε-約束法對模型求解。

（2）提出的改進(jìn)ε-約束法，得到了包括非凸前沿的整個Pareto前沿，可以為調(diào)度部門提供不同的列車調(diào)整決策方案，并且在非支配解個數(shù)NNS，逆代距IGD 和超體積HV 這3 個優(yōu)化性能評價(jià)指標(biāo)上均優(yōu)于加權(quán)法和FCFS 法。與加權(quán)法相比，大部分非支配解對應(yīng)列車總晚點(diǎn)時間和列車到發(fā)時刻調(diào)整次數(shù)相同，但改進(jìn)ε-約束法的計(jì)算時間更短；對于邊界值，加權(quán)法可能會得到支配解，但改進(jìn)ε-約束法對應(yīng)調(diào)整后的總晚點(diǎn)時間更短。與FCFS法相比，改進(jìn)ε-約束法能夠得到多樣化的結(jié)果，在列車到發(fā)時刻調(diào)整次數(shù)相近情況下，總晚點(diǎn)時間更短，終點(diǎn)站晚點(diǎn)列車個數(shù)更少。

（3）當(dāng)更加復(fù)雜的干擾場景，求解問題規(guī)模增大后，計(jì)算整個Pareto前沿會消耗過多時間，可以在Pareto前沿中選擇調(diào)度員感興趣的搜索方向，搜索部分非支配解。此外，還可以通過設(shè)計(jì)一些啟發(fā)式方法和多目標(biāo)進(jìn)化計(jì)算算法，在有限時間獲得收斂性、多樣性好的近似前沿。