基于公共交通的高精度时空可达模型与算法①

董绍轩, 张 彤



基于公共交通的高精度时空可达模型与算法①

董绍轩, 张 彤

(武汉大学测绘遥感信息工程国家重点实验室, 武汉 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]