高峰期城市軌道交通列車跳站運(yùn)行優(yōu)化

吳文祥，趙浩淋，周慧娟，陳 智

（北方工業(yè)大學(xué)，城市道路智能交通控制技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室，北京 100144）

0 引言

隨著大城市軌道交通高峰期大客流的常態(tài)化，軌道交通運(yùn)營管理面臨著巨大的壓力與挑戰(zhàn)，運(yùn)營部門采用擴(kuò)大列車運(yùn)力、增加發(fā)車頻率、實(shí)行進(jìn)站限流等一系列措施來緩解高峰期的客運(yùn)壓力。傳統(tǒng)“站站停”軌道交通列車運(yùn)行模式雖然可以滿足乘客基本的出行需求，但是由于忽略了不同車站客流時空分布特征，影響了列車運(yùn)力配置的效果，造成乘客旅行時間增加、列車運(yùn)行時間增加等問題。因此，本文基于動態(tài)客流時空分布特征，以最小化乘客總旅行時間和站臺乘客最大數(shù)量為目標(biāo)，提出了一種基于跳站運(yùn)行模式的軌道交通列車運(yùn)行圖優(yōu)化方法，實(shí)現(xiàn)列車跳站運(yùn)行方案與實(shí)時大客流的精準(zhǔn)匹配。軌道交通列車跳站運(yùn)行模式（也稱跳停模式），不同于“站站?！钡倪\(yùn)行模式，是指列車只?？烤€路的若干特定車站，而其他站只通過不停車。雖然跳站運(yùn)行增加了列車運(yùn)行組織的難度，也增加了站臺候車乘客的平均等待時間，但是跳站可以減少列車加速、減速以及停站的次數(shù)，從而縮短了乘客的車內(nèi)旅行時間，減少了列車站間運(yùn)行時間，提高車輛周轉(zhuǎn)率，也減少列車能源消耗。美國、法國、英國、德國、日本等國家早在20世紀(jì)中葉就已在城市軌道交通中采用列車跳站模式[1]。國內(nèi)上海、深圳、廣州等城市的一些軌道交通線路預(yù)留了越行配線，已采用或準(zhǔn)備采用列車跳站運(yùn)行模式。

列車跳站優(yōu)化是鐵路組織優(yōu)化的重要組成部分，已引起了國內(nèi)外學(xué)者的廣泛關(guān)注和深入研究?？紤]靜態(tài)客流需求，鄭鋰等[2]建立了一個列車跳站運(yùn)行非線性整數(shù)規(guī)劃模型，并使用了禁忌搜索算法對模型進(jìn)行求解。Wang 等[3]針對單向地鐵列車跳站運(yùn)行調(diào)度問題，以最小化乘客等待時間和列車能源為目標(biāo)，構(gòu)建了一個基于跳站策略的非線性規(guī)劃模型，設(shè)計了雙層優(yōu)化算法，并在北京亦莊線進(jìn)行了算法驗(yàn)證。Salama 等[4]提出了列車跳站運(yùn)行策略下的最大化乘客直達(dá)數(shù)量的非線性整數(shù)規(guī)劃模型，并運(yùn)用窮舉法求得最佳跳站策略。Abdelhafiez 等[5]首先提出了一種OD 矩陣生成方法，再以最小化乘客平均旅行時間為目標(biāo)，建立了一個列車跳站運(yùn)行非線性整數(shù)規(guī)劃模型，最后用生成的OD 矩陣驗(yàn)證了跳站運(yùn)行的有效性。Lee 等[6]提出了四種地鐵跳站運(yùn)行策略，以列車總運(yùn)行時間為目標(biāo)，建立非線性整數(shù)規(guī)劃模型，對四種地鐵跳站運(yùn)行策略進(jìn)行對比分析。Niu等[7]考慮了地鐵列車的跳站模式，為動態(tài)客流需求下的列車跳站運(yùn)行問題建立了非線性整數(shù)規(guī)劃模型，并采用GAMS/AlphaECP 對模型進(jìn)行求解。Shang 等[8]基于乘客的公平性原則，建立了地鐵跳站運(yùn)行線性整數(shù)規(guī)劃模型，并設(shè)計了有效的拉格朗日松弛算法。Zhao 等[9]研究了動態(tài)客流需求下單向軌道線路的列車跳站策略，以乘客出行時間成本和列車運(yùn)營成本為優(yōu)化目標(biāo)，建立了非線性整數(shù)規(guī)劃模型并設(shè)計了遺傳算法，最后以廣州地鐵八號線為例，驗(yàn)證了模型和算法的有效性。陳吉懷和趙星[10]以最小化乘客總候車時間為目標(biāo)，提出了一種可預(yù)見大客流下的列車跳站與列車時刻表優(yōu)化聯(lián)合模型，采用一種改進(jìn)的遺傳算法求解模型，并借助南京地鐵S1號線的早高峰數(shù)據(jù)驗(yàn)證模型與算法的有效性。孟凡婷等[11]引入列車運(yùn)行圖與車站限流的相關(guān)決策變量，以提高列車運(yùn)行效率、減少客流乘車延誤人數(shù)為優(yōu)化目標(biāo)，建立軌道交通列車運(yùn)行與車站限流協(xié)同優(yōu)化的雙目標(biāo)整數(shù)非線性規(guī)劃模型，運(yùn)用時間重構(gòu)和大M 方法將原模型中的非線性約束進(jìn)行線性化處理，得到一個新的整數(shù)線性規(guī)劃模型，并利用CPLEX 軟件求解。此外，還有一些學(xué)者研究地鐵運(yùn)行中斷或不確定情形下的列車跳站運(yùn)行問題。Altazin 等[12]研究了中斷地鐵線路上的跳站運(yùn)行策略問題，提出了一個整數(shù)線性規(guī)劃模型，以實(shí)現(xiàn)地鐵線路恢復(fù)時間和乘客等待時間最小化。Gao等[13]在鐵路運(yùn)行中斷后，考慮了動態(tài)客流的過飽和情況，結(jié)合跳站策略設(shè)計了一種地鐵線路恢復(fù)期列車運(yùn)行圖再優(yōu)化模型，達(dá)到減少乘客站臺等待時間的目的。Jamil等[14]考慮了在不確定客流情況下，結(jié)合跳站運(yùn)行策略，提出了一種最小化線路總列車運(yùn)行時間的魯棒性數(shù)學(xué)模型，并設(shè)計了分解算法與模擬退火算法相結(jié)合的求解算法。

綜上所述，國內(nèi)外學(xué)者對列車跳站模式進(jìn)行了廣泛深入地研究。但是，目前大多數(shù)研究僅考慮單向線路的跳站策略，沒有刻畫列車跳站運(yùn)行導(dǎo)致乘客的復(fù)雜換乘行為[3，7，8，14，15]。雖然有些研究考慮了雙向線路的列車跳站策略，但是大多數(shù)模型不允許乘客換乘，導(dǎo)致列車跳站的機(jī)會較少、列車運(yùn)行時間降低不明顯[13]；當(dāng)然，也有少數(shù)模型允許乘客換乘，但是假設(shè)乘客換乘的等待時間只與車頭時距有關(guān)，與站臺人數(shù)無關(guān)[4-6，16]?？傊?，現(xiàn)有的列車跳站優(yōu)化模型還不能很好地跟蹤乘客的動態(tài)決策過程、乘客在各站臺的上下車過程以及乘客的動態(tài)換乘行為，即不能很好描述客流動態(tài)分配過程。可見，現(xiàn)有的列車跳站優(yōu)化模型難以對客流指標(biāo)及其目標(biāo)函數(shù)進(jìn)行精細(xì)化刻畫，這影響了列車跳站優(yōu)化的效果。

事實(shí)上，每個起點(diǎn)和終點(diǎn)（OD 對）的動態(tài)客流分配過程恰恰是制定列車停站計劃的關(guān)鍵決策依據(jù)[17]。此外，高峰期軌道交通的客流需求比較大，而且車站客流呈現(xiàn)明顯的峰值特征，這意味著：（1）客流等待時間與站臺人數(shù)有關(guān)，站臺人數(shù)越多，客流等待時間越長；（2）客流等待時間與列車剩余空間有關(guān)，停靠列車剩余空間越小，站臺客流的等待時間就越長；（3）客流等待時間還與乘客到達(dá)時間有關(guān)，越靠近峰值，等待時間越長?？梢?，客流乘車方案的選擇不僅與列車跳站方案、時刻表有關(guān)，而且還與乘客到達(dá)時間、站臺客流狀態(tài)以及列車運(yùn)行狀態(tài)有關(guān)?；谝陨戏治觯疚脑诰?xì)化描述客流指標(biāo)的基礎(chǔ)上，以最小化乘客總旅行時間及最大站臺人數(shù)為目標(biāo)，構(gòu)建一個雙向軌道交通線路的列車跳站運(yùn)行整數(shù)規(guī)劃模型，實(shí)現(xiàn)列車運(yùn)力與客流時空分布的精準(zhǔn)匹配。本文主要有以下三個方面的貢獻(xiàn)：首先，不同于以往大多數(shù)研究，綜合考慮了乘客的等待時間、換乘時間與車內(nèi)時間，描述了列車跳站運(yùn)行導(dǎo)致乘客的同向換乘行為和反向換乘行為[18]；其次，高峰期大客流可能導(dǎo)致乘客無法登上當(dāng)前的列車，即乘客的愿意上車人數(shù)和實(shí)際上車人數(shù)不相等，因此，本文結(jié)合乘客的換乘行為和動態(tài)決策過程，計算當(dāng)前列車各OD 對乘客的愿意上車人數(shù)，然后根據(jù)列車的剩余空間計算各OD 對乘客的實(shí)際上車人數(shù)，以此為基礎(chǔ)，完成站臺人數(shù)和車內(nèi)人數(shù)的更新；最后，為了避免列車靈活跳站導(dǎo)致站臺乘客數(shù)量過大、等待時間過長，將最大站臺人數(shù)作為懲罰值引入模型的目標(biāo)函數(shù)，并基于上述動態(tài)客流分配方法，對乘客總旅行時間和站臺最大人數(shù)進(jìn)行精細(xì)刻畫。

1 列車靈活跳站優(yōu)化模型

1.1 問題描述

本文研究雙向城市軌道交通線路的列車跳站運(yùn)行優(yōu)化問題，軌道交通線路的物理結(jié)構(gòu)如圖1所示。該軌道交通線路有上行、下行兩個方向，各方向共有N個車站、N-1 個區(qū)段，上行方向車站編號j（j=1,2,…,N）與下行方向車站編號N+1-j對應(yīng)同一個站臺，線路兩端由折返線與發(fā)車站相連，列車沿兩側(cè)的折返線到達(dá)始發(fā)站后，沿預(yù)設(shè)方向運(yùn)行。

圖1 軌道交通線路物理結(jié)構(gòu)

為實(shí)現(xiàn)列車運(yùn)力與客流的精準(zhǔn)匹配，本文采用列車靈活跳站(Flexible Skip-Stop)模式。為方便研究，本文作出以下假設(shè)：

假設(shè)1 根據(jù)歷史的刷卡數(shù)據(jù)和其他數(shù)據(jù)，可以精確預(yù)測乘客的出行需求，即模型中的客流動態(tài)OD是已知的。

假設(shè)2 高峰期列車發(fā)車間隔是固定的，站臺有足夠大的空間容納已進(jìn)站的乘客。

假設(shè)3 乘客上車遵循先到先行原則，即先進(jìn)站的乘客先乘車，滯留乘客在下次列車到達(dá)時優(yōu)先乘車。

假設(shè)4 乘客換乘在同站臺進(jìn)行，不單獨(dú)計算乘客的換乘步行時間，將換乘步行時間計入乘客等待時間。

假設(shè)5 在滿足列車安全約束和列車停站約束的條件下，除始發(fā)站和終點(diǎn)站外，允許列車不停車通過任意中間車站，即列車是靈活跳站運(yùn)行。

假設(shè)6 同道路交通確定性用戶均衡模型一樣，假設(shè)軌道交通線路的所有乘客都選擇最小旅行時間的出行方案。

1.2 符號和定義

（1）索引和參數(shù)

N：軌道交通線路的車站數(shù)量，N>3；

i，j，v：地鐵車站編號，i,j,v=1,2,…,N；

vjm：列車m停靠站j的下個停靠車站；

M：計劃期內(nèi)上行（下行）發(fā)出的列車數(shù)量；

m，k，u：列車的編號，m,k,u=1,2,…,M；

ujm：站j停靠列車m的上一個?？寇嚧?；

f：方向編號，f=1 為上行方向，f=2 為下行方向；

Cm：列車m的最大容量（最大載客量）；

H1：同方向相鄰兩列車離開同一車站的最小時間間隔；

H2：同方向相鄰兩列車到達(dá)同一車站的最小時間間隔；

H3：同方向在同一車站相鄰兩列車到站與離站的最小時間間隔；

Hf：f方向的列車發(fā)車間隔；

T：計劃期；

（2）時間參數(shù)

WT：軌道交通線路的乘客總等待時間；

VT：軌道交通線路的乘客總車內(nèi)時間；

PN：最大站臺人數(shù)；

β1，β2，β3：分別是WT、VT、PN的權(quán)重系數(shù)。

（3）動態(tài)客流參數(shù)

pjif(t)：f方向在t時刻乘客到達(dá)車站j且出站為車站i的客流到達(dá)率；

wjif(t)：f方向在截止到t時刻從車站j到車站i的潛在上車乘客數(shù)量；

wjf(t)：f方向在截止到t時刻車站j的潛在上車乘客數(shù)量；

（4）決策變量

1.3 列車跳站運(yùn)行相關(guān)約束

（1）列車到發(fā)時間約束

約束（1）為計劃期內(nèi)各方向第一輛列車的發(fā)車時間。約束（2）、（3）分別是各方向各列車的發(fā)車時間間隔約束和各站的停站時間約束，如不?？寇囌緅，則=0。約束(4)是各方向列車到達(dá)車站j的時間等于列車的首站到站時間、從首站到車站j的列車站間運(yùn)行時間與從首站到j(luò)-1 站的所有停站時間之和。公式（4）表明列車跳站不僅減少了列車停站時間而且還減少了列車站間運(yùn)行時間。

（2）列車停站約束

約束（5）確保所有列車都停靠首末站，約束（6）確保在任意中間車站j都有列車?？?。

（3）停站時間約束

約束（7）確保列車m在車站j的停站時間不超過最大停站時間且不小于最小停站時間。

（4）安全車頭時距約束

為了確保列車安全運(yùn)行，約束（8）是指在同一站的相鄰車次到達(dá)時間間隔不小于H1；約束（9）保證同一站的相鄰車次出發(fā)時間間隔不小于H2；約束（10）保證同一站的后一輛列車到站與前一輛列車出站的時間間隔不小于H3。H1、H2、H3均為安全時距。

（5）車輛容量約束

約束（11）是指任意時刻列車m的車內(nèi)人數(shù)不大于其最大容量。

1.4 精細(xì)化客流約束

為了便于計算，本模型只統(tǒng)計列車進(jìn)站、離站時刻的相關(guān)客流指標(biāo)。

（1）乘客的下車數(shù)量

f方向列車m離開j站前，乘客在車站j從列車m下車的人數(shù)等于f方向乘坐列車m在車站j之前上車并在車站j下車出站的乘客總?cè)藬?shù)，f方向乘坐列車m在車站j下車同向換乘去目的地車站的乘客總?cè)藬?shù)，f方向乘坐列車m在車站j下車反向換乘去目的地車站的乘客總量以及f方向乘坐列車m在車站j下車反向換乘去目的地車站的乘客總量之和。計算公式如下：

公式（12）中若f=1，則=2；若f=2，則=1。

為了便于理解，下面用示意圖解釋公式（12）。從圖2可以看出：f方向從車站j（2

另外，從圖2 也能看出：f方向列車m在首發(fā)站無乘客下車。f方向第二站無反向換乘乘客，否則乘客的終點(diǎn)站是首發(fā)站，顯然不可能。同理，倒數(shù)第二站方向無反向換乘乘客。顯然，f方向末站只有f方向下車出站的乘客和f方向下車反向換乘的乘客。

圖2 在車站j（2

（2）潛在上車乘客數(shù)量

列車m離開車站j前潛在上車乘客數(shù)量等于列車m到達(dá)車站j時站臺潛在上車乘客數(shù)量、列車m在車站j?？繒r段內(nèi)進(jìn)站到達(dá)站臺人數(shù)與列車m在車站j?？繒r段內(nèi)f—方向在車站j下車反向換乘的乘客數(shù)量之和，如圖3所示。

圖3 列車m離開車站j前潛在上車乘客示意圖

計算公式如下：

列車m到達(dá)車站j時，潛在上車人數(shù)等于列車ujm離開車站j時站臺剩余上車人數(shù)，從列車ujm離開車站j至列車m到達(dá)車站j時間段內(nèi)的f方向進(jìn)站人數(shù)，從列車ujm離開車站j至列車m到達(dá)車站j時間段內(nèi)的方向在車站j下車的反向換乘乘客人數(shù)以及在車站j從列車ujm下車的同向換乘乘客人數(shù)之和，如圖3 所示。特別指出：從列車ujm下車同向換乘乘客不可能再上列車ujm，只能是列車m的潛在上車乘客。因此，潛在上車人數(shù)的計算公式如下：

（3）乘客的實(shí)際上車數(shù)量

顯然，列車m的潛在上車乘客數(shù)量不一定等于實(shí)際上車人數(shù)，這有兩個原因：①乘客不一定愿意乘坐當(dāng)前列車m；②即使乘客愿意乘坐當(dāng)前列車m，列車m的能力約束也不能保證所有愿意上車的乘客都能上車。為了計算乘客實(shí)際上車數(shù)量，首先要描述乘客是否愿意乘坐當(dāng)前列車m。如圖2所示，f方向乘客可能存在三種乘車方案：①乘客直達(dá)目的地；②乘客需同向換乘到達(dá)目的地；③乘客需反向換乘到達(dá)目的地。乘客從三種乘車方案中選擇旅行時間最小的乘車方案。計算各乘車方案的旅行時間都是將當(dāng)前列車m離開車站j的時間當(dāng)作基準(zhǔn)時間，之前的時間都可看作沉沒成本，對當(dāng)前的決策不產(chǎn)生影響。根據(jù)列車時刻表，下面分別計算乘客各種乘車方案的旅行時間。

（a）乘客直達(dá)

從車站j到車站i的乘客如果選擇次列車直達(dá)目的地，則其旅行時間為：

公式（16）表明，乘客選擇列車k直達(dá)目的地，列車k必須?？寇囌緅和車站i（即>0），而且列車k必須滿足k≥m。

（b）同向換乘

公式（17）中乘客首先選擇列車k到達(dá)換乘車站，這要求列車k必須?？寇囌緅和車站v但不停靠車站i（即>0 且=0），而且列車k必須滿足k≥m。既然是同向換乘，乘客選擇的換乘車站v必須滿足j0）并且滿足u>k。

（c）反向換乘

與同向換乘一樣，反向換乘的乘客首先選擇列車k到達(dá)換乘車站v，這要求列車k必須?？寇囌緅和車站v但不停靠車站i（>0 且=0），而且列車k必須滿足k≥m。不同于同向換乘，公式（18）中乘客選擇的換乘車站v必須滿足v>i，而且乘客選擇的從換乘車站到目的地車站的反向車次u必須晚于列車k到達(dá)車站v（即，而且反向車次u必須?？寇囌緑和i（即

顯然，從車站j到車站i的乘客選擇直達(dá)、同向換乘、反向換乘方案中旅行時間最小的車次，即：

如果k=m（即，則從車站j到車站i的乘客選擇乘坐當(dāng)前列車m，具體乘車方案如下：

特別指出：相對于道路交通系統(tǒng)，地鐵系統(tǒng)運(yùn)行是可靠的，列車跳站方案可在互聯(lián)網(wǎng)、站臺大屏及時向乘客發(fā)布，乘客可以獲取所需信息進(jìn)行動態(tài)乘車決策，選擇當(dāng)前最快乘車方案。地鐵公司也可以基于乘客達(dá)到時間和列車跳站方案生成最快乘車方案，并通過手機(jī)APP向乘客推薦該方案。

根據(jù)得到的乘車方案，計算從車站j到車站i乘客愿意乘坐列車m的人數(shù)：

顯然，j站乘客愿意乘坐當(dāng)前列車m的總?cè)藬?shù)為：

?？寇囌緅列車m的剩余空間由列車最大容量與列車m在車站j的下車人數(shù)之和減去列車m到達(dá)車站j時的車內(nèi)人數(shù)，則：

列車m在車站j實(shí)際上車人數(shù)等于愿意乘坐當(dāng)前列車m的乘客人數(shù)與車內(nèi)剩余空間的最小值，即：

在計算車站j實(shí)際上車人數(shù)之后，再計算各OD 實(shí)際上車人數(shù)。由車站j到車站i的乘坐列車m的實(shí)際上車人數(shù)等于從車站j到車站i乘客愿意上車的人數(shù)與在車站j愿意上車的總?cè)藬?shù)的比值乘以列車m在車站j實(shí)際上車人數(shù)[13]，則：

簡而言之，OD 對(3，5)乘客和OD 對(3，9)乘客，按需求比例各有20 人乘坐當(dāng)前列車m直達(dá)目的地車站，未上車的乘客在下一輛?？寇囌?的列車到站后再做決策。

從車站j登上列車m且出站為i的乘客人數(shù)為：

更新站臺潛在上車乘客數(shù)量：

更新列車m在車站j離站時的車內(nèi)人數(shù)，車內(nèi)人數(shù)等于列車m在車站j到達(dá)時的車內(nèi)人數(shù)與從車站j登上列車m的實(shí)際上車人數(shù)之和減去在車站j的下車人數(shù)：

列車m離開車站j的車內(nèi)人數(shù)等于列車m到達(dá)下一?？寇囌緯r的車內(nèi)人數(shù)，則：

1.5 目標(biāo)函數(shù)與模型構(gòu)建

本文從乘客的角度優(yōu)化列車跳站運(yùn)行方案，以最小化乘客站臺總等待時間，乘客車內(nèi)總時間以及最大站臺人數(shù)為目標(biāo)，下面分別給出它們的計算公式。

（1）乘客站臺總等待時間

站臺乘客總等待時間WT等于列車停站期間站臺乘客等待時間，相鄰兩輛列車到站間隔期間站臺剩余乘客等待時間與兩輛列車到站間隔期間新進(jìn)站乘客等待時間之和，具體計算公式如下：

（2）乘客車內(nèi)總時間

乘客車內(nèi)總時間VT包括列車停站時車內(nèi)乘客時間加上列車在區(qū)段內(nèi)運(yùn)行時車內(nèi)乘客時間，計算公式如下：

（3）站臺乘客最大數(shù)量

在靈活跳站模式中列車停站沒有規(guī)律，可能會造成某一個站臺乘客的持續(xù)增加，為了避免站臺客流過度擁擠，將最大站臺人數(shù)作為懲罰引入目標(biāo)函數(shù)，上行方向和下行方向的最大站臺人數(shù)的計算公式如下：

（4）列車跳站優(yōu)化模型構(gòu)建

基于上面刻畫的目標(biāo)函數(shù)和約束條件，引入權(quán)重系數(shù)β1，β2，β3，以最小化系統(tǒng)乘客總等待時間，乘客總車內(nèi)時間和最大站臺人數(shù)的加權(quán)和為目標(biāo)，構(gòu)建列車靈活跳站模型如下：

約束條件(1)～(31)。

2 求解算法

本文所構(gòu)建的模型是一個大規(guī)模非線性0-1整數(shù)規(guī)劃模型。各列車都?？渴啄┱?，其他中間車站列車都可以通過不停車，則上行方向或下行方向任意列車最大停站方案有2N-2個，M輛列車最大停站方案有2M(N-2)種組合。例如，上行方向N=20，M=40，上行方向共有240×18=2720個停站方案，解的空間規(guī)模極大，傳統(tǒng)算法難以求解?；旌贤芴惴ㄊ且环N新興的群體智能優(yōu)化算法，在處理具有復(fù)雜多峰的優(yōu)化問題上具有良好的魯棒性和全局收斂性。鑒于列車靈活跳停問題的規(guī)模和復(fù)雜性，本文在混合蛙跳算法（SFLA）的基礎(chǔ)上提出改進(jìn)的SFLA算法。本文對SFLA的改進(jìn)體現(xiàn)在以下兩個方面：（1）基于子蛙種群規(guī)模與子蛙群內(nèi)部最大迭代次數(shù)之間的函數(shù)關(guān)系，更新不同子蛙種群的最大迭代次數(shù)；（2）在子蛙種群迭代中引入了安全約束判定，在不符合安全約束的最差解基礎(chǔ)上，重新生成新的可行解，因?yàn)樽畈罱庵幸灿锌赡馨瑑?yōu)秀的基因，以增加子蛙種群搜索的廣度?；旌贤芴惴鞒倘鐖D4所示。

圖4 混合蛙跳算法流程圖

步驟0 初始化。隨機(jī)生成Spop個停車方案，組成方案集合pop（即青蛙種群），Spop是青蛙種群規(guī)模，種群最大進(jìn)化次數(shù)是。設(shè)置子蛙群數(shù)量Q，每個子蛙群的集合subi（i=1,2,3,…,Q），即子蛙群中停車方案的集合，Ssubi（i=1,2,3,…,Q）是青蛙種群規(guī)模。設(shè)置子蛙群規(guī)模Ssubi和子蛙群內(nèi)部最大迭代次數(shù)的函數(shù)關(guān)系=f(Ssubi)（i=1,2,3,…,Q），設(shè)置各子蛙群從青蛙種群取值比例α（0<α<1）。輸入乘客到達(dá)率pjif(t)（任意i，j，f，t）。

步驟1 編碼。每個停車方案χMN就是一個青蛙個體χMN，采用0-1 編碼形式，單個青蛙個體由M×N個編碼組成，每行代表一列車，每列代表一車站，1代表停站，0代表跳過車站。令種群進(jìn)化代數(shù)ngen=1。

步驟2 計算客流參數(shù)。根據(jù)青蛙種群中χMN停車方案，計算上行和下行方向任意列車m在任意站j的到站時間和發(fā)車時間，按照約束條件（1）～（10）判斷停車方案是否符合安全約束，將不符合安全約束的停車方案其適應(yīng)度函數(shù)（目標(biāo)函數(shù)）置為足夠大的常數(shù)，轉(zhuǎn)到步驟4。針對符合安全約束的停車方案，計算客流相關(guān)指標(biāo)，下面是客流相關(guān)指標(biāo)計算的具體步驟。

步驟3 計算適應(yīng)度函數(shù)值。按照公式（32）～（34）計算乘客站臺總等待時間WT、乘客車內(nèi)總時間VT和最大站臺人數(shù)PN，再按照公式（35）計算停車方案χMN的適應(yīng)度函數(shù)值，即目標(biāo)函數(shù)值Z=min (β1WT+β2VT+β3PN)。

步驟4 青蛙種群適應(yīng)度計算終止判定。青蛙種群pop中每一個青蛙個體按照步驟2至步驟3重復(fù)迭代，得到青蛙種群pop中每個停車方案的目標(biāo)函數(shù)值；否則，轉(zhuǎn)步驟2 至步驟3 繼續(xù)迭代，計算青蛙種群pop中停車方案的目標(biāo)函數(shù)值。

步驟7 構(gòu)建新種群。將所有子蛙群中青蛙個體重新混合即停車方案重新混合，生成新的停車方案種群pop，置ngen=ngen+1。

步驟8 收斂條件判定。當(dāng)種群進(jìn)化次數(shù)ngen<，轉(zhuǎn)步驟2至步驟7；否則，終止迭代，輸出最優(yōu)解，即最優(yōu)列車跳站運(yùn)行方案。

3 數(shù)值算例

下面以北京地鐵亦莊線為例，研究列車在高峰期跳站運(yùn)行停站方案。北京地鐵亦莊線線路長度為23 km，共有14 座車站，亦莊火車站到宋家莊為上行方向，宋家莊到亦莊火車站為下行方向。模型中涉及運(yùn)營時段為6：00～10：00，計劃期（分析時段）為早高峰7：00～9：00，早高峰上行方向和下行方向的發(fā)車間隔都是3 min，模型參數(shù)Cm=1460人（m=1,2,…,M），H1=H2=2min，H3=1.5min，β1=β2=1，β3=3min/人。模型權(quán)重系數(shù)的物理含義是除了考慮乘客總等待時間和乘客總車內(nèi)時間以外，再額外給最大站臺人數(shù)每人一個發(fā)車間隔（3min）的時間懲罰。計劃期內(nèi)上行方向、下行方向各有40個車次，上行列車采用靈活跳站策略，下行列車采用全停策略。為方便計算，將計劃期以Δt=30s 為單位進(jìn)行時間離散化處理?？土鲾?shù)據(jù)取自北京地鐵亦莊線刷卡數(shù)據(jù)，計劃期內(nèi)上行方向乘客為38 969 人，將地鐵刷卡數(shù)據(jù)中乘客進(jìn)站時間與乘客從閘機(jī)到站臺行走時間相加得到乘客到達(dá)站臺時間，將乘客進(jìn)站人數(shù)按Δt時間間隔進(jìn)行統(tǒng)計，得到計劃期內(nèi)乘客到達(dá)率pjif(t)（任意i，j，f，t）。計劃期內(nèi)客流OD 如圖5 所示即需求模式1。從圖5 可以看出：上行方向絕大部分客流是去宋家莊站，而其他目的地車站的客流很少；下行方向絕大部分客流是從宋家莊站到其他車站。

圖5 研究周期內(nèi)北京亦莊線需求模式1的客流數(shù)據(jù)

此外，為了對比研究不同需求模式下的跳站優(yōu)化效果，本文還構(gòu)造了一個新的客流需求模式（即需求模式2），上行方向客流也為38 969 人，計劃期內(nèi)客流OD 如圖6 所示。與需求模式1 相比較，需求模式2中上行客流最高峰出現(xiàn)在次渠站和次渠南站，而需求模式1中上行客流最高峰出現(xiàn)在小紅門站。另外，從圖7 可以看出，需求模式1 中的高峰客流靠近終點(diǎn)站宋家莊站，但是需求模式2中的高峰客流靠近始發(fā)站亦莊火車站。特別指出雖然算例用的是動態(tài)客流OD，但是由于空間維度涉及起點(diǎn)、終點(diǎn)兩個維度，難以用三維圖形刻畫動態(tài)客流OD，所以圖5 和圖6 用的都是計劃期內(nèi)累積客流OD 量，以區(qū)別兩種需求模式下客流分布空間特征。

圖6 研究周期內(nèi)北京亦莊線需求模式2的客流數(shù)據(jù)

圖7 目的地為宋家莊站的各站乘客人數(shù)

本模型算法實(shí)現(xiàn)環(huán)境為MATLAB R2020a，CPU 為AMD3900XT，12 核24 線程，內(nèi)存32GB。下面分別給出需求模式1、需求模式2 下模型優(yōu)化結(jié)果并進(jìn)行比較分析。

3.1 需求模式1

對模型進(jìn)行優(yōu)化求解，得到需求模式1的列車運(yùn)行圖，如圖8 所示。從圖8 可以看出，在靠近亦莊火車站的前幾站7：00 到7：34 發(fā)出的列車跳站較少，從7：34 到9：00 列車跳站略有增加。但是，整個計劃期內(nèi)列車在靠近宋家莊的最后幾站跳站較多。

圖8 需求模式1下亦莊線靈活跳站列車運(yùn)行圖

為方便分析，圖9 和圖10 分別給出了全停模式下亦莊線的站臺人數(shù)和車內(nèi)人數(shù)的統(tǒng)計結(jié)果。圖9表明，全停模式下亦莊線站臺人數(shù)高峰出現(xiàn)在7：30 到8：30，第一個站臺人數(shù)高峰出現(xiàn)在同濟(jì)南路站，第二個高峰出現(xiàn)在小紅門站。圖10顯示，車內(nèi)人數(shù)高峰出現(xiàn)在第6 輛車到第17 輛車。結(jié)合列車運(yùn)行圖，車內(nèi)人數(shù)與站臺人數(shù)高峰是高度耦合的。

圖9 需求模式1下亦莊線全停模式各站臺人數(shù)

圖10 需求模式1下亦莊線全停模式各列車車內(nèi)人數(shù)

圖11 和圖12 分別描述了跳站模式下站臺人數(shù)、車內(nèi)人數(shù)與全停模式下站臺人數(shù)、車內(nèi)人數(shù)的差值。從圖11可以看出，與全停運(yùn)行模式相比較，在靠近亦莊火車站前面幾站的站臺人數(shù)變化不大，這是因?yàn)榱熊囋谶@幾站跳站較少。但是，在靠近宋家莊最后幾站的站臺人數(shù)增加較多，尤其是小紅門和舊宮站臺人數(shù)增加最多，這是列車在這幾站跳站較多導(dǎo)致的。圖12 表明，靠近亦莊火車站的前面幾站車內(nèi)人數(shù)變化不大，這也是因?yàn)榱熊囋谝嗲f火車站前面幾站跳站較少。但在靠近宋家莊后面幾站的車內(nèi)人數(shù)變化較大，這取決于列車跳站方案、列車?？寇囌镜南萝嚾藬?shù)和上車人數(shù)。

圖11 需求模式1下亦莊線跳站運(yùn)行模式與全停模式站臺人數(shù)差值圖

圖12 需求模式1下跳站運(yùn)行模式與全停模式車內(nèi)人數(shù)的差值圖

圖13 描述了列車跳站模式導(dǎo)致各OD 對客流總旅行時間的變化。具體來說，亦莊火車站前面幾站上車的乘客總旅行時間大大減少，這是因?yàn)榍懊鎺渍玖熊囂据^少乘客等待時間變化不大，但后面的列車跳站大大降低了乘客的車內(nèi)時間。中間幾站的乘客總旅行時間變化不大，這是因?yàn)樘緶p少的乘客車內(nèi)時間與增加的乘客站臺等待時間相互抵銷了。但是，從小紅門和肖村上車的乘客旅行時間增加了，這是因?yàn)樘緦πご迳宪嚨某丝蜎]有任何益處，只會增加等車時間，跳站對小紅門上車的乘客益處也不大。特別指出，OD 對客流總旅行時間還與客流需求有關(guān)。例如，同濟(jì)南路上車到宋家莊站的乘客總旅行時間減少最多，這是因?yàn)樵揙D對乘客的需求最大。

圖13 需求模式1下跳站模式相較于全停模式OD總旅行時間差值圖

3.2 需求模式2

圖14 是需求模式2 下優(yōu)化的列車運(yùn)行圖。與需求模式1類似，在靠近亦莊火車站的前面幾站列車跳站也較少。但是，在靠近宋家莊的后面幾站列車跳站較多，這是由于需求模式2中乘客需求比需求模式1更靠近始發(fā)站。

圖14 需求模式2下亦莊線靈活跳站運(yùn)行模式列車運(yùn)行圖

從圖15可看出站臺人數(shù)高峰出行時段為7：30到8：50。圖16 表明，車內(nèi)人數(shù)高峰出現(xiàn)在第3 輛車到第25輛車。不同于需求模式1，乘客高峰站點(diǎn)為次渠南站，從次渠南站往后，第6 輛車到第30 輛車列車的滿載率就達(dá)到了55%。

圖15 需求模式2下亦莊線全停模式各站臺人數(shù)

圖16 需求模式2下亦莊線全停模式各列車車內(nèi)人數(shù)

圖17 中列車跳站站臺人數(shù)的正負(fù)差值高峰均為榮昌東街，相較于需求模式1，需求模式2 中站臺人數(shù)的波動較小。圖18 表明，與需求模式1類似，跳站模式導(dǎo)致車內(nèi)人數(shù)從次渠南開始波動，但相對于需求模式1，需求模式2 車內(nèi)人數(shù)波動較小。

圖17 需求模式2下亦莊線靈活跳站模式與全停模式的站臺人數(shù)差值圖

圖18 需求模式2下亦莊線跳站模式與全停模式的車內(nèi)人數(shù)差值圖

從圖19 可以看出，與需求模式1 類似，列車跳站模式減少了乘客總旅行時間?？拷及l(fā)站的頭幾站上車的乘客旅行時間減少較多。與需求模式1 不同的是，從始發(fā)站的附近站點(diǎn)上車的乘客人數(shù)最多，如從亦莊火車站、次渠、次渠南和經(jīng)海路到宋家莊，這四個OD的乘客總旅行時間減少最多。

圖19 需求模式2下靈活跳站模式相較于全停模式OD總旅行時間差值圖

3.3 兩種需求模式列車跳站運(yùn)行性能指標(biāo)分析

本文基于預(yù)測的客流OD 分布優(yōu)化列車跳站方案是一個超大規(guī)模的非線性組合優(yōu)化問題，優(yōu)化結(jié)果以列車運(yùn)行圖和列車時刻表的形式呈現(xiàn)，列車時刻表及時向社會發(fā)布并在相當(dāng)長的時間范圍內(nèi)不做調(diào)整。從圖20 可以看出：需求模式1 下其適應(yīng)度函數(shù)值進(jìn)化到57 代就開始收斂，隨后適應(yīng)度函數(shù)值幾乎保持不變；需求模式2下其適應(yīng)度函數(shù)值進(jìn)化到63代也開始收斂。另外，需求模式1下和需求模式2 下程序運(yùn)行時間分別為4 852 s 和5 082 s?？梢?，本文提出的改進(jìn)混合蛙跳算法有較好的收斂性能，能夠滿足該應(yīng)用場景要求。

圖20 需求模式1與需求模式2的適應(yīng)度函數(shù)進(jìn)化曲線

表1 給出了兩種需求模式下不同列車運(yùn)行模式的性能指標(biāo)。具體來說，需求模式1的列車跳站模式比全停模式的乘客平均等待時間增加了2.32-1.66=0.89 min，乘客平均車內(nèi)時間較少了16.40-14.20=2 min，乘客平均旅行時間減少了18.06-16.75=1.31min，乘客總旅行時間減少了1.31×38 969=51 049 min，總旅行時間減少比例為1.31/18.06=7.25%。雖然列車跳站運(yùn)行增加了乘客的平均等待時間，但是最大站臺人數(shù)并沒有增加。另外，相較于全停模式，需求模式2下列車跳站模式導(dǎo)致乘客的平均等待時間增加了2.28-1.38=0.9 min，平均車內(nèi)時間減少了24.34-20.66=3.68 min，平均旅行時間減少25.72-22.94=2.78 min，乘客總旅行時間減少了2.78×38 969=108 333 min，總旅行時間減少比例為2.78/25.72=10.8 %。雖然最大站臺人數(shù)增加了95人，但控制在合理范圍之內(nèi)。可見，兩種需求模式下列車跳站運(yùn)行明顯降低了系統(tǒng)的乘客總旅行時間。此外，表1還表明客流分布更靠近始發(fā)站的需求模式2 比需求模式1 更適合列車跳站運(yùn)行。

表1 不同需求模式下不同列車運(yùn)行模式的性能指標(biāo)

表2 給出了不同需求模式下?lián)Q乘乘客數(shù)量的統(tǒng)計結(jié)果。表2 中主動換乘是指在一定時間范圍內(nèi)乘客可以直達(dá)但為了減少旅行時間而采用換乘方式完成出行；被動換乘是指在一定時間范圍內(nèi)乘客不得不采用換乘方式完成出行。同向換乘是指乘客在中間車站換乘同向其他列車到達(dá)目的地；反向換乘是乘客多坐一站或幾站，換乘反向列車達(dá)到目的地車站。從表2可以看出，列車跳站導(dǎo)致乘客換乘的人數(shù)并不多，需求模式1 為857 人，需求模式2 為721 人，分別占總客流需求的857/38969=2.19%，721/38969=1.85%。需求模式1下最不利的被動反向換乘占比為66/38969=0.16%，而需求模式2下沒有乘客選擇被動反向換乘?？梢?，優(yōu)化后的列車跳站方案只給極少數(shù)乘客帶來不便。

表2 不同需求模式下列車跳站運(yùn)行換乘乘客數(shù)量統(tǒng)計

特別指出，在這兩種需求模式下，上行方向乘客反向換乘的人數(shù)很少，對反向（下行方向）列車“全?！边\(yùn)行幾乎沒有影響。因此，本文不統(tǒng)計下行方向的列車運(yùn)行和客流相關(guān)性能指標(biāo)。

4 結(jié)論

針對傳統(tǒng)“站站停”模式難以精準(zhǔn)匹配列車運(yùn)力與乘客需求的局限性，本文以最小化乘客旅行時間和最大站臺人數(shù)為目標(biāo)，構(gòu)建了雙向軌道交通線路列車靈活跳站非線性整數(shù)規(guī)劃模型，設(shè)計了改進(jìn)的混合蛙跳智能算法，并通過北京地鐵亦莊線的列車跳站優(yōu)化驗(yàn)證了模型與算法的有效性。結(jié)果表明：（1）列車跳站運(yùn)行明顯降低了乘客的總旅行時間，并且最大站臺人數(shù)也控制在合理范圍之內(nèi)；（2）列車跳站運(yùn)行給前幾站上車的乘客帶來較大收益，中間站上車的乘客收益變化不大，最后一站上車的少數(shù)乘客利益受損；（3）雖然列車跳站運(yùn)行導(dǎo)致復(fù)雜的乘客換乘行為，但是只有極少數(shù)乘客需要采用換乘方案完成出行；（4）客流需求更靠近始發(fā)站的需求模式更適合列車跳站運(yùn)行。

本文研究的是列車靈活跳站優(yōu)化問題，一定程度上增加了列車運(yùn)行組織和乘客選擇乘車方案的難度。地鐵公司通過及時發(fā)布列車時刻表和列車停站信息引導(dǎo)乘客乘車，乘客也可以根據(jù)自己到站時間和列車時刻表來選擇合適的乘車方案。本研究可進(jìn)一步拓展到列車運(yùn)行組織相對簡單的AB 型列車跳站優(yōu)化問題。另外，本文僅僅從乘客的角度優(yōu)化列車跳站方案，將來可以進(jìn)一步考慮列車能耗、碳排放、車輛周轉(zhuǎn)率等指標(biāo)，從乘客和地鐵公司的角度，同時優(yōu)化列車發(fā)車間隔與列車跳站方案。