基于人工蜂群算法的軌道交通列車行車間隔優化

方春林，劉曉娟，辛營營，羅 歡

(蘭州交通大學 電子與信息工程學院，蘭州 730070)

0 引言

隨著我國經濟的迅速發展，城市化進程速度日趨加快，城市交通壓力和公共交通供需矛盾日漸增大，城市的形態已從單一中心城形式向著都市圈、城市群以及更大范圍的區域經濟體形勢發展，城市間的聯系越來越緊密。城際鐵路以其快速便捷、舒適安全、經濟環保等特點，在區域交通中發揮著非常重要的作用，其高速度、高密度、小編組的公交化運輸組織模式也成為我國發達城市及沿海發達地區必然的發展趨勢[1]。

國內外諸多學者對列車開行方案、城際列車公交化運行的可行性及列車公交化組織等一系列問題進行了多方面的研究[2-5]。本文視旅客到達車站的過程為隨機過程(理想狀態下)，主要從旅客乘車前的等待時間及軌道運營企業的效益關系出發，提出了旅客滿意度和運營企業滿意度最佳的雙目標優化模型。其中旅客滿意度體現在旅客在車站的平均等待時間最少；運營企業滿意度則體現在列車從車站發車前的一段時間內有足夠的旅客已經到達車上(滿意的客座率)。最后采用人工蜂群算法對模型進行求解，并結合實例進行了論證。

隨著都市圈、城市群的產生，城際鐵路應運而生；關于城際鐵路，普遍認可的定義[6]是：在經濟較發達、人口較稠密的城市(鎮)群區域各個城市之間或在城市組團、次中心城鎮之間新建的便捷、快速、大運能、公交化的客運軌道交通系統，主要承擔區域內城際間或大城市周邊城際間的中短途客流運輸，專門用于開行城際列車。相應地，城際軌道交通作為區域軌道交通的重要組成部分，指在經濟發達、人口稠密的經濟區域的主要中心城市之間或在某一大城市軌道交通通勤范圍內修建的便捷、快速、運力大的客運軌道交通系統[7]。本文主要針對城際軌道交通范疇內的某一單式城際高速鐵路線上城際列車開行間隔優化問題進行研究分析。

1 客流特性描述及相關定義

本文視旅客到達車站(始發站)的過程為隨機過程[8]，設一定時間段內到達車站的旅客人數N(t)是一隨機變量，假設旅客均為獨立個體，其到達過程與其他旅客不相關；同一時段內列車的行車間隔保持不變，單位時間內期望到達車站旅客人數不變，具備如下性質：

1)互不重疊的時間段內，旅客到達人數是相互獨立，即旅客到達車站的時間互不相關；

2)某一時段，即對充分小的Δt，在時間區間(t+Δt)內單個旅客到達車站的概率與t無關，與區間長度Δt成正比；

3)對于充分小的Δt，在時間區間(t,t+Δt)內有多位旅客到達車站的概率極小，可忽略不計。根據以上性質，可證明在[0,t]時間內到達n位旅客的概率：

(1)

即旅客到達車站服從泊松分布，旅客的到達是一個泊松過程，其數學期望[8]：

E[N(t)]=λt

(2)

定義1 設{N(t),t≥0}是參數為λ的泊松過程，Δt表示[0,t]內質點出現的個數，以σn表示第n個質點的到達時刻(n=1,2,…);其累計分布函數和概率密度[8]分別為：

(3)

(4)

引理1 設{N(t),t≥0}是強度為λ的泊松過程，{Yk,k=1,2,…}是一系列獨立同分布的隨機變量，且與{N(t),t≥0}獨立，有[8]:

(5)

稱{X(t),t≥0}是復合泊松過程；若E[|Y(1)|2]<+∞，則有:

E[X(t)]=λtE[Y(1)]

(6)

引理2 設{N(t),t≥0}是強度為λ的泊松過程，對?實數t>0，N(t)=n>0的條件下，n個發生時刻(σ1,σ2,…,σn)與對應于n個[0,t]上與均勻分布且相互獨立的隨機變量順序統計量具有相同分布[8]。

2 人工蜂群算法基本原理

人工蜂群(Artificial Bee Colony, ABC)算法是由Karaboga等[9]于2005年提出的一種基于群體智能的隨機優化算法，是一種模仿蜜蜂群體尋找優良蜜源的仿生智能計算方法；具有全局搜索、并行性、易于實現且控制參數少等優點；對于復雜函數尋優具有很高的收斂性和穩定性。ABC算法中，人工蜂群包含3個組成部分：采蜜蜂(employ bees)、觀察蜂(onlooker bees)和偵查蜂(scouts)。蜂群中，采蜜蜂負責搜索和記憶蜜源(food source)(與蜜源一一對應)，并將蜜源的信息以舞蹈的形式傳遞給觀察蜂；觀察蜂以一定的選擇策略在鄰近的蜜源里選擇蜜源；如果一個蜜源連續Limit次未能更新，則放棄該位置，此時蜜源對應的采蜜蜂轉變為偵查蜂，并開始隨機搜索新的蜜源代替原蜜源。包括以下4個階段[9]：

1)初始階段。每個蜜源代表一個可行解，由：

(7)

(8)

3)觀察蜂階段。采蜜蜂完成搜索之后，觀察蜂根據接收到的信息隨機選擇一個蜜源進行開采，按照式(9)選擇蜜源：

(9)

其中：fiti表示蜜源i的適應度值，與第i個位置的蜜源花蜜量成正比；NP為蜜源的數量；如果選擇的新的適應度值更優(即全局最優解)，則替換掉原蜜源，否則原蜜源保持不變。fiti由式(10)給出：

(10)

4)偵查蜂階段。若對蜜源i使用式(8)搜索失敗，也即采蜜蜂搜索次數(蜜源停留)max(trial)超過限定次數Limit，仍未找到更高適應度的蜜源，則說明蜜源被放棄，對應采蜜蜂轉變為偵查蜂，通過式(7)隨機選擇一個新蜜源代替原蜜源。

3 模型建立

3.1 模型假設

在分析城際軌道交通列車行車間隔優化的過程中，作出如下假設：

1)旅客服從”先到先服務”原則，即先到達車站的旅客先上車，且旅客進站的過程是隨機的，在每個時段內服從不同強度的均勻分布。

2)以線路單向的行車間隔為決策變量，采用分時段的方式確定列車的行車間隔。

3)運營企業利益僅考慮列車出發前所能到達列車上的旅客數量(客座率)，旅客利益僅考慮旅客候車總時間的平均值。

4)限定線路上的列車型號統一，列車的座位數和最大容量為一定值，列車中途不停站。

3.2 旅客候車時間模型

旅客在站的等待時間即旅客到達車站的時刻至列車駛離該車站的時刻之差。假設旅客(不包括換乘)按照強度為λ的泊松過程到達車站[10-11]，列車的開行間隔為t，也即列車t時刻后發車，σi表示第i位旅客的到來時刻，則[0,t]內到達旅客等待時間總和的數學期望：

(11)

欲求旅客候車時間最少，即求：

(12)

由引理1、引理2知：

(13)

因此旅客等待時間總和的數學期望：

(14)

于是：

(15)

最終旅客候車時間最小的數學模型

(16)

其中：Emin表示取期望最小；Emax表示取期望最大。

3.3 列車等候時間模型

假設旅客數達到n時列車便發車，也即列車等待的時間為第n位旅客到達時的數學期望[10-12]：

(17)

欲求列車等候時間最大，即求：

maxf=φ(t)max={E(σn)}max

(18)

求解過程:

其中：

式(3)表示第n位旅客在[0,t]時間段內的到達概率，若令n表示定員時，理論上可用Fσn表示列車的客座率，則上式可表示為：

φ(t)=E[σn]=(Fσn(t)n)/λ

(19)

最終列車等候時間最大的數學模型：

maxf2={E(σn)}max=Emax(σn)

(20)

3.4 目標函數

綜上，兼顧運營企業和旅客雙方利益，以列車的行車間隔為決策變量、列車總等待時間最大(E[σn]越大，運營成本越高)和旅客候車時間總和最小(σ(t)越小，旅客出行成本越低)為優化目標，以運營企業效益(客座率)、行車間隔的上下限等為約束條件，建立列車行車間隔優化模型：

(21)

可以看出這兩個目標函數的優化方向是相悖的，于是引入權重系數，設置目標函數中兩項成本的加權系數值，最終的目標函數表示為：

(22)

其中：ω1、ω2為目標函數權重系數，ω1表示運營企業成本加權比例；ω2表示旅客等待時間加權比例；0<ω1,ω2<1且ω1+ω2=1。

3.5 約束條件

對于單式線路列車行車間隔優化的目標函數需滿足以下3個約束條件：

1)滿足相鄰列車最小、最大行車間隔約束；

Δtmin≤t≤Δtmax

(23)

其中Δtmin表示列車最小開行間隔；Δtmax表示列車最大開行間隔。

2)考慮到企業的利益需求，列車須滿足一定的客座率才能保證鐵路部門的正常支出：

Fσn≥A

(24)

其中A表示列車的客座率。

3)滿足對任意相鄰兩列車之間的行車時間間隔的約束；

為確保列車發車間隔的連續性，對相鄰兩列車的行車間隔之差進行一定范圍的限制：

|(Δtk+1-Δtk)-(Δtk-Δtk-1)|≤δ

(25)

其中δ表示相鄰時段發車間隔之差的極限。

4 基于ABC算法的列車開行間隔優化

4.1 ABC算法的改進

基本ABC算法作為一種隨機優化算法，同樣易陷入局部最優，繼而導致前期收斂過早、后期收斂速度變低的缺陷。究其原因，主要有：

1)基本ABC算法在采蜜蜂搜索階段，由于過度開采蜜源而導致算法的收斂速度變低，提出一種自適應搜索策略來提高算法的收斂速度[13](即在式(8)增加一權重因子ω)：

(26)

其中

2)基本ABC算法在觀察蜂搜索階段，由于蜜源被選擇的概率與其蜜源質量(收益度)成正比，在經過多次迭代之后，當前較差的蜜源(解)易被放棄，從而降低了種群的多樣性，影響算法的全局收斂能力，提出一種基于排序的概率選擇策略[14]：

首先，根據適應度值對所有蜜源進行排序，蜜源適應度越大，越靠前；然后，根據式(9)計算排序后第m個蜜源被選擇的概率：

(27)

其中

其中α表示自適應參數。

4.2 ABC算法求解過程

1)初始化。初始時刻所有蜜蜂均為偵查蜂，設置種群大小NP，最大迭代次數Max_cycle，循環限定次數Limit，權重因子ωmax、ωmin，隨機產生NP個可能的行車間隔(行車間隔即待優化值)。

2)初始適應度值計算。根據初始適應度值的大小，將蜜蜂分為采蜜蜂和觀察蜂2種，設定并記錄采蜜蜂搜索次數(依據行車間隔計算對應目標函數值)。

3)最終適應度值計算。在采蜜蜂搜索階段，使用自適應搜索機制隨機選擇蜜源進行交叉搜索，得到新蜜源并進行排序操作；在觀察蜂搜索階段，使用基于排序的概率選擇策略計算蜜源被選擇的概率(即不斷更新列車的行車間隔及對應目標函數值)。依據最終的適應度函數值評價蜜源質量，判斷其是否保留或丟棄。進行以上2種搜索機制時，須保證列車在車站的發車時刻在[Δtmin,Δtmax]范圍內。

4)終止條件判斷。如果達到終止條件，獲得最優解，則停止迭代，結束程序。本文采用最大迭代次數作為終止條件。

5)結果記錄。迭代結束后對于所有行車間隔對應的成本(總等待時間)，取最優值即最小成本，并記錄對應的行車間隔t。

4.3 算例分析

本文針對京津地區某一單式城際高速鐵路進行分析，對其線路里程及列車的行車速度等不作分析，只考慮以下方面：動車組采用CRH3型8輛編組，為便于仿真，列車定員人數設為600人；列車的最小行車間隔時間為5 min，最大行車間隔時間為20 min；規定列車的客座率須達到85%及以上；相鄰列車間的行車間隔之差為5 min。以文獻[15]中京津城際鐵路不同時段的客流基礎數據為依據，考慮到不同時段內旅客的需求不同，將某日時段劃分為早高峰、早平峰、午高峰、午平峰、晚高峰和晚平峰6個時段，且計算出不同時段旅客的平均到達強度如表1所示。

表1 京津城際鐵路不同時段客流基礎數據劃分

由于平峰時段旅客強度對列車影響較小，這里不作分析，僅對高峰時段客流強度與列車的開行間隔進行分析，不同時段旅客平均到達強度λ與列車的行車間隔t存在：

λ=λ(t)

(28)

對應早高峰、午高峰和晚高峰時段，有：

(29)

于是得到列車行車間隔優化模型為：

minf=-ω1.nFσn/λ(t)+ω2.t2λ(t)/2

(30)

s.t.

(31)

其中k=0,1,…。

4.4 模型求解

采用上述改進的人工蜂群算法進行求解，與同條件下傳統遺傳算法進行對比。在列車行車間隔優化模型中，將目標函數值作為算法的適應度值，設定模型中決策變量為列車的發車間隔t。采用實驗仿真平臺為Windows 7，Matlab 7.6。CPU為Intel Core i5-3240 3.40 GHz，內存為4.0 GB。在ABC算法中,經過多次實驗與分析，設定初始種群數目NP=50(即隨機生成50個初始解)，其中采蜜蜂和觀察蜂各占一半；最大迭代次數Max_cycle=800；循環限定次數Limit=50；權重因子ωmax=0.9；ωmin=0.3；交叉概率Pc=0.9，變異概率Pm=0.05。圖1為種群最好適應度變化圖。

圖1 種群最好適應度變化

早高峰時段：取ω1=0.8、ω2=0.2。

經最優化得到結果是：t=16.32 min，minf=5 325.67 min，即總等待時間為5 325.67，客座率如圖2所示。

圖2 早高峰時段客座率

午高峰時段：取ω1=0.2、ω2=0.8。

經最優化得到結果是：t=9.87 min，minf=2 955.62 min，即總等待時間為2 955.62，客座率如圖3所示。

圖3 午高峰時段客座率

晚高峰時段：取ω1=0.5、ω2=0.5。

經最優化得到結果是：t=9.76 min，minf=3 145.48 min，即總等待時間為3 145.48，客座率如圖4所示。

圖4 晚高峰時段客座率

以上分別為早高峰、午高峰、晚高峰3個不同時段取不同的權重因子所得結果，并得到各時段下的最佳適應度變化及客座率，平均迭代次數100次左右，與同條件下的遺傳算法進行對比，無論從收斂效果還是穩定性能，均具備很高的收斂性和穩定性；不同權重下的運算時間均小于30 s，能夠滿足列車行車間隔優化方案的需要。表2為不同高峰時段在不同權重系數下得到的列車行車間隔、列車的客座率及列車和旅客的總等待時間。

表2 不同高峰時段和權重對應列車的行車間隔及客座率

由仿真結果來看，權重因子對優化結果的影響很大。實際運用當中，決策者可針對不同時段的客流特性以及對各目標權重的側重傾向，結合各目標的總消耗費用制定出更科學合理的列車行車間隔。

5 結語

本文依據不同時段的客流分布特性，運用隨機理論建立了兼顧軌道交通運營企業和旅客雙方利益的列車行車間隔優化模型，針對基本人工蜂群算法的不足，提出基于改進的ABC算法對模型進行優化。仿真結果表明本文提出的基于ABC優化算法的列車行車間隔優化策略，是一種解決行車間隔優化問題的有效方法，為城際列車行車間隔優化提供了很好的參考。實際列車開行過程中，有很多不確定及不可預測因素，在具體規劃和設計列車開行方案過程中，應采取定性分析與定量分析相結合的方式，盡可能與實際情況相符合。

[12] 廖勇.公交化城際列車開行間隔優化[J].鐵道學報,2010,32(1):8-12.(LIAO Y. The headway optimization of intercity trains of mass transit type [J]. Journal of the China Railway Society, 2010, 32(1): 8-12.)

[13] ZHU G, KWONG S. Gbest-guided artificial bee colony algorithm for numerical function optimization [J]. Applied Mathematics and Computation, 2010, 217(7): 3166-3173.

[14] BAO L, ZENG J C. Comparison and analysis of the selection mechanism in the artificial bee colony algorithm [C]// HIS ’09: Proceedings of the 2009 9th International Conference on Hybrid Intelligent Systems. Washington, DC: IEEE Computer Society, 2009, 1: 411-416.

[15] 鄭鵬杰.彈性需求條件下城際鐵路時段定價問題研究[D].蘭州:蘭州交通大學,2015:43-44. (ZHENG P J. Research on inter-city rail time pricing under elastic demand [D]. Lanzhou: Lanzhou Jiaotong University, 2015: 43-44.)