基于客流需求的城市軌道交通行車計劃與列車時刻表優(yōu)化

曹璐，曹成鉉

(北京交通大學(xué) 軌道交通控制與安全國家重點實驗室，北京 100044)

維系一座城市正常運轉(zhuǎn)必不可缺的是城市內(nèi)的公共交通，相比于其他公共運輸方式，軌道交通優(yōu)勢明顯。如何提高城市軌道交通的運輸效率，是近些年研究的重點之一，行車計劃和列車時刻表的優(yōu)化中起到了關(guān)鍵作用。行車計劃決定了各個時間段的列車開行數(shù)量和運用車輛，是城市軌道交通一系列工作的基礎(chǔ)。列車時刻表決定了列車在每個站的到發(fā)時間以及是否停車等，是城市軌道交通運營組織的重要內(nèi)容。

針對行車計劃，以往主要研究行車間隔和列車開行對數(shù)。王樹文[1]根據(jù)掌握的客流時空分布特性，利用有序樣品最優(yōu)分割法分割運營時段，提出行車間隔和開行對數(shù)優(yōu)化模型。孫焰等[2]以實載率最大化和時間分段數(shù)最小化為目標(biāo)研究多個循環(huán)區(qū)段上的列車開行對數(shù)，分步優(yōu)化確定行車計劃。洪玲等[3]分析客流分布特征、列車交路形式和服務(wù)水平與行車間隔之間的相互影響關(guān)系，給出了行車間隔與實際客流需求和系統(tǒng)能力的變化趨勢線。

國內(nèi)外學(xué)者也對列車時刻表進(jìn)行了一系列的研究。Zhang等[4]以乘客總出行時間最小化為目標(biāo)建立兩種非線性非凸規(guī)劃模型，對時刻表進(jìn)行優(yōu)化使其適應(yīng)擁擠條件下的動態(tài)客流需求。Niu等[5]以乘客的總等待時間最小化為目標(biāo)建立非線性規(guī)劃模型，并引入二元整數(shù)規(guī)劃模型表示乘客的到站和離開，實現(xiàn)了過飽和情況下列車時刻表優(yōu)化。張璐[6]提出乘客出行能量消耗反映列車的擁擠情況和乘客的等待時間，并以乘客等待時間最小和出行能量消耗最小為目標(biāo)建立了兩個模型。Hassannayebi等[7]以乘客的平均出行成本最小為目標(biāo)，創(chuàng)建優(yōu)化模型，使用拉格朗日松弛算法將模型簡化，有效縮短了模型計算的時間。王一閣[8]從乘客出行費用出發(fā)，利用遺傳算法，在預(yù)測客流的基礎(chǔ)上優(yōu)化時刻表中列車的發(fā)車間隔和停站時間, 降低了車載乘客數(shù)與車載定員之差，減少了乘客的候車時間和乘車時間。Sun等[9]計算了總出行等待時間和列車能源消耗，求得使乘客和運營商兩者利益達(dá)到平衡的列車時刻表。

遺傳和聲算法(genetic harmony algorithm)是將遺傳算法與和聲算法結(jié)合的改進(jìn)啟發(fā)式算法，目前已經(jīng)被應(yīng)用到很多復(fù)雜問題的優(yōu)化中。韓紅燕等[10]為了驗證改進(jìn)遺傳和聲算法的可行性對6個測試函數(shù)進(jìn)行仿真，結(jié)果顯示改進(jìn)后的算法計算結(jié)果更優(yōu)，而且能提高搜索效率，更容易跳出局部極小。王英博等[11]設(shè)計了車輛配送路徑優(yōu)化模型，在求解時使用了改進(jìn)的遺傳和聲算法，減輕了初始記憶庫對算法的影響，使求解時間減少，并提高了準(zhǔn)確性。張風(fēng)榮[12]提出遺傳和聲算法能夠幫助提高解的質(zhì)量，提升算法跳出局部極小的能力。

綜上所述，目前的研究傾向于單獨討論行車計劃或單獨優(yōu)化列車時刻表。在此基礎(chǔ)上，本文將行車計劃的結(jié)果作為列車時刻表優(yōu)化的約束條件，將兩者結(jié)合從而獲得更好的優(yōu)化效果。在模型求解時，設(shè)計遺傳和聲算法求解，并通過計算比較，驗證了該算法對于解決本文提出的優(yōu)化模型的合理性和準(zhǔn)確性。

1 行車計劃和列車時刻表優(yōu)化

在一條單線循環(huán)的線路中，如圖1所示，共有2K個車站。車站的編號依次為1,2,…,K，車站1和K分別表示每條線路的起點和終點，列車在線路上循環(huán)行駛。為了使模型的表述更加簡單，將圖1所示的循環(huán)線路分成兩個方向：f=1表示上行方向；f=2表示下行方向。由于兩條線路方向相反，認(rèn)為乘客不換乘即乘客的需求相互獨立。

圖1 軌道交通單線循環(huán)示意圖

1.1 模型假設(shè)和參數(shù)規(guī)定

為了使模型的表達(dá)更加清晰，本文主要作了以下假設(shè)：

注：T為計劃期結(jié)束時刻。

(2)折返站有足夠的容量容納來的列車。除了折返站，一個車站每次只能接受一輛列車，網(wǎng)絡(luò)上不會發(fā)生越行。

(3)如果折返站的列車超過一輛，在調(diào)度時遵循先來先服務(wù)原則。

(4)列車循環(huán)受最小車頭時距和折返站的折返時間的限制。

(5)在折返站對向到達(dá)的車輛優(yōu)先折返發(fā)車，在對向車輛沒有到達(dá)時，采用備用車輛，沒有備用車輛不發(fā)車。

(6)列車在運行中采取站站停的停站方式。

本文的優(yōu)化分兩步進(jìn)行，首先給出行車計劃，然后以此為基礎(chǔ)優(yōu)化列車時刻表，模型參數(shù)如表1所示，變量如表2所示。

表1 模型參數(shù)

表2 中間變量與決策變量

1.2 行車計劃

為了滿足線路上的客流需求，同時節(jié)約城市軌道系統(tǒng)運能和運輸資源，在規(guī)定了研究計劃期后，結(jié)合最大斷面客流、列車容量、設(shè)計滿載率和最大發(fā)車間隔等影響因素。不考慮列車跳停，計劃期開行的列車數(shù)按照如下公式計算：

(1)

為了保證公式(1)計算的開行對數(shù)有意義，要求地鐵公司在車輛段必須準(zhǔn)備一定數(shù)量的運用列車數(shù)，該列車數(shù)與高峰小時列車開行對數(shù)、每列車的編組數(shù)以及列車周轉(zhuǎn)時間有關(guān)。本文假設(shè)每輛列車為6輛車編組，需要的列車數(shù)nf按如下公式計算：

(2)

通過計算得出能夠滿足乘客需求的行車計劃。

1.3 列車運行時刻表優(yōu)化

為了更好地描述模型，對文中的中間變量進(jìn)行簡單計算，第k個車站對于第r個列車的潛在乘客數(shù)按照公式(3)、(4)進(jìn)行計算，是第r-1列車離開后第k個車站剩下的乘客與第k個車站在時間間隔[dk,r-1,f，dkrf]新到達(dá)的乘客數(shù)量之和，而對第一輛列車來說是列車到達(dá)車站之前到達(dá)的乘客數(shù)量。

(3)

(4)

公式(3)、(4)中時間間隔[dkrf，dk,r+1,f]期間到達(dá)的乘客數(shù)量按照公式(5)、(6)計算，公式(6)表示第k個車站從最后一輛列車發(fā)出后到達(dá)的乘客數(shù)量。

(5)

(6)

公式(3)中列車從k站出發(fā)時刻的站臺上沒有上車的乘客數(shù)量按照公式(7)、(8)計算，即為想要上車的乘客數(shù)量減去考慮列車運力后實際上車的乘客數(shù)量。

(7)

(8)

此外，當(dāng)列車從第k個車站離開時列車上的乘客數(shù)量可以使用公式(9)、(10)計算，一輛車從車站出發(fā)后的載客量等于其到達(dá)時的載客量加上上車乘客減去下車乘客。

(9)

(10)

上車的乘客數(shù)量計算分兩種情況，當(dāng)候車乘客數(shù)量大于車上剩余位置時，上車的乘客數(shù)量等于列車上的剩余位置，否則等于候車的乘客數(shù)量也就是說候車的乘客都能上車。

(11)

(12)

在前文計算得到行車計劃的基礎(chǔ)上，將乘客在站臺的等待時間分為四部分，第一部分為由于列車滿員未能上車的乘客的等待時間，第二部分是在兩輛服務(wù)列車運行間隔期間到達(dá)的乘客的等待時間，第三部分是指第一輛車到達(dá)車站之前乘客的等待時間，第四部分是列車服務(wù)結(jié)束后到規(guī)劃期結(jié)束之前乘客的等待時間。

(13)

可以為線路提供服務(wù)的列車數(shù)量是有限的，因此這個問題的主要解決方案是優(yōu)化所有列車的發(fā)車時間以及到達(dá)時間。利用表1～3的變量和參數(shù)，列車時刻表優(yōu)化模型需要滿足以下約束：

(14)

(15)

(16)

(17)

(18)

(19)

約束(14)是最小以及最大車頭時距限制，結(jié)合《地鐵設(shè)計規(guī)范》[13]對于城市軌道交通列車高峰和平峰的運行間隔的規(guī)定，為了保證列車運行的安全性，列車運行時的車頭時距不能小于最小追蹤間隔hmin=2 min，最大運行間隔為hmax=10 min。約束(15)保證列車在計劃期內(nèi)發(fā)車的均衡性。在不同的階段，列車發(fā)車時間的跳躍性可增長乘客的出行時間，列車的發(fā)車間隔應(yīng)保證均衡性[14]，其中α∈[0,1]，β∈[0,1]。約束(16)規(guī)定了列車在車站的停留時間，列車的停車時間等于列車離開站臺的時刻減去列車到達(dá)站臺的時刻，列車在站臺上的停留時間太短會導(dǎo)致乘客無法順利上車，停留時間過長則會增加乘客的旅行時間，因此列車在站臺上的停靠時間應(yīng)該控制在合理的范圍內(nèi)。約束(17)規(guī)定了列車的折返作業(yè)組織，說明了起始站的發(fā)車時間與對向列車的到達(dá)時間以及折返作業(yè)時間相關(guān)，在服務(wù)列車數(shù)量有限的情況下，如果列車晚點，可能造成整個線路的列車運行發(fā)生故障。約束(18)為車站空余約束，假設(shè)除折返站外其余車站每次只能停一輛列車，該約束保證車站只有不大于一輛列車?？?。約束(19)為運營時間約束，第r列列車在第f方向列車從k站行駛到k+1站的時間為Rkf。

2 遺傳和聲算法

傳統(tǒng)的遺傳算法在優(yōu)化大規(guī)模不規(guī)則問題時，計算時間長，難以實現(xiàn)全局搜索，給求解造成一定困難。Geem[15]受協(xié)調(diào)樂隊演奏出音樂的啟發(fā)，抽象出一種新的啟發(fā)式智能算法——和聲算法，具有概念簡單、可調(diào)參數(shù)少、容易實現(xiàn)的特點，并成功應(yīng)用于函數(shù)優(yōu)化問題，但取值概率以及微調(diào)概率的不同對求解過程以及結(jié)果影響較大，求解復(fù)雜問題容易陷入局部最優(yōu)。為了優(yōu)化兩種算法的缺點，本文將遺傳算法和和聲算法組合并優(yōu)化，優(yōu)化后算法穩(wěn)定性強，比原算法跳出局部最小的能力強[12]。將問題的求解分成以下兩個部分：運用遺傳算法求得一組列車到達(dá)始發(fā)站時刻和停站時間，作為和聲初始庫輸入和聲算法進(jìn)行求解；再運用和聲搜索機制在得到的始發(fā)站時刻和停站時間的次優(yōu)種群中進(jìn)行搜索微調(diào)，獲得更優(yōu)的列車時刻表。

具體算法求解步驟如下，求解邏輯圖如圖3所示。

圖3 算法邏輯圖

步驟1：初始化算法參數(shù)。設(shè)定最大遺傳代數(shù)、種群規(guī)模、交叉變異概率、和聲記憶庫大小、和聲保留概率、音調(diào)微調(diào)概率、擾動帶寬、和聲迭代次數(shù)。

步驟2：編碼。染色體由車輛到達(dá)始發(fā)站時間和列車在站臺?？繒r間兩部分組成。根據(jù)計劃期以及列車服務(wù)總次數(shù)Df生成所有方向的列車到達(dá)始發(fā)站時刻的初始編碼；根據(jù)各區(qū)間列車最大?？繒r間和最小?？繒r間為界限隨機生成列車在站臺停靠時間編碼。

步驟3：選擇操作。根據(jù)得到的每一個列車在初始站到達(dá)時刻和停站時刻組結(jié)合路段運行時間，計算乘客在站臺等待的時間，根據(jù)得到的等待時間的倒數(shù)分配個體被選擇的比例，隨機選擇，更新種群。

步驟4：交叉操作。將染色體片段分為列車始發(fā)站到達(dá)時刻片段和列車停站時間片段，隨機選擇兩個父代個體，選擇基因起止位置，選擇方式為隨機選擇，交換這兩組基因的位置。進(jìn)行沖突監(jiān)測，監(jiān)測列車始發(fā)站到達(dá)時刻片段是否出現(xiàn)重復(fù)整數(shù)，是否滿足列車追蹤間隔約束，保證子代基因無沖突。比較交叉前后個體的適應(yīng)度大小，將較優(yōu)個體加入到子代。

步驟5：變異操作。經(jīng)過多次計算嘗試，本文變異參數(shù)p的取值范圍為0.05～0.20。與交叉操作類似，將染色體片段劃分為列車始發(fā)站到達(dá)時刻片段和列車停站時間片段。列車到達(dá)始發(fā)站時刻組是一組升序自然數(shù)，列車在站停車時間組是一組最大和最小停站時間范圍內(nèi)的隨機自然數(shù)，因此，對前者基因片段采用均勻變異法，對后者采用插入變異法，驗證變異后的染色體片段是否滿足優(yōu)化問題中的約束條件，滿足則將變異后的個體遺傳到下一代。

步驟6：遺傳算法結(jié)束條件。若迭代次數(shù)小于最大遺傳代數(shù)，進(jìn)行步驟7，否則返回步驟3。

步驟7：生成新和聲。步驟6得到的次優(yōu)種群輸入為和聲算法的和聲庫，一系列列車到達(dá)時刻和停站時間，通過隨機選擇、和聲保留、擾動原則等3個原則產(chǎn)生新解，擾動原則為Xnew=X+2LbwR-Lbw，其中，X表示解的集合，R是0和1之間的隨機數(shù)，Lbw是擾動帶寬。

步驟8：更新記憶庫。根據(jù)步驟7得到新的時刻表，驗證得到的時刻表是否滿足以上模型的約束條件，滿足則求乘客站臺等待時間，將其與原來最長等待時間比較，若小于則替換，和聲記憶庫更新。

步驟9：和聲算法終止條件。迭代次數(shù)是否小于最大迭代次數(shù)，否則返回步驟7，是則輸出求解的較優(yōu)列車到達(dá)始發(fā)站時刻和列車停車間隔時間，轉(zhuǎn)化為優(yōu)化后的最終的列車時刻表。

3 算例分析

本文以圖4所示的單線循環(huán)的線路為例，共有2×5個相互獨立的車站。循環(huán)線路分成兩個方向：f=1表示上行方向；f=2表示下行方向。兩條線路相互獨立，不存在乘客換乘。為了驗證本文所提方法的正確性及模型的效果，兩端都有車輛段可以發(fā)車，列車從1車站發(fā)車后，經(jīng)過車站2、3、4后在車站5進(jìn)行折返并從另一方向的車站1繼續(xù)發(fā)車，研究時間段為5400 s。

圖4 算例示意圖

3.1 參數(shù)設(shè)置

列車的各項基本參數(shù)如表3所示。

表3 列車運行基礎(chǔ)參數(shù)

遺傳和聲算法參數(shù)包括種群規(guī)模100、交叉概率0.7、變異概率0.2、最大遺傳代數(shù)600、和聲記憶庫大小100、和聲迭代次數(shù)600、和聲保留概率0.95、音調(diào)調(diào)節(jié)率0.3和擾動帶寬0.2。

OD矩陣(origin-destination matrix)又名起訖點矩陣，其中“O”指出行的出發(fā)地點，“D”指出行的目的地，直觀簡潔地表示了從一個地點向另一個地點轉(zhuǎn)移的客流數(shù)量。本文軌道交通線路上的乘客出行OD矩陣如表4所示。

表4 乘客出行OD矩陣

3.2 計算結(jié)果

根據(jù)上述參數(shù)和約束條件，使用遺傳算法和遺傳和聲算法分別計算得到的9次較優(yōu)解的結(jié)果以及平均值，見表5。

表5 遺傳算法與遺傳和聲算法計算人均候車時間對比

通過表5的對比可以直觀地看出，遺傳算法共搜索到了3次較優(yōu)解，人均等待時間為1141 s/人，9次較優(yōu)解的平均值為1 152.6 s/人。而遺傳和聲算法共搜索到了7次較優(yōu)解1141 s/人，9次較優(yōu)解的平均值為1 144.6 s/人。結(jié)果表明，遺傳和聲算法相較遺傳算法計算結(jié)果更加準(zhǔn)確，跳出局部最小的能力更強，體現(xiàn)了遺傳和聲算法的應(yīng)用價值。

在按照客流需求給出行車計劃后，用Matlab設(shè)計的遺傳和聲算法求解列車時刻表優(yōu)化模型得到較優(yōu)解。圖5是根據(jù)解所繪制的列車運行圖，優(yōu)化結(jié)果符合列車運行安全等約束。

圖5 列車運行圖

4 結(jié)論

本文根據(jù)客流需求計算行車計劃，將行車計劃結(jié)果用于列車時刻表的優(yōu)化模型，并采用遺傳和聲算法求解優(yōu)化問題，提高了求解效率和準(zhǔn)確性。最后通過算例分析，得到了符合實際且合理的列車時刻表。在未來的工作中，將進(jìn)一步研究混合編組、跨站停車、快慢車等復(fù)雜條件下行車計劃的制定和列車運行時刻表的優(yōu)化問題，并進(jìn)一步驗證遺傳和聲算法求解這類復(fù)雜問題的合理性和準(zhǔn)確性。