基于在途時間的快慢車停站方案優(yōu)化算法

丁小兵 徐行方

(1.上海工程技術(shù)大學城市軌道交通學院，201620，上海；2.同濟大學道路與交通工程教育部重點實驗室,201804,上海 ∥第一作者，講師)

?

基于在途時間的快慢車停站方案優(yōu)化算法

丁小兵1徐行方2

(1.上海工程技術(shù)大學城市軌道交通學院，201620，上海；2.同濟大學道路與交通工程教育部重點實驗室,201804,上海 ∥第一作者，講師)

地鐵開行快慢車是國內(nèi)近幾年的新探索,而其停站方案的不同會影響地鐵的服務(wù)水平高低及企業(yè)運輸成本等。首先確定車站重要度評價指標體系,對指標逐一打分形成評價指標矩陣,運用層次分析法評價沿線車站的重要度,并據(jù)此確定停站權(quán)重；然后將停站權(quán)重作為停站優(yōu)化方案建模的重要參數(shù),再構(gòu)建基于啟發(fā)式蟻群算法的MATLAB程序,對快慢車停站方案優(yōu)化模型求解,得出優(yōu)化停車方案；最后,以上海軌道交通16號線為例,設(shè)計相關(guān)調(diào)查問卷獲取數(shù)據(jù)對優(yōu)化算法進行求解,并與目前停站方案作對比分析。通過該優(yōu)化算法可以縮短乘客出行時間,提升地鐵服務(wù)水平,同時為運營管理部門制定行車方案提供決策支持。

地鐵；快慢車模式; 蟻群算法; 行車方案； 在途時間

First-author′s address School of Urban Rail Transportation, Shanghai University of Engineering Science,201620,Shanghai,China

隨著中國城市化進程的不斷推進,中心城與郊區(qū)、衛(wèi)星城鎮(zhèn)之間的客流量日益增大。軌道交通郊區(qū)線路早晚高峰潮汐客流特征明顯,其客流時空分布不均衡,且主要集中在部分車站,其非高峰時段列車載客率低。故若仍然實行站站停方案,必將降低運營效率,從而對乘客出行時間和企業(yè)運輸成本造成一定的浪費。研究與沿線客流出行特征相吻合的快慢車停站方案,有利于解決由于早晚高峰客流大而造成的列車運能不匹配、車廂擁堵、列車客流分布不均衡、社會對地鐵的投訴率增加等問題。是軌道交通郊區(qū)線路開行快慢車模式必須解決的問題。

近幾年,國內(nèi)已經(jīng)開展了軌道交通快慢車行車組織方面的研究,文獻[1]研究了基于彈性需求的軌道交通列車開行方案,主要從乘客的廣義出行費用上入手,構(gòu)造乘客出行彈性需求函數(shù),運用模擬退火算法優(yōu)化列車的行車方案,而且，其開行方案中包含了零散的停站方案的研究。這為本文的研究思路指明方向,奠定了研究基礎(chǔ)。文獻[2]研究了在城市軌道交通的非高峰時期的客流特點,建立了以企業(yè)利益和出行者效益最大化的多目標決策模型。文獻[3]研究了區(qū)域城際鐵路開行方案,建立了站間距計算模型,為系統(tǒng)研究區(qū)域城際快速鐵路開行方案提供了理論依據(jù)。

本文從乘客總在途時間出發(fā)研究軌道交通快慢車停站方案的優(yōu)化問題,構(gòu)建以乘客總在途時間最小為目標的優(yōu)化模型，結(jié)合上海軌道交通16號線進行仿真驗證,以實現(xiàn)運營企業(yè)經(jīng)濟效益最大化、乘客出行總時間最小化,從而提高軌道交通的服務(wù)水平。

1 乘客出行時間分析

乘客出行時間由列車所有乘客的在途時間和候車時間兩部分組成[5]。開行快慢車模式,能使部分乘客的在途時間縮短,但也使部分乘客因候車時間的延長而增加總出行時間。優(yōu)化停站方案可使乘客總體出行時間減少,其目的是使在優(yōu)化方案的乘客總體出行時間相比于現(xiàn)行站站停方案下節(jié)省最多。

節(jié)省的時間為:

Δt=Δtt+Δtw

(1)

式中:

Δt——大站停模式較站站停模式(后文簡稱變化模式)乘客總出行時間變化量;

Δtt——變化模式下乘客在途旅行時間變化量;

Δtw——變化模式下乘客等待時間變化量[4-6]。

乘客出行時間通常主要受發(fā)車間隔與客流量影響,其指標量化計算式為

(2)

(3)

式中：

h——站站停模式下平均發(fā)車間隔;

hAB——大站停模式下相鄰慢車和快車的時間間隔;

hA/B——大站停模式下相鄰兩列快車或相鄰兩列慢車時間間隔,hA/B≥hAB;

tl——因停站而引起的時間損失;

Vmax——列車最高運行速度;

α——列車起動時的加速度;

β——列車制動時的減速度;

ts——停站時間。

(4)

(5)

構(gòu)建線性規(guī)劃模型為

Δtmax=Δtt+Δtw

(6)

其約束條件為

(7)

(8)

主要從軌道交通服務(wù)水平角度考慮。

(9)

i,j∈(1,2,3,…,n)

我們將2010～2016年這7年間不同飼料企業(yè)采購的不同魚粉產(chǎn)品進行感官分析、化學質(zhì)量分析的數(shù)據(jù)進行歸納整理，得到一些有意義的結(jié)果，旨在分享這些結(jié)果的同時，對魚粉產(chǎn)品的質(zhì)量評價和質(zhì)量控制進行有益的探討，供同行者參考。

在求解運算中設(shè)定每位乘客都能搭乘第1趟車,即不考慮超過車廂滿載率而滯留車站的情況[8]。

2 軌道交通車站重要度

2.1 車站重要度

從客流量、旅客出行時間、企業(yè)運營成本三個指標出發(fā)建立加權(quán)的AHP(層次分析法)模型,來綜合評價軌道交通線路沿途車站的重要度。其評價指標體系如圖1所示。

圖1 軌道交通車站重要度評價指標

2.2 節(jié)點重要度的確定

根據(jù)圖1建立軌道交通車站評價指標矩陣。矩陣的構(gòu)建方法采用傳統(tǒng)的方法:①aij>0,②aji=1/aij。并用1-9及其倒數(shù)作為標度來確定aij的值。指標體系中的指標,擬通過調(diào)查問卷的方式(抽樣調(diào)查對象為經(jīng)驗豐富的基層員工和行業(yè)專家)獲取。并通過評分確定其權(quán)重,最終確定車站重要度的一級判斷矩陣A。

將軌道交通路網(wǎng)中的車站視為復雜網(wǎng)絡(luò)中的節(jié)點,則節(jié)點i(i=1,2,…,n)的重要度計算式為:

式中:

n——節(jié)點數(shù)量；

m——選取的評價指標值；

wj——通過層次分析法評價得到的車站的停站權(quán)重；

pij——節(jié)點i的評價指標得分值,i,j=1,2,…,m。

3 快慢車停站方案優(yōu)化建模實例分析

3.1 上海軌道交通16號線運營數(shù)據(jù)

上海軌道交通16號線從龍陽路站—滴水湖站在龍陽路站與上海軌道交通2號線、7號線及磁浮列車換乘,以滿足連接遠郊臨港新城到中心城區(qū)的要求。其線路長度達58.96 km。其主要運營條件為:

(1)終端站和部分大站設(shè)站前折返雙島四線,接發(fā)車間隔時間應(yīng)至少滿足60 s要求。

(2)列車采用A型車,定員216人/輛(站立標準4人/m2)，最高運行速度為120 km/h。

(3)近期快車采用3節(jié)編組,慢車6節(jié)編組,短期可用列車數(shù)不設(shè)上限。

(4)現(xiàn)行停站方案快慢車全程運行時間和旅行速度如表1所示。

表1 快車、普快、慢車運行信息

3.2 客流數(shù)據(jù)

上海軌道交通16號線開通后,通過AFC(自動售檢票)系統(tǒng)數(shù)據(jù)可得出開通后初期的早晚高峰時段沿線60 min進站客流量。其具有明顯的地域影響,與車站所在的位置、周邊的商場、社區(qū)，以及與其他交通方式的銜接等緊密相關(guān)。高峰客流分布如表2所示。

表2 上海軌道交通16號沿線車站早晚高峰進站客流量

3.3 車站重要度計算

相應(yīng)的權(quán)重分別為W1=(0.50,0.13,0.37),W2=(0.11,0.64,0.25),W3=(0.22,0.61,0.17)。通過對判斷矩陣和指標權(quán)重的計算,得出判斷矩陣的偏離一致性CI。如CI值小于標準參數(shù)0.12,則表明判斷矩陣具有滿意的一致性,各級指標計算可靠。

將軌道交通線路中的車站視為復雜網(wǎng)絡(luò)中的節(jié)點,則節(jié)點i(i=1,2,…,n)的重要度為

分別計算出上海軌道交通16號線各車站節(jié)點重要度結(jié)果如表3所示。

表3 上海軌道交通16號線各車站節(jié)點重要度

3.4 行車方案優(yōu)化模型構(gòu)建

3.4.1 數(shù)據(jù)獲取

通過問卷實地調(diào)查和網(wǎng)上調(diào)查,獲取軌道交通沿線車站乘客的出行情況,獲得乘客出行的OD出行情況、出行的時段、周出行次數(shù)及出行總時長等參數(shù),如表4所示。

3.4.2 模型的構(gòu)建

計算出沿線車站節(jié)點重要度后,需構(gòu)建多目標優(yōu)化模型,才能得出最優(yōu)的行車方案。設(shè)上海軌道交通16號線模型為N=(S,E),具有n個車站、m個區(qū)段。其中，S為車站的集合,S={S(1),S(2)…S(n)};E為運行區(qū)段集合,E={e(1),e(2)…e(3)};Sr為列車r的停站集合。建立基于行車方案的多目標優(yōu)化模型,其多目標函數(shù)主要包括以下4個方面。

表4 上海16號線軌道交通客流時段分布

(1) 快慢車停站次數(shù)目標函數(shù)為:

(10)

式中:

yr,a,b——車站a到車站b乘坐列車r的客流量；

nr,a,b——列車r通過車站a到車站b的停站次數(shù)；

wk——車站的重要度系數(shù),其值由上述模型計算而得。

(2) 乘客乘坐快慢車在途節(jié)省時間Δt值最優(yōu)按式(6)為:

Δtmax=tt+Δtw

(11)

計算時間所需的客流量數(shù)據(jù)由軌道交通AFC閘機獲得。

(3) 上海軌道交通16號線運營費用最小化目標函數(shù)為:

(12)

式中:

xr——列車r的開行對數(shù);

de——區(qū)段e的里程。

(4) 上海軌道交通16號線開行對數(shù)目標函數(shù)為

(13)

根據(jù)上海軌道交通16號線采用的快慢車實際情況建立如下4個約束條件:

(3)xr≥m(r);xr≤n(r),m(r)為列車最小開行對數(shù),n(r)為最大的開行對數(shù),xr為整數(shù)。

(4) 式(11)的約束條件由式(7)～(9)確定。

3.5 模型求解

根據(jù)車站重要度分析,建立上海軌道交通16號線基于客流、旅行時間、企業(yè)運營成本的多目標模型。其中，列車采用3節(jié)A型列車編組,定員216個座位,其滿載率上限為250人(超員15.7%)。超載時按7～9人/m2計算，最小發(fā)車間隔為4 min。運用蟻群算法多次迭代搜尋最優(yōu)解時，首先初始化信息,設(shè)集合C為所有的線路車站集合;CG(min)為每次蟻群尋優(yōu)的最優(yōu)值;CA(min)為目標最優(yōu)值。則蟻群算法求解步驟為:

(1) 蟻群和路徑初始化。將M只螞蟻放置于上海軌道交通16號線的沿線車站，并將螞蟻視為計算中心; 設(shè)初始時間t= 0,且所有配送路徑上的初始信息和信息素之和都為零。

(2) 設(shè)蟻群的禁忌表索引號為1，將所有螞蟻出發(fā)后訪問的第一個停站編號放入其相對應(yīng)的禁忌列表中。

(3) 循環(huán)次數(shù)增加1。

(4) 蟻群個體根據(jù)狀態(tài)轉(zhuǎn)移概率來選擇下一步該到達的停站編號。

(5) 修改禁忌表的索引號,將選擇好之后的螞蟻移到新的編號上,并將該編號插入到禁忌表中。

(6) 如集合C中所有的編號沒有遍歷完,則跳到步驟(4)繼續(xù),否則停止運算。

(7) 如果一個螞蟻找到了終點站點,則計算該只螞蟻的總路徑費用(出行時間),同時更新當前得到的最小費用路徑,記錄此時最小費用線路所對應(yīng)值,并更新路徑上的信息素的濃度。

(8) 計算每一條路徑上的信息量。

(9) 若沒有達到最大循環(huán)次數(shù),則清空所有禁忌表,并跳轉(zhuǎn)至步驟(1)；否則跳轉(zhuǎn)至步驟(7)。

(10) 對已找到的最小費用(出行時間)停站方案更新,并記下最小費用值,如果CG(min)與CA(min)之間的差小于預先設(shè)定的值,則得到最小費用線路，并終止整個程序的執(zhí)行;否則轉(zhuǎn)至步驟(3),繼續(xù)執(zhí)行。

運用MATLAB對上述蟻群算法求解,其主要計算代碼如附錄1所示,迭代過程示意圖如圖2所示。通過MATLAB算法對構(gòu)建的最優(yōu)化模型進行計算,最終得出開行方案的停站方案如圖3所示,相應(yīng)的停站時間如表5所示。

圖2 迭代次數(shù)與時間變化量示意圖

表5 上海軌道交通16號線不同停站方案的停站時間

圖3 上海軌道交通16號線停站優(yōu)化方案示意圖

3.6 優(yōu)化結(jié)果分析

根據(jù)上海軌道交通16號線現(xiàn)行列車運行圖(如圖4所示),大站車停靠惠南站和新場站。在該運行方案開通運營后一個月里,多次乘客反映大站停站設(shè)置不合理,在臨港大道站和書院站上班的市民很不方便。這也與網(wǎng)絡(luò)調(diào)查結(jié)果吻合。在大站停模式下,列車僅?？績烧?旅客出行時間約37 min 34 s;而站站停方案全程耗時約48 min,其中,慢車在越行站等待時間約3 min,乘客普遍反映不能接受。運營管理方也一直在尋找解決方案。

圖4 上海軌道交通16號線列車運行圖

在優(yōu)化模型計算出的停站方案下,大站車?？啃聢稣?、惠南站及書院站等3站,全程運行時間為32 min 51 s,停站時間也作了相應(yīng)改進和調(diào)整。與現(xiàn)采用的停站方案相比,列車雖多?？?個車站,全程仍節(jié)省了4 min 43 s,不僅縮短了乘客在途時間,而且增加了書院站的客流吸引力,提升了軌道交通對外服務(wù)水平。若再優(yōu)化大站車與慢車的開行比例和越行站的位置,則該方案優(yōu)勢更明顯。

4 結(jié)語

軌道交通快慢車共線組合運行在國內(nèi)探索尚不多,其行車方案參多照高鐵的開行方案。如何有針對性的摸索出適合軌道交通的快慢車的方案還需作深入探究。本文從軌道交通停站方案的影響因素出發(fā),建立基于多目標優(yōu)化模型,運用啟發(fā)式蟻群算法構(gòu)建MATLAB程序,搜索最優(yōu)解,在保證乘客目的地可達性的基礎(chǔ)上(即合適的停站方案),縮短乘客總出行時間,提升地鐵服務(wù)水平。最后結(jié)合上海軌道交通16號線進行實例分析,得出的優(yōu)化方案具有實踐指導意義。啟發(fā)式蟻群算法的計算效率和精確度是今后的研究重點,結(jié)合考慮快慢車停站方案的更多影響因素,可使得優(yōu)化方案更好地服務(wù)于乘客。

[1] 鄧連波,曾強.基于彈性需求的城市軌道交通列車開行方案研究[J].鐵道學報,2012,34 (12):16.

[2] 孫鵬,丁宏飛.城市軌道交通非高峰期開行方案建模與求解[J].計算機工程與應(yīng)用,2012(28):26.

[3] 高麟.我國發(fā)展區(qū)域城際快速鐵路的相關(guān)研究[D].成都:西南交通大學,2003.

[4] 徐瑞華,潘寒川.市域軌道交通快慢車組合運營的通行能力研究[J].城市軌道交通研究,2009(10):48.

[5] MUNDER S,GAVRILA D.An experimental study on pedestrian classification[J].IEEE Trans,2006,28(11):1863.

[6] 聶磊,郭富娥.計算機編制高速鐵路列車運行圖的研究[J].中國鐵道科學,1997,18(1):101.

[7] 徐行方,忻鐵朕.城際列車的概念及其開行條件[J].同濟大學學報(自然科學版),2003,31 (4):432.

[8] CHEN H,YAO X.Multi-objective neural network ensembles based on regularized negative correlation learning[J].IEEE Trans,2010,22(12):1738.

[9] DAM H, ABBASS H.Neural-based learning classifier systems[J].IEEE Trans,2008,20(1):26.

[10] 陳曉峰.上海軌道交通16號線快慢車運行方案研究[J].城市軌道交通研究，2014(5):68.

Optimization Algorithm of Fast/Slow Train Stop Scheme Based on Passenger Travel Time

DING Xiaobing, XU Xingfang

Since the quality of urban rail stop schemes will influence the business cost and service level, the operation of fast/slow stop scheme becomes a new research topic in China. An evaluation index system of importance degree is firstly established, and AHP is used to evaluate the importance degree of stations along the line from the influencing factors over traffic organization plan; then based on MATLAB in ant colony algorithm, the best stopping solution and interval from both the operators and passengers are studied to maximize the economic benefits of enterprises. Finally, taking Shanghai rail transit Line 16 as an example, a questionnaire is designed to collect data for modeling and solution of the optimization algorithm. Through optimization Algorithm, the cost could be saved, the service level be improved with a certain value to support the decision-making for urban rail transit operation.

metro; fast/slow operation model; ant colony algorithm; operation scheme; travel time

U 292

10.16037/j.1007-869x.2016.06.011

2014-12-02)