基于公共交通的高精度時空可達模型與算法①

董紹軒, 張 彤

?

基于公共交通的高精度時空可達模型與算法①

董紹軒, 張 彤

(武漢大學測繪遙感信息工程國家重點實驗室, 武漢 430079)

公共交通作為我國城市居民的主要出行方式, 對其可達性的研究具有非常重要的價值和意義. 然而, 由于站點位置、固定線路、時刻表等條件的限制, 使得公共交通可達性的研究具有一定的特殊性. 針對已有研究存在的可達精度不高或者無法進行大規模可達分析等問題, 基于路網、公交網絡、地鐵網絡和時刻表信息建立高精度時空網絡模型, 設計時間依賴條件下樞紐站點和A*算法相結合的快速公交換乘算法. 以武漢市為例, 對其進行大規模高精度時空可達分析, 證明了模型的可靠性和算法的高效性.

公共交通; 時空可達; 模型; 算法; 時間依賴

可達性是交通系統中最重要的評價標準之一, 提供可達服務無疑是城市交通系統的一個重要功能. 所以, 公共交通可達性強弱的研究對于評價和改善現有公共交通服務, 為交通規劃及個體行程安排提供決策支持具有非常重要的作用[1].

目前關于公共交通可達性的研究相對較少, 已有的研究仍有許多需要改進的地方, 如沒有行程時間計算不準確[2], 沒有考慮多模態和上下車點問題, 忽略時間限制等, 這些都導致可達精度受到影響, 而考慮到可達精度的又無法進行大規模可達分析.

本文在同時考慮步行、公交和地鐵三種交通模式的條件下, 基于路網、公交網絡、地鐵網絡和線路時刻表信息建立高精度時空網絡模型, 設計基于樞紐站點和A*算法相結合的快速公交換乘算法. 以武漢市為例, 實現了大規模高精度時空可達分析.

1　公共交通可達

隨著交通問題的凸顯, 公共交通可達性的研究被越來越多的人所關注. 相對于其他的交通模式, 公共交通以特殊的方式影響可達性. 除了個體的時間成本和社會經濟特征, 公共交通可達還依賴于線路, 時刻表, 個體的位置和乘車時間等. 正是由于這些特殊性, 公共交通可達性的研究要比基于路網的私家車的可達性研究更加復雜.

所以, 許多學者在對公共交通可達性的研究過程中對問題進行簡化, 主要體現在三個方面:

(1) 行程時間計算粗略. Liu和Zhu[3]利用距離/平均速度來計算行程時間, O’Sullivan[4]利用Dijkstra最短路徑算法, 假設了所有路段的速度相等, 并且假設等車時間為發車間隔的一半, 而且沒有考慮行程方向導致的行程時間差異, 這些都會是行程時間計算不夠準確.

(2) 沒有考慮上下車點和多模態問題. Liu和Zhu[3]和O’Sullivan[4]假設最近站點為上車點, Tasic[5]只計算站點的可達, 并沒有具體到具體的位置. 由于站點的位置限制所以必須要考慮步行, 所以公共交通還具有多模態的特征. 如果還存在地鐵和其他的交通模式, 就需要根據實際情況建立多模態交通網絡, 而Lei[1]及Liu、Zhu[3]等都只考慮了公交一種模式, O’Sullivan[4]同時考慮公交和地鐵但是沒有考慮步行.

(3) 沒有考慮時變導致的可達差異. 而且, 公共交通本身具有時間依賴的特征, 由于發車時間和交通狀況等因素的影響, 不同時間的可達情況不一定相同, Liu、Zhu[3]和O’Sullivan[4]均未考慮時變因素, Tribby[6]和Mavoa[7]只是分時段進行計算, 也并沒有在時間維度精細建模.

這些問題都會導致可達的計算不夠精確, 直接影響可達的分析效果. 所以, 可達的分析正朝著越來越高的時空分辨率發展[6]. 空間維上, Tribby[6]和Mavoa[7]以人口區塊(parcel-level)為研究單元分析可達, 使得步行時間計算更加準確, 可達的表達更加精細.

時間維上, Charleux[8]和Anderson[9]在時間維度上精細建模, 證明了由于等車時間的變化, 不同的出發時間會對可達造成非常大的影響. Lei[1]在在公交網絡中加入時刻表信息, 同時考慮行程方向, 體現了不同時刻和不同行程方向導致的可達差異.

但是高精度的模型計算需要消耗大量時間, 大規模的可達分析會受到一定限制. 一些學者只針對少數線路, 或者選擇較小的城市進行分析, 如Anderson[9]只分析了四條線路隨時間的可達變化, 而Lei[1]選擇了規模較小的Santa Barbara進行分析.

在此基礎上, 本文采用規則格網對研究區域進行精細劃分,考慮公交、地鐵和步行三種交通模式, 基于路網、公交網絡、地鐵網絡和線路時刻表信息建立高精度時空網絡模型, 設計時間依賴條件下樞紐站點和A*算法相結合的高效換乘算法, 算法中考慮上下車站點選擇問題, 精確計算各部分行程時間, 以武漢市為例, 實現了大規模高精度的時空可達分析.

2　可達量度設計

可達性被普遍定義為個體到達所需服務或者興趣點的難易程度[10], 常見的可達量度可以分為基于位置和基于個體兩類[11].

基于位置的可達量度最常用的包括到達最近興趣點的行程時間或者距離、從某一位置出發一定時間或者距離范圍內可達的興趣點的總數或者可達的范圍面積. 基于位置的可達量度計算簡單, 表達直觀, 但是基于位置的可達量度無法體現個體差異, 也不能體現不同時間的可達差異[12].

大多數基于個體的可達量度都是基于H?gerstrand[13]提出的時間地理框架, 具體地可以用是否可達某個興趣點、選擇哪個興趣點行程時間最短、可達位置集合興趣點的數量、活動時間長短、時間地理效用函數來量化. 但是基于個體的可達量度存在計算復雜、個體數據難以獲取、無法表達個體位置差異等缺點[14].

綜合考慮基于位置與基于個體的可達量度的優缺點, 為了精確表達所有位置的可達情況, 本文用規則格網對整個研究區域進行精細劃分. 在時空棱鏡框架內, 以每個格網中心點的個體在時間t到t的范圍內可達興趣點的最長逗留時間MAXD和最短逗留時間MIND限制條件下累計可達的興趣的累計數量CUMF為可達量度:

可達量度的計算可以轉換為最早到達與最遲出發兩個問題, 并通過分級色彩對結果進行直觀表達, 使得每個格網都能精確表達一定時間限制條件下的可達情況, 而且可以體現出不同格網之間的可達差異.

3　模型與算法

3.1高精度時空網絡模型

公共交通網絡模型一般通過圖來表示, 為了反映更加真實的可達情況, 本文中考慮公交、地鐵和步行三種交通模式, 結合公交和地鐵時刻表建立高精度時空網絡模型. 路網用來計算步行時間, 公交網絡和地鐵網絡用來計算乘車時間. 各層之間相互獨立, 又相互連接. 通過將公交站點和地鐵站點匹配到路網上, 建立路網與公交網絡和地鐵網絡的連接, 通過換乘邊將公交網絡與地鐵網絡進行連接.

為了更準確地考慮換乘的影響, 本文不僅考慮相同站點的站內換乘, 而且考慮不同站點間的換乘, 包括公交站點間換乘與地鐵和公交站點間換乘, 換乘所需時間基于路網步行進行計算.

圖1 站內換乘

圖2 站點間換乘

基于時刻表的公共交通網絡一般采用時間依賴模型或者時間擴展模型進行表達[15]. 時間擴展模型將一個站點在時刻表中的每次出發或者到站都表示為一個事件, 存儲量大, 算法運行效率低. 相對而言, 時間依賴模型每個站點只存儲一次, 邊的權重通過時間依賴函數進行計算, 實際應用更加高效[16], 所以本文選擇使用時間依賴模型.

模型中顯式考慮線路的運行方向, 因為來去兩個方向上最優的乘車方案可能不同, 行程時間也不一樣. 對于最早到達問題, 可以根據出發時間和地點使用換乘算法進行直接計算, 而對于最遲出發問題, 需要建立反向圖, 從終止時間進行反推來進行計算[1].

圖3 行程時間計算示意圖

如圖3所示, 個體從s點出發, 步行至A站點上車, B站點下車后在C站點換乘, D站點下車后在E點換乘地鐵, 在地鐵站F下車后步行至終點t. 行程時間包括步行時間、等車時間和乘車時間三部分, 步行時間包括s->A、F->t、B->C和D->E的換乘步行時間, 等車時間包括在站點A、C、E等車的時間, 根據時刻表進行推算, 例如, 乘客11:00到達站點A, 線路L最近一趟車到達站點A的時間為11:20, 則選擇線路L的等車時間為20分鐘, 乘車時間根據每條邊的時間依賴函數進行計算[15].

3.2 換乘算法

大規模高精度時空可達分析需要高效率的公共交通換乘算法, 交通中主流的最短路徑算法都是基于Dijkstra及其改進算法[17]. Dijkstra的加速主要通過減小搜索空間或者在數據預處理階段對最短路徑進行壓縮存儲.

基于時間依賴的Dijkstra加速算法通過預處理階段的結果存儲進行加速比較困難, 所以本文基于樞紐站點和A*算法相結合, 通過減小搜索空間來設計時間依賴條件下的快速公交換乘算法. 以最短行程時間作為單一目標進行搜索, 潛在時間下界通過當前站點到終點的歐式距離/最大路網速度求得.

(1) 樞紐站點

圖4 樞紐站點示意圖

如圖4, 有三條線路L1(A->C->D->E->F->G)、L2(B->C->D->E->F->H)、L3(I->F->G), 如果要從B站點到G站點, 中間C、D、E、F都有可能是換乘站點, 但是沒有特殊原因, 我們不會選擇在D點和E點, 而會在C點或者F點進行換乘. 對于C點和F點, 我們成為樞紐站點, D點和E點稱為非樞紐站點. 實際上, 以武漢市為例, 只有1/3的站點為樞紐站點, 樞紐站點的考慮不僅會大大加快計算速度, 而且會減少不合理的換乘搜索.

樞紐站點定義: (,)表示網絡圖中的一條有向邊,S表示從站點出發的所有線路集合,S表示從站點出發的所有線路集合, 如果SS, 則點為樞紐站點.

將樞紐站點單獨建立樞紐站點層進行分層存儲, 非樞紐站點存儲前向樞紐站點H(), 后向樞紐站點L(), 對于起始站點, 終止站點, 如果、都是樞紐站點, 我們只需要在樞紐站點層進行搜索;是非樞紐, 先計算站點到H()的行程時間, 再計算H()到L()的行程時間, 最后計算L()到終點的行程時間.

(2) 上下車站點

假設公交站點A與地鐵站點B都位于出發點附近, 但是A距離更近, 而事實上去終點乘坐地鐵時間最短, 所以我們需要在算法中考慮所有潛在的上下車站點.

本文通過設置上下車點的步行時間限制, 在數據預處理階段先計算得到的潛在上車點集(),的下車點集(), 在A*搜索開始時, 將潛在上車點集()全部放入優先隊列, 直至取出()中的站點結束.

(3) 算法改善

A*算法用label-setting的方式進行搜索, 為減少不必要搜索, 當從優先隊列中取出站點時, 確定選擇乘坐線路l到達, 如果線路l經過下一條邊(,), 則要到達不考慮換乘其他線路.

4　實驗

為了檢驗模型的分析效果, 我們用C++語言開發了一個桌面端可達分析工具. 以武漢市為例, 通過設置不同的限制條件來分析公共交通可達的變化情況.

目前武漢市共有同名公交站點2400個, 公交線路625條, 武漢地鐵已投入運營1號線、2號線和4號線, 共75座車站, 全程95.6公里, 如圖5和圖6所示.

城市綜合體融合了商業零售、酒店餐飲、公寓住宅、綜合娛樂等城市功能為一體, 在城市居民生活中扮演著非常重要的角色. 所以, 本文選取全市范圍內16個城市綜合體作為可達興趣點.

圖5 武漢市公交網絡圖

圖6 武漢市地鐵線路圖

4.1數據預處理

(1) 格網劃分

為了在空間上精細建模, 并且反映研究區域的整體可達情況, 本文采用200m*200m的規則格網對武漢市主城區進行精細劃分, 用格網中心點的可達來代表所在格網的可達, 去除水系后一共有5953個格網.

圖7 格網剖分效果圖

(2) 格網中心點、興趣點、站點匹配到道路

為了方便計算步行時間, 建立不同模式之間的聯系, 將格網中心點、興趣點和站點都匹配到距離路網最近的點.

(3) 建立換乘邊

利用ArcGIS網絡分析功能, 300米為換乘距離限制, 生成公交站點間與地鐵和公交站間的換乘步行邊, 并設置人的步行速度1.3米/秒, 計算兩站點間換乘步行所需時間并進行存儲.

(4) 潛在上下車站點

以5分鐘為時間限制, 同樣設置人的步行速度1.3米/秒, 利用ArcGIS網絡分析找到格網中心點和興趣點潛在的上下車站點, 計算步行時間并進行存儲.

4.2 效率分析

為驗證可達分析工具的運行效率, 本文隨機選擇1000, 2000, 3000, 4000, 5000個格網和所有格網, 在有無地鐵兩種情況下計算15:00——17:00的時間成本下每個格網的可達. 所有方案在3.1-GHz處理器和Windows7操作系統環境下計算, 運行時間如圖8所示. 可以看出, 隨著格網數量的增多, 計算時間呈線性增長, 一個格網的平均可達計算時間<0.5秒, 并且有地鐵的情況下比無地鐵的情況下計算速度要快, 說明地鐵速度比公交快的優勢使得有地鐵的情況下搜索速度更快, 同時也證明了本文所設計的可達工具具備大規模可達分析的能力.

圖8 運行時間分布圖

4.3實驗結果

根據工作日時刻表, 以MAXD為可達量度, 圖9是以17:00—19:00為時間成本條件下可達的分布情況. 可以直觀看出, 城市綜合體、地鐵站點附近格網的可達性相對較強, 而邊緣區域可達性相對較弱.

圖9 17:00——19:00 MAXD分布圖

圖10 19:00——21:00 MAXD分布圖

圖10是以19:00—21:00為時間成本條件下可達的分布情況, 對比圖9可以發現部分格網的顏色發生了變化, 說明了不同時間限制條件下的可達性確實存在一定差異. 將兩個時間成本條件下的MAXD做差后取絕對值TD, 結果分布如圖11所示, 可以發現比較偏遠的位置可達差異相對較大, 因為邊緣區域的公交線路數量相對少, 發車頻率相對較低, 所以不同時間條件下等車時間的差異可能更大.

圖11 不同時間成本下TD分布圖

圖12 有地鐵17:00——19:00 CUMF分布圖

圖13 無地鐵17:00——19:00 CUMF分布圖

為了檢驗地鐵的修建對于可達的影響, 本文采用最短活動時間為20分鐘的限制條件下累計可達機會數量CUMF作為新的可達量度. 圖12和圖13分別為有無地鐵時, 17:00——19:00的時間成本下累計可達機會數量CUMF分布圖, 可以看出非常明顯的變化, 體現出地鐵對于改善公共交通可達性具有非常重要的作用.

綜上可以看出, 本文的實驗結果與城市可達實際情況相符合, 可以滿足大規模高精度時空可達分析的需要, 而且可以靈活改變格網密度、增加或減少地鐵公交線路、使用不同POI以及設置不同時間成本進行分析.

5　結語

本文分析了已有公共交通可達性研究的一些不足, 在其基礎上進行改進完善, 建立了高精度時空網絡模型, 提出時間依賴條件下的快速公交換乘算法, 并實現對武漢市的大規模高精度時空可達分析, 證明了模型的可靠性和算法的高效性.

但是, 真實的交通狀況往往是不確定的, 行程時間具有不確定性的本質特征[18], 本文的分析結果一定程度了高估了擁堵狀態下的可達情況. Nie[19]等人基于路網的行程時間不確定性進行了一系列研究, Hannemann[20]、Keyhani[21]等研究了火車的行程時間不確定性條件下的行程規劃. Casello[22]證明和評價了公共交通中行程時間不確定性所帶來的影響. 但是公交的情況更加復雜[23], 發車頻率更高, 而且會提前發車等. 所以, 在模型和算法中加入行程時間不確定性會是今后一個很好的研究擴展.

1 Lei TL, Church RL. Mapping transit-based access: Integrating GIS, routes and schedules. International Journal of Geographical Information Science, 2010, 24(2): 283–304.

2 Benenson I, Martens K, Rofé Y, et al. Public transport versus private car GIS-based estimation of accessibility applied to the Tel Aviv metropolitan area. The Annals of Regional Science, 2011, 47(3): 499–515.

3 Liu S, Zhu X. An integrated GIS approach to accessibility analysis. Trans. in GIS, 2004, 8(1): 45–62.

4 O’Sullivan D, Morrison A, Shearer J. Using desktop GIS for the investigation of accessibility by public transport: An isochrone approach. International Journal of Geographical Information Science, 2000, 14(1): 85–104.

5 Tasic I, Zhou X, Zlatkovic M. Use of spatiotemporal constraints to quantify transit accessibility: Case study of potential transit-oriented development in west valley city, Utah. Transportation Research Record: Journal of the Transportation Research Board, 2014, (2417): 130–138.

6 Tribby CP, Zandbergen PA. High-resolution spatio-temporal modeling of public transit accessibility. Applied Geography, 2012, 34: 345–355.

7 Mavoa S, Witten K, McCreanor T, et al. GIS based destination accessibility via public transit and walking in Auckland, New Zealand. Journal of Transport Geography, 2012, 20(1): 15–22.

8 Charleux L. A modification of the time-geographic framework to support temporal flexibility in “fixed” activities. International Journal of Geographical Information Science, 2015, 29(7): 1125–1143.

9 Anderson P, Owen A, Levinson D. The time between: Continuously-defined accessibility functions for scheduled transportation systems. 92nd Annual Meeting of the Transportation Research Board. 2013.

10 Wachs M, Kumagai TG. Physical accessibility as a social indicator. Socio-Economic Planning Sciences, 1973, 7: 437–456.

11 Horner MW, Downs J. Integrating people and place: A density-based measure for assessing accessibility to opportunities. Journal of Transport and Land Use, 2014, 7(2): 23–40.

12 Neutens T, Delafontaine M, Scott DM, et al. An analysis of day-to-day variations in individual space-time accessibility. Journal of Transport Geography, 2012, 23: 81–91.

13 H?gerstraand T. What about people in regional science? Papers in Regional Science, 1970, 24(1): 7–24.

14 Delafontaine M, Neutens T, Van de Weghe N. A GIS toolkit for measuring and mapping space-time accessibility from a place-based perspective. International Journal of Geographical Information Science, 2012, 26(6): 1131–1154.

15 Müller-Hannemann M, Schulz F, Wagner D, et al. Timetable information: Models and algorithms. Algorithmic Methods for Railway Optimization. Springer Berlin Heidelberg, 2007: 67–90.

16 Antsfeld L, Walsh T. Finding optimal paths in multi-modal public transportation networks using hub nodes and TRANSIT algorithm. Artificial Intelligence and Logistics, 2012: 7.

17 Bast H, Delling D, Goldberg A, et al. Route planning in transportation networks. arXiv:1504.05140, 2015.

18 Chen BY, Lam WHK, Sumalee A, et al. Finding reliable shortest paths in road networks under uncertainty. Networks and Spatial Economics, 2013, 13(2): 123–148.

19 Nie YM, Wu X. Shortest path problem considering on-time arrival probability. Transportation Research Part B: Methodological, 2009, 43(6): 597–613.

20 Müller-Hannemann M, Schnee M. Finding all attractive train connections by multi-criteria Pareto search. Algorithmic Methods for Railway Optimization. Springer Berlin Heidelberg, 2007: 246–263.

21 Keyhani MH, Schnee M, Weihe K, et al. Reliability and delay distributions of train connections. ATMOS. 2012. 35–46.

22 Casello J, Nour A, Hellinga B. Quantifying impacts of transit reliability on user costs. Transportation Research Record: Journal of the Transportation Research Board, 2009, (2112): 136–141.

23 Keyhani MH, Schnee M, Weihe K. Path Finding Strategies in Stochastic Networks. http://tuprints.ulb.tu-darmstadt.de/ id/eprint/4302.

High-Resolution Spatio-Temporal Modeling and Algorithm of Public Transit Accessibility

DONG Shao-Xuan, ZHANG Tong

(State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China)

Public transit system plays the central role for traveling in cities of China. Therefore, it is important to study the accessibility provided by public transit. However, public transit influences accessibility in unique ways, which depends significantly on the routes, schedule, location of the users as well as the time of day the trip is made. Existing researches scarcely establish high-resolution spatio-temporal models, calculate travel time accurately, consider the time constraint, or achieve large-scale accessibility analysis. This paper establishes a high-resolution spatio-temporal model based on road network, bus network, metro network and schedule information, designs an efficient time-dependent transfer algorithm combining Hub with A* Algorithm. To demonstrate the reliability of the model and the efficiency of the algorithm, a case study is presented with respect to mapping accessibility of public transit in Wuhan.

public transit; spatio-temporal accessibility; high-resolution model; algorithm; time-dependent

國家自然科學基金(41271400);深圳市基礎研究計劃(JCYJ2014082813633980);空間信息智能感知與服務深圳市重點實驗室(深圳大學)開放基金

2016-06-22;

2016-07-25

[10.15888/j.cnki.csa.005647]