基于在途時間的快慢車停站方案優化算法

丁小兵 徐行方

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

?

基于在途時間的快慢車停站方案優化算法

丁小兵1徐行方2

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

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

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

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

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

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

本文從乘客總在途時間出發研究軌道交通快慢車停站方案的優化問題,構建以乘客總在途時間最小為目標的優化模型，結合上海軌道交通16號線進行仿真驗證,以實現運營企業經濟效益最大化、乘客出行總時間最小化,從而提高軌道交通的服務水平。

1 乘客出行時間分析

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

節省的時間為:

Δt=Δtt+Δtw

(1)

式中:

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

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

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

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

(2)

(3)

式中：

h——站站停模式下平均發車間隔;

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

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

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

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

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

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

ts——停站時間。

(4)

(5)

構建線性規劃模型為

Δtmax=Δtt+Δtw

(6)

其約束條件為

(7)

(8)

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

(9)

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

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

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

2 軌道交通車站重要度

2.1 車站重要度

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

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

2.2 節點重要度的確定

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

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

式中:

n——節點數量；

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

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

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

3 快慢車停站方案優化建模實例分析

3.1 上海軌道交通16號線運營數據

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

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

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

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

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

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

3.2 客流數據

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

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

3.3 車站重要度計算

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

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

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

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

3.4 行車方案優化模型構建

3.4.1 數據獲取

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

3.4.2 模型的構建

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

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

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

(10)

式中:

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

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

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

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

Δtmax=tt+Δtw

(11)

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

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

(12)

式中:

xr——列車r的開行對數;

de——區段e的里程。

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

(13)

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

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

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

3.5 模型求解

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

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

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

(3) 循環次數增加1。

(4) 蟻群個體根據狀態轉移概率來選擇下一步該到達的停站編號。

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

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

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

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

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

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

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

圖2 迭代次數與時間變化量示意圖

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

圖3 上海軌道交通16號線停站優化方案示意圖

3.6 優化結果分析

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

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

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

4 結語

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

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

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

[3] 高麟.我國發展區域城際快速鐵路的相關研究[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)