基于雙目標(biāo)優(yōu)化的高速鐵路列車(chē)運(yùn)行調(diào)整

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

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

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

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

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

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

1 優(yōu)化模型

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

1.1 模型假設(shè)

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

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

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

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

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

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

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

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

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

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

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

其中，

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

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

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

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

1.4 約束條件

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

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

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

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

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

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

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

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

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

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

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

3）列車(chē)到發(fā)間隔時(shí)間約束

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

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

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

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

5）決策變量約束

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

1.5 模型處理

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

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

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

1.6 相關(guān)定義

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

定義1（Pareto 支配）：目標(biāo)向量u和v為2 個(gè)可行解集對(duì)應(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)個(gè)數(shù)），且u≠v。

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

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

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

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

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

2 模型求解

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

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

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

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

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

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

3 算例分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

針對(duì)3.1 節(jié)中給出的3 種干擾場(chǎng)景，在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，通過(guò)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)重組合個(gè)數(shù)為51。

3.3.1 求解得到的Pareto前沿和解

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

圖3 不同場(chǎng)景下的非支配解的分布

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

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

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

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

1）場(chǎng)景1

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

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

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

2）場(chǎng)景2

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

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

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

3）場(chǎng)景3

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

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

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

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

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

表2 不同場(chǎng)景下的算法性能

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

4 結(jié) 論

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

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

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