考慮客流時變特性的列車時刻表優化方法

張矢宇, 楊云超, 楊宇昊

(1.武漢理工大學 交通學院,湖北 武漢 430063; 2.河南省交通規劃設計研究院股份有限公司,河南 鄭州 450000)

0 引言

近年來,城市軌道交通憑借其容量大、速度快、消耗低和綠色環保的特點迅速成為解決大城市擁堵問題的優先考慮對象。客流是交通運輸能力和運輸系統合理配置、制定運營計劃的重要因素。城市軌道交通中的乘客流量明顯存在時間和空間不平衡,沿線各車站的入站和出站車站的乘客流量差異很大。目前國內外城市軌道交通的出發間隔一般根據每小時的OD客流量或每小時最大客流量確定,運行方式為均衡運行方式。同等間隔的平衡列車模式易于管理,廣泛用于控制國有和城際列車的運行,但對于城市地鐵,這種調度模式可在高峰時段使用,隊列中的等待時間太長,非高峰容量被浪費,并且每列的載客率不平衡,將不可避免地導致運營成本增加或服務水平下降,阻礙了城市軌道交通服務水平的提高。研究表明利用實際動態客流信息、科學建模方法和優化算法來解決城市軌道交通中的時間表優化問題是十分關鍵的。

國內外對于軌道交通時間表優化的研究成果較為豐富,研究成果較多。隨著動態客流信息可獲取性越來越強,使用動態客流信息進行時刻表優化,能為乘客提供更好的旅行服務[1]。曹亮[2]構建了基于客流需求的旅客列車時刻表優化模型;許得杰等[3]構建了考慮客流時變需求的大小交路列車時刻表優化模型;ZHU等[4]構建了考慮乘客出發時間的時刻表優化模型;祁奇[5]構建了基于動態客流的城軌列車時刻表優化模型。對現有單線時間表優化的研究考慮了動態客流特征,主要是通過優化時間表來減少乘客等待時間[6,7],缺乏對更靈活的停車模式的研究。綜上所述,對時間表的優化研究不單單要考慮客流的時間不平衡,同時也要考慮其空間不平衡,即考慮客流的時空不平衡性。

基于以上成果,本文分析了城市軌道交通客運需求的時變特征,給出了一種基于客運效率計算客運成本的方法;建立了城市軌道交通列車時刻表的優化模型,并設計了一種基于仿真的兩階段遺傳算法求解該模型;以武漢地鐵一號線為例進行實證分析,驗證了模型和算法的有效性。

1 考慮客流時空特性的列車時刻表優化模型

1.1 問題描述

(1)研究對象

如圖1所示,城市軌道線路共有n個站點,列車出發方向記為f=1,返回方向記f=2。所有列車從出發站出發,到終點站后返回,休整后進入等待下一次出發的空閑車道。

圖1 城市軌道交通線路示意圖

(2)研究時段

為了更好地解釋乘客的乘車過程,將為不同的車站分配不同的研究時段,具體見圖2。每個站的研究時段如下:

圖2 運行圖示例

車站11:[Tb(11),Te(11)]=[6:00,8:00]

車站21:[Tb(21),Te(21)]=[6:06,8:06]

……

車站22:[Tb(22),Te(22)]=[6:39,8:39]

車站12:[Tb(12),Te(12)]=[6:45,8:45]

整個研究時段為[0,T],0表示開始時間,即圖2中的6∶00,T表示結束時間,即圖2中的8∶45。為了便于建模,將[0,T]離散化為一系列相等長度的時間段,[0,T]可以表示為一組離散節點的集合,Γ={0,1δ,2δ,3δ,…,(m-1)δ,mδ}。這里,δ表示時間間隔,0表示研究時段的開始時間,mδ表示研究時段結束時間。為了簡化說明,在后面的時間的說明中省略了時間間隔δ,即Γ={0,1,2,3,…,(m-1),m}。

1.2 基本假設及變量定義

(1)基本假設

根據研究經驗做出假設,具體如下:

①沿地鐵運輸路線的車站的旅行需求和乘客到達分布是已知,且相對穩定的。

②所有列車在相同路段的運行過程和時間都是固定且相同的。

③所有列車為同一款列車,容量是已知,且在列車運行期間,不允許乘客數量超過列車上的最大人數。

④車站的設計容量是已知的,并且車站的最大容量不應超過車站的設計容量。

根據研究,在車站聚集的人數與在平臺上等待的人數和下車的乘客數量密切相關。由于每列列車的乘客人數眾多,預測下車人數較為困難。為簡化計算,本文僅預測在研究期間可以沿著線路下車的最大人數,并且將車站容量安全約束轉換為在車站等待的人數。可以使用以下公式計算在車站等待的最大人數:

(1)

(2)變量定義

模型中變量具體定義如下:

N:車站,N={1,2,3,…,n};

Nf:車站站臺,Nf={11,12,21,22,…,n1,n2};

uf:當f=1時,站u的上行方向上的站臺,當f=2時,站u的下行方向上的站臺;

L:運行線路的長度;

R:列車編號,R={1,2,3,…,rmax};

r:開行列車編號;

rmax:最大列車編號;

Puν:車站u的乘客前往車站ν的概率;

qu:研究時段到達的乘客總數;

du:列車在車站u停車的時間;

Su,u+1:列車在時間段[u,u+1]的運行時間;

e1:在出發站1修整列車的時間;

en:在n站折回列車的時間;

m:離散時間段長度;

φ1:每單位時間購買列車車廂的成本;

φ2:列車車廂的行駛距離轉換費;

η:乘客等待值;

Hmax:最大發車間隔;

Hmin:最小發車間隔;

CT:列車容量;

B:列車數量;

?:最大載客率;

θu:乘客到達閥值,如果在車站等候的乘客數量小于θu·γu,乘客可以進入車站u,否則乘客將等待下一站機會,需要在車站外排隊;

ωu,t:0-1變量,如果站u允許乘客在時間t進入車站,則ωu,t=1,否則ωu,t=0;

TFr:列車r重新進入空閑車底的時間;

K:可用車輛的總數;

NFt:t時刻站1的具有空閑車底數,NF0=K;

σu,t:0-1變量,當車站u處于擁擠狀態時,即當不允許乘客進入車站時,σu,t=1,否則,σu,t=0;

xt:0-1決策變量,如果在時間t有列車離開站1,則xt=1,否則xt=0;

X:決策變量向量,X={xt,t∈Γ}。

1.3 優化模型

(1)目標函數

運行單位總是希望滿足乘客的出行需求的條件下盡可能地降低運營成本;乘客總是希望盡可能高效地出行。因此,城市軌道交通業務的決策部門需要從整個系統的角度全面考慮雙方的利益,優化列車時刻表。

①運營單位

地鐵運輸運營成本一直是相關運營單位在優化城市軌道交通列車時刻表方面的重點。本文的運營成本主要包括調查期間購買列車的成本和行駛距離的成本。研究時段的列車購買成本可以通過以下公式計算:

(2)

研究時段列車行駛公里的轉換成本可以通過以下公式計算:

(3)

②乘客

作為城市軌道交通的服務,乘客總是希望提高效率。然而,一旦地鐵線路和車站完工,將很難改善乘客的步行和乘車時間。因此,本文重點關注減少乘客等待時間,通過減少乘客的等待時間來提高乘客的出行效率。

每個乘客的移動過程簡單描述如下:到站-進站-候車-上車-下車-出站。乘客等待過程可分為以下站內等待和站外等待兩種。

基于上述分析,乘客上車和到達的時間差就是實際等待時間,具體如下:

(4)

然而,由于等待環境的影響,乘客對車站外的等待時間敏感,而等待列車的等待時間由于列車滿載而使得感知的等待時間長于實際等待時間。因此,在本文中,通過引入懲罰系數α和β(α,β>1),此參數表明了乘客站內外等待時間的感知誤差。另外此處引入了時間價值因子,將乘客的等待時間轉換為乘客的廣義等待時間成本。乘客的總等待時間如下:

(5)

(2)列車時刻表優化模型

基于以上分析,建立如下的優化模型:

(6)

(14)

2 基于仿真的優化模型求解方法

遺傳算法是模擬生物進化機制的全局隨機搜索和優化算法,被廣泛用于解決運輸行業優化問題[8-11]。基于以上分析,提出了一種基于仿真的遺傳算法求解該模型。

2.1 仿真過程

列車仿真過程模擬包括列車出發和列車到達兩個事件。具體仿真模擬過程如下:

①當根據列車的時間表確定每個列車出發站的出發時間并且將模擬時間提前到列車的出發時間時,即是否滿足列車的出發需求。如果空閑車底存在(NFt≥1),列車將準時離開出發站,相反,如果沒有空車的底部(NFt<1),列車將按計劃出發。

②當列車開始運行時,根據行程和停止時間,按順序計算列車沿車站的到達和離開時間。

③當列車返回出發站并且修理工作的時間結束時,列車使用的車底進入空閑車底行列,此時,NFt←NF+1。

另外,列車下車最大人數直接影響每個車站最大乘客人數的計算結果、乘客的等候時間和每列車的乘客人數。然而,由于在模擬之前難以準確地計算來自每個站的列車的最大數量,因此在本文中,在模擬期間添加反饋處理,并且不斷更新每個站的最大列車數量,確保其小于車站的安全容量。

2.2 基于仿真的兩階段遺傳算法

由于決策變量X是與二進制編碼形式相似的0-1變量,直接將其作為遺傳算法的染色體。

根據解向量X的結構,可以看出,可以表示任何一種開行方案,即在研究時段從始發站發送的列車的數量可以從0～m變化。然而,如果兩列地鐵列車之間的距離太長或太短,由于約束(7)和(8)難以滿足,大多數開行方案將不可行。如果仍然使用傳統的遺傳算法求解方法,則需要大量的計算時間來隨機生成具有特定可行性的指定數量的初始解決方案組。為提高效率,提出了一種基于仿真的兩步遺傳算法。具體過程如下:

(1)階段1:產生初始解候選集合

為提高效率,在優化之前提前部分生成初始解候選合集。

①生成均衡方案合集。該方案為等間隔發車,解決方案相對簡單,枚舉法即可以快速找到部分可行解。故采用枚舉法,將每個均衡運行計劃依次輸入到仿真模型中,選擇所有可行的均衡運行計劃。

②豐富最初解決方案。基于均衡方案生成的初始備選解決方案,通過變異操作生成部分不平衡方案,將方案代入模型,若結果可行,將方案加入候選初始解,否則則舍棄該方案。此過程中具體變異過程如下:從初始候選組中隨機選擇親本染色體,隨機產生實數a∈[0,1],如果a≤0.5,則使用突變規則I突變父染色體(見圖3)。否則,使用變體染色體II突變親本染色體(見圖4)。

圖3 變異規則I:基因片段內部重組

圖4 突變規則II:單點變異

(2)階段2:遺傳算法優化

該優化過程包括6個步驟:

步驟1生成種群進化代數最大值max_generation。

步驟2從之前生成的方案中隨機選擇pop_size個染色體作為初始種群。

步驟3將每條染色體的驅動方法輸入模型中,運行獲得參數值,并代入自適應函數以獲得每條染色體的自適應函數值。在本文中,選擇目標函數(6)作為遺傳算法的適應度函數:

Eval(Xk)=z(X),?k=1,2,…,pop_size

(15)

在該等式中,Eval(Xk)表示對應于染色體Xk的適應度函數值。

步驟4使用輪盤賭方法,從親代染色體群體中選擇pop_size個染色體以形成子染色體群體。具體程序如下:

步驟4.1找出最大的適應度函數值F:

F=max(Eval(Xk))

(16)

步驟4.2令P0=0,計算累積選擇概率Pk:

(17)

步驟4.3隨機生成實數a∈(0,1],并將其與累積選擇概率Pk(k=1,2,…,pop_size)進行比較以選擇第k個染色體(Pk-1

步驟4.4結束條件判斷。如果選擇pop_size個染色體,則終止選擇操作并輸出子染色體群,否則過程進入步驟4.3。

步驟5兩個選擇的親本染色體交叉操作產生新的染色體。具體程序為:

確定染色體交叉概率Pc,隨機選擇兩條染色體,同時隨機生成實數a∈[0,1],如果a≤Pc,則遵循單點交叉規則(圖5)染色體相交。

圖5 交叉規則:單點交叉

步驟6隨機選擇染色體突變,程序如下:

步驟6.1確定染色體交叉概率Pc,隨機選擇染色體,同時隨機生成隨機數a∈[0,1],如果a≤Pc,則進行步驟6.2以突變染色體;否則,父代染色體不改變。

步驟6.2隨機生成實數b∈[0,1],如果b≤0.5,改變父染色體,此時改變規則遵循突變規則I;否則遵循突變規則II。

步驟6.3將新生成的染色體代入模型進行模擬驗證,若方案可行,則將新染色體加入到子染色體群。

步驟7當算法達到最大進化代數時,算法結束并輸出最佳染色體;否則進化代數增加1,進入步驟3。

3 武漢地鐵一號線時刻表優化分析

3.1 參數設置

武漢地鐵1號線由26個站組成,站間的行程時間設置為5分鐘,每個站點的停止時間為30秒,返回站點的周轉時間和出發站點的翻新時間均為90秒。每個站臺的設計容量為2000,安全閾值θu=0.65。優化目標是在出發站1處制定每列地鐵列車的特定出發時間,假設每個站的乘客的到達分布規律滿足下面的分布:

在公式中,γu,μu和σu是每個站的乘客數量的基本參數,基本值如表1所示。

表1 各站客流需求的基本參數取值

顯然,當確定優化時間間隔δ時,可以通過以下等式計算各站t(t∈[1,7200/δ])的乘客需求。

(18)

例如,假設δ=180s,將發送站1的基本參數代入等式(16),并且在第一時間間隔[0,180]內到達的乘客數量是65。

以1至7站為例,表2顯示了前往每個站的乘客的概率ρuv。研究表明:3站的10%乘客可以通過地鐵轉移到1站。

算例參數取值和遺傳算法參數取值情況分別見表3和表4。

表3 算例參數取值

表4 遺傳算法參數取值

3.2 模型優化結果分析

作為優化結果和優化率的重要因素之一,優化時間間隔δ的調整對于整個結果有顯著影響,基于此本文選擇了三個不同的時間間隔(5s,10s和30s)來優化模型,收斂過程如圖6所示,優化結果如表5所示。

表5 優化結果

圖6 收斂過程

根據上述優化結果,可以得出以下結論:

①從圖6可以看出,優化結果在53代后開始收斂。

②根據表5,在δ=5s的情況下,模型的最優解優化為566142元,比δ=10s時的最優解優化了2736元,比δ=30s時的最優解優化了12549元。在此,給出δ=5s時求得到的最優開行方案。

4 結論

(1)對于所建模型基于仿真的兩步遺傳算法,收斂性強,求解效率高。

(2)選擇三個不同的時間間隔(5s,10s和30s)優化模型,優化結果在53代后開始收斂。在時間間隔為5s的情況下,模型的最優解優化為566142元,比時間間隔為10s時的最優解優化了2736元,比時間間隔為30s時的最優解優化了12549元,故時間間隔為5s時求得到的最優開行方案。

(3)通過對列車數量、車站人數和乘客等待時間進行敏感性分析,發現“小而高密度”列車運行計劃可以平衡乘客和運營單位的利益;同時,較小的平臺容量嚴重限制了城市軌道交通的服務水平,增加了城市軌道交通的運營成本;而且越小的平臺容量就會導致越高的成本,包括運營成本和乘客等候的成本。

(4)有關部門根據所得最優方案可對列車開行方案進行優化,確定更加合理的列車開行方案(包括運營時間及交路和用車計劃等),將會有效提高乘客出行效率,減少出發站每列列車的運營費用,提高了城市軌道交通服務水平,對城市軌道交通高質量發展起到推動作用。