曹璐，曹成鉉

(北京交通大學(xué) 軌道交通控制與安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100044)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 模型參數(shù)

表2 中間變量與決策變量

1.2 行車計(jì)劃

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

(1)

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

(2)

通過(guò)計(jì)算得出能夠滿足乘客需求的行車計(jì)劃。

1.3 列車運(yùn)行時(shí)刻表優(yōu)化

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

(3)

(4)

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

(5)

(6)

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

(7)

(8)

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

(9)

(10)

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

(11)

(12)

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

(13)

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

(14)

(15)

(16)

(17)

(18)

(19)

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

2 遺傳和聲算法

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

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

圖3 算法邏輯圖

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

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

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

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

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

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

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

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

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

3 算例分析

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

圖4 算例示意圖

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

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

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

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

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

表4 乘客出行OD矩陣

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

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

表5 遺傳算法與遺傳和聲算法計(jì)算人均候車時(shí)間對(duì)比

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

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

圖5 列車運(yùn)行圖

4 結(jié)論

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