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

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

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

0 引言

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

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

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

1 客流特性描述及相關(guān)定義

本文視旅客到達(dá)車站(始發(fā)站)的過程為隨機(jī)過程[8]，設(shè)一定時(shí)間段內(nèi)到達(dá)車站的旅客人數(shù)N(t)是一隨機(jī)變量，假設(shè)旅客均為獨(dú)立個(gè)體，其到達(dá)過程與其他旅客不相關(guān)；同一時(shí)段內(nèi)列車的行車間隔保持不變，單位時(shí)間內(nèi)期望到達(dá)車站旅客人數(shù)不變，具備如下性質(zhì)：

1)互不重疊的時(shí)間段內(nèi)，旅客到達(dá)人數(shù)是相互獨(dú)立，即旅客到達(dá)車站的時(shí)間互不相關(guān)；

2)某一時(shí)段，即對(duì)充分小的Δt，在時(shí)間區(qū)間(t+Δt)內(nèi)單個(gè)旅客到達(dá)車站的概率與t無關(guān)，與區(qū)間長度Δt成正比；

3)對(duì)于充分小的Δt，在時(shí)間區(qū)間(t,t+Δt)內(nèi)有多位旅客到達(dá)車站的概率極小，可忽略不計(jì)。根據(jù)以上性質(zhì)，可證明在[0,t]時(shí)間內(nèi)到達(dá)n位旅客的概率：

(1)

即旅客到達(dá)車站服從泊松分布，旅客的到達(dá)是一個(gè)泊松過程，其數(shù)學(xué)期望[8]：

E[N(t)]=λt

(2)

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

(3)

(4)

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

(5)

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

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

(6)

引理2 設(shè){N(t),t≥0}是強(qiáng)度為λ的泊松過程，對(duì)?實(shí)數(shù)t>0，N(t)=n>0的條件下，n個(gè)發(fā)生時(shí)刻(σ1,σ2,…,σn)與對(duì)應(yīng)于n個(gè)[0,t]上與均勻分布且相互獨(dú)立的隨機(jī)變量順序統(tǒng)計(jì)量具有相同分布[8]。

2 人工蜂群算法基本原理

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

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

(7)

(8)

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

(9)

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

(10)

4)偵查蜂階段。若對(duì)蜜源i使用式(8)搜索失敗，也即采蜜蜂搜索次數(shù)(蜜源停留)max(trial)超過限定次數(shù)Limit，仍未找到更高適應(yīng)度的蜜源，則說明蜜源被放棄，對(duì)應(yīng)采蜜蜂轉(zhuǎn)變?yōu)閭刹榉?，通過式(7)隨機(jī)選擇一個(gè)新蜜源代替原蜜源。

3 模型建立

3.1 模型假設(shè)

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

1)旅客服從”先到先服務(wù)”原則，即先到達(dá)車站的旅客先上車，且旅客進(jìn)站的過程是隨機(jī)的，在每個(gè)時(shí)段內(nèi)服從不同強(qiáng)度的均勻分布。

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

3)運(yùn)營企業(yè)利益僅考慮列車出發(fā)前所能到達(dá)列車上的旅客數(shù)量(客座率)，旅客利益僅考慮旅客候車總時(shí)間的平均值。

4)限定線路上的列車型號(hào)統(tǒng)一，列車的座位數(shù)和最大容量為一定值，列車中途不停站。

3.2 旅客候車時(shí)間模型

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

(11)

欲求旅客候車時(shí)間最少，即求：

(12)

由引理1、引理2知：

(13)

因此旅客等待時(shí)間總和的數(shù)學(xué)期望：

(14)

于是：

(15)

最終旅客候車時(shí)間最小的數(shù)學(xué)模型

(16)

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

3.3 列車等候時(shí)間模型

假設(shè)旅客數(shù)達(dá)到n時(shí)列車便發(fā)車，也即列車等待的時(shí)間為第n位旅客到達(dá)時(shí)的數(shù)學(xué)期望[10-12]：

(17)

欲求列車等候時(shí)間最大，即求：

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

(18)

求解過程:

其中：

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

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

(19)

最終列車等候時(shí)間最大的數(shù)學(xué)模型：

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

(20)

3.4 目標(biāo)函數(shù)

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

(21)

可以看出這兩個(gè)目標(biāo)函數(shù)的優(yōu)化方向是相悖的，于是引入權(quán)重系數(shù)，設(shè)置目標(biāo)函數(shù)中兩項(xiàng)成本的加權(quán)系數(shù)值，最終的目標(biāo)函數(shù)表示為：

(22)

其中：ω1、ω2為目標(biāo)函數(shù)權(quán)重系數(shù)，ω1表示運(yùn)營企業(yè)成本加權(quán)比例；ω2表示旅客等待時(shí)間加權(quán)比例；0<ω1,ω2<1且ω1+ω2=1。

3.5 約束條件

對(duì)于單式線路列車行車間隔優(yōu)化的目標(biāo)函數(shù)需滿足以下3個(gè)約束條件：

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

Δtmin≤t≤Δtmax

(23)

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

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

Fσn≥A

(24)

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

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

為確保列車發(fā)車間隔的連續(xù)性，對(duì)相鄰兩列車的行車間隔之差進(jìn)行一定范圍的限制：

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

(25)

其中δ表示相鄰時(shí)段發(fā)車間隔之差的極限。

4 基于ABC算法的列車開行間隔優(yōu)化

4.1 ABC算法的改進(jìn)

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

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

(26)

其中

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

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

(27)

其中

其中α表示自適應(yīng)參數(shù)。

4.2 ABC算法求解過程

1)初始化。初始時(shí)刻所有蜜蜂均為偵查蜂，設(shè)置種群大小NP，最大迭代次數(shù)Max_cycle，循環(huán)限定次數(shù)Limit，權(quán)重因子ωmax、ωmin，隨機(jī)產(chǎn)生NP個(gè)可能的行車間隔(行車間隔即待優(yōu)化值)。

2)初始適應(yīng)度值計(jì)算。根據(jù)初始適應(yīng)度值的大小，將蜜蜂分為采蜜蜂和觀察蜂2種，設(shè)定并記錄采蜜蜂搜索次數(shù)(依據(jù)行車間隔計(jì)算對(duì)應(yīng)目標(biāo)函數(shù)值)。

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

4)終止條件判斷。如果達(dá)到終止條件，獲得最優(yōu)解，則停止迭代，結(jié)束程序。本文采用最大迭代次數(shù)作為終止條件。

5)結(jié)果記錄。迭代結(jié)束后對(duì)于所有行車間隔對(duì)應(yīng)的成本(總等待時(shí)間)，取最優(yōu)值即最小成本，并記錄對(duì)應(yīng)的行車間隔t。

4.3 算例分析

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

表1 京津城際鐵路不同時(shí)段客流基礎(chǔ)數(shù)據(jù)劃分

由于平峰時(shí)段旅客強(qiáng)度對(duì)列車影響較小，這里不作分析，僅對(duì)高峰時(shí)段客流強(qiáng)度與列車的開行間隔進(jìn)行分析，不同時(shí)段旅客平均到達(dá)強(qiáng)度λ與列車的行車間隔t存在：

λ=λ(t)

(28)

對(duì)應(yīng)早高峰、午高峰和晚高峰時(shí)段，有：

(29)

于是得到列車行車間隔優(yōu)化模型為：

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

(30)

s.t.

(31)

其中k=0,1,…。

4.4 模型求解

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

圖1 種群最好適應(yīng)度變化

早高峰時(shí)段：取ω1=0.8、ω2=0.2。

經(jīng)最優(yōu)化得到結(jié)果是：t=16.32 min，minf=5 325.67 min，即總等待時(shí)間為5 325.67，客座率如圖2所示。

圖2 早高峰時(shí)段客座率

午高峰時(shí)段：取ω1=0.2、ω2=0.8。

經(jīng)最優(yōu)化得到結(jié)果是：t=9.87 min，minf=2 955.62 min，即總等待時(shí)間為2 955.62，客座率如圖3所示。

圖3 午高峰時(shí)段客座率

晚高峰時(shí)段：取ω1=0.5、ω2=0.5。

經(jīng)最優(yōu)化得到結(jié)果是：t=9.76 min，minf=3 145.48 min，即總等待時(shí)間為3 145.48，客座率如圖4所示。

圖4 晚高峰時(shí)段客座率

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

表2 不同高峰時(shí)段和權(quán)重對(duì)應(yīng)列車的行車間隔及客座率

由仿真結(jié)果來看，權(quán)重因子對(duì)優(yōu)化結(jié)果的影響很大。實(shí)際運(yùn)用當(dāng)中，決策者可針對(duì)不同時(shí)段的客流特性以及對(duì)各目標(biāo)權(quán)重的側(cè)重傾向，結(jié)合各目標(biāo)的總消耗費(fèi)用制定出更科學(xué)合理的列車行車間隔。

5 結(jié)語

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

[12] 廖勇.公交化城際列車開行間隔優(yōu)化[J].鐵道學(xué)報(bào),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] 鄭鵬杰.彈性需求條件下城際鐵路時(shí)段定價(jià)問題研究[D].蘭州:蘭州交通大學(xué),2015:43-44. (ZHENG P J. Research on inter-city rail time pricing under elastic demand [D]. Lanzhou: Lanzhou Jiaotong University, 2015: 43-44.)