林禹童，曹成鉉，柳雨彤，馮紫嫣

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

城市軌道交通為市民提供了便利的出行方式，具有運行速度穩(wěn)定、運輸量大的特點。隨著交通需求量的增加，城市軌道交通也面臨著較大的運營壓力。因此，設(shè)計一個與客流需求相匹配的列車時刻表和車底調(diào)度計劃，對提高城市軌道交通的服務(wù)質(zhì)量具有重要的現(xiàn)實意義。

在城市軌道交通列車調(diào)度問題的相關(guān)領(lǐng)域，國內(nèi)外學(xué)者已經(jīng)取得了很多研究成果，這些成果多以列車時刻表和客流需求匹配為目標(biāo)。Sch?bel[1]以乘客滿意度為目標(biāo)，將路線規(guī)劃、時刻表制定和列車調(diào)度三個規(guī)劃階段整合進(jìn)行綜合規(guī)劃。Wang等[2]提出了以客流需求為目標(biāo)的混合整數(shù)非線性規(guī)劃模型，求解和客流需求匹配的列車運行時刻表。Shi等[3]提出了以乘客滿意度為目標(biāo)的模型，該模型主要討論在過飽和客流情形下，如何給出最優(yōu)的列車時刻表和精確的客流控制策略。Robenek等[4]以乘客滿意度為核心建立求解最優(yōu)列車時刻表的混合整數(shù)線性規(guī)劃模型。Robenek等[5]又對文獻(xiàn)[4]的模型進(jìn)行改進(jìn)，引入乘客的隨機(jī)需求要素，建立彈性需求模型。國內(nèi)學(xué)者在相關(guān)研究領(lǐng)域也取得了一些成果。Yu等[6]和王世峰[7]提出了動態(tài)客流需求雙層規(guī)劃模型，并通過模型求解給出較優(yōu)的列車時刻表和車底調(diào)度計劃。薛彤[8]應(yīng)用BP(back propagation)神經(jīng)網(wǎng)絡(luò)算法預(yù)測客流需求，對根據(jù)客流需求制定列車調(diào)度方案具有很大的參考價值。以上研究主要基于乘客需求建立模型，并進(jìn)行求解，但未考慮城市軌道交通運行成本。

文獻(xiàn)[9-11]以列車的最小運行時間為目標(biāo)建立優(yōu)化模型，得出最優(yōu)列車車底調(diào)度方案，并對列車運行圖的編制進(jìn)行優(yōu)化。周翔翔等[12]運用遺傳算法，解決了軌道交通列車系統(tǒng)在以成本最低為目標(biāo)時的最優(yōu)列車開行方案。以上研究都是以城市軌道交通運營成本最小為目標(biāo)給出解決方案。

目前的研究一般都是以乘客滿意度或城市軌道交通運營成本最小為目標(biāo)。本文在此基礎(chǔ)上，在建模時綜合考慮了乘客滿意度和城市軌道交通成本兩個要素，將兩者結(jié)合構(gòu)建目標(biāo)函數(shù)。在模型求解上，運用模擬退火算法，設(shè)計出列車時刻表和車底調(diào)度方案，并通過數(shù)值算例驗證模型的可行性。

1 模型建立

1.1 問題描述

在一個線狀的線路中，有m個車站，車輛段位于線路的起終點站，線路如圖1所示。列車運行路線有兩個方向，分別是方向b1和b2，兩個方向經(jīng)過的車站完全相同，在線路中所有的站都需要?？浚渲?，車站1為起點站，車站m為終點站。

列車運行方式為列車開始從某車輛段出發(fā)，到達(dá)某方向bi的起點站1站，然后沿方向bi出發(fā)，到達(dá)終點站m后，再進(jìn)入對面的車輛段，從相反方向b3-i的起點站1站出發(fā)，執(zhí)行新的運輸任務(wù)(在該問題中有兩個方向b1和b2，b1的相反方向為b2，b2的相反方向為b1，因此在一般性的描述中，用b3-i表示某方向bi的相反方向)。

圖1 城市軌道線路圖Fig.1 Urban rail transit line

1.2 模型假設(shè)

(1)兩個方向的列車在各自的線路上，互不干擾。

(2)列車在所有中間車站均停車，且停車時間為定值。

(3)車底不屬于特定的車輛段。

(4)列車到達(dá)中間站的下車率為定值。

(5)列車從某個車站發(fā)車到達(dá)另一個車站的時間為定值。

1.3 符號說明

模型中所使用的符號集合見表1，模型參數(shù)在表2中給出，模型變量見表3。

表1 符號集合

表2 模型參數(shù)Table 2 Parameters of model

表3 模型變量

1.4 模型構(gòu)建

該模型的目標(biāo)為綜合目標(biāo)，總共分為兩個子目標(biāo)，如下：

(1)降低運營成本

(2)降低乘客總等待時間

總乘客等待時間的計算方式，將總時間段分割成相等的離散時間段，對在每一個小的離散時間段內(nèi)車站等待的乘客數(shù)進(jìn)行計數(shù)，將每一個時間段內(nèi)的乘客數(shù)相加，乘以離散時間段的時間單位得到總乘客等待時間。

設(shè)在方向b,車站i上的車次k和k+1的發(fā)車間隔為l，其中,

l=dk+1,i,b-dk,i,b。

(1)

單位時間段為Δt, 到達(dá)率定義為Δt內(nèi)到站人數(shù)為λib，設(shè)將時間間隔分割成n個時間段，在k次列車發(fā)車后，有人數(shù)為wkib的乘客滯留在i站。其中，滯留的乘客在車次k和k+1之間的等待時間

t1=wkibl。

(2)

計算車次k和k+1次之間進(jìn)站的乘客等待時間。由于乘客進(jìn)站率為定值，每一個小時間段人數(shù)都增加lλib/n，則進(jìn)站乘客的等待時間

(3)

在乘客達(dá)到率為定值的情形下，可以視為連續(xù)到達(dá)，則取極限

(4)

則有在該時間區(qū)間內(nèi)，乘客總等待時間t總

(5)

在初始發(fā)車前的時間，滯留乘客數(shù)為0，所以乘客總等待時間為

(6)

將兩個目標(biāo)乘以一定的系數(shù)求和后形成一個綜合目標(biāo)，并以該目標(biāo)函數(shù)最小化為最優(yōu)目標(biāo)。

在約束條件中，需要充分考慮要素：客流的分布情況；可調(diào)用的車底數(shù)量；列車乘客容量；最小停車間隔；客流狀態(tài)平衡的約束，其中起點站乘客下車率為0，終點站為100%。

該模型的綜合表述如下：

(7)

s.t.

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

2 算法設(shè)計

圖2 算法流程圖Fig.2 Flow chart of algorithm

在大規(guī)模問題中，找到較優(yōu)列車調(diào)度方案的方法是先根據(jù)總的客流需求情況找到一個初始的運行方案，再根據(jù)每一時刻具體的客流狀況沿著一定路徑進(jìn)行調(diào)整，逐漸找到較優(yōu)的運行方案。由于該問題的混合整數(shù)規(guī)劃模型由0-1決策變量組成，理論上可以使用枚舉法找到最優(yōu)解。但如果模型規(guī)模較大，則枚舉法并不可行，而模擬退火算法可以提高尋找最優(yōu)解的效率且可有效避免陷入局部最優(yōu)解的困境，因此該模型的求解應(yīng)用模擬退火算法。算法流程圖如圖2所示，應(yīng)用該算法的具體步驟如下：

步驟1：初始化。給出初始溫度T0、終止溫度Tf,以及迭代次數(shù)n,第一步令T=T0,n=0,轉(zhuǎn)步驟2。

步驟2：隨機(jī)生成一個優(yōu)化方案X′ 。判斷此方案能否滿足約束，若滿足，則X′是可行的，令X′=X0，轉(zhuǎn)步驟3繼續(xù)迭代；若不滿足，則對未滿足約束條件的方案進(jìn)行隨機(jī)調(diào)整，直到生成一個可行方案，得到初始可行解，轉(zhuǎn)至步驟3。

步驟3：對該方案進(jìn)行隨機(jī)擾動，直到得到一個符合約束的新方案X,并計算該方案和原可行方案X0的目標(biāo)函數(shù)的增量Δf=f(X)-f(X0)，轉(zhuǎn)至步驟4。

步驟 4：若Δf<0，則令X=X0，即接受路徑X為新的路徑；若Δf≥0，計算p=exp (-Δf/T0)，若p為大于(0,1)的隨機(jī)數(shù)，令X=X0，讓X成為新路徑，轉(zhuǎn)至步驟5，否則轉(zhuǎn)至步驟3。

步驟 5：進(jìn)行終止條件判斷，滿足則給出可行方案，結(jié)束迭代；否則更新T0，令n=n+1轉(zhuǎn)至步驟3。

3 數(shù)值案例

圖3 數(shù)值案例線路圖Fig.3 Transit line in numerical case

表4 算例參數(shù)

表5 乘客需求

根據(jù)表4算例參數(shù)和表5乘客需求狀況，應(yīng)用模擬退火算法，得到的較優(yōu)解對應(yīng)的時刻表如表6所示。城市軌道交通列車運行圖如圖4所示。

表6 列車運行時刻表

圖4 城市軌道交通列車運行圖Fig.4 Diagram of timetable planning in urban transit line

在該時間段內(nèi)，由于方向b1的乘客需求大，因此和方向b2比，發(fā)車頻率較高。在目標(biāo)函數(shù)中考慮降低乘客總等待時間和列車運行成本后，其發(fā)車頻率更加合理。若僅考慮降低乘客總等待時間，則成本的增加量高于乘客總等待時間的降低量后，目標(biāo)函數(shù)值會增加。在建立目標(biāo)函數(shù)時，綜合考慮乘客等待時間和運營成本，可得到一個和客流需求匹配，且能夠節(jié)約成本的列車運行計劃。

4 結(jié)論

本文根據(jù)乘客需求，以最小化乘客總等待時間和城市軌道交通系統(tǒng)運營成本為綜合目標(biāo)，建立混合整數(shù)規(guī)劃模型。在模型求解時，運用模擬退火算法得到較優(yōu)的列車時刻表和車底調(diào)度方案，并通過算例分析對模型進(jìn)行驗證，結(jié)果證明該較優(yōu)解是符合客流需求的。

本文數(shù)值算例的計算結(jié)果與預(yù)期一致。相比目標(biāo)函數(shù)中僅考慮單一要素，本文考慮綜合要素后給出的列車調(diào)度方案，發(fā)車頻率保持在一個合理的范圍，且和客流需求更加匹配，不會出現(xiàn)列車發(fā)車頻率過高或者過低的情況。而保持一個合理的發(fā)車頻率，既可以降低乘客等待時間，提高乘客滿意度，又可以降低列車運營成本。

但是該模型是在列車停站時間及客流下車率為定值的假設(shè)下提出的，缺乏靈活性，如果乘客下車率在不同車站不同時段是變動的，則對于該優(yōu)化問題中模型提出了更多的改進(jìn)要求，這也是下一步的工作方向。