EN中文

Journal of Geo-information Science >

2015 , Vol. 17 >Issue 10: 1187 - 1195

DOI: https://doi.org/10.3724/SP.J.1047.2015.01187

Orginal Article

A New Network Voronoi Diagram Considering the OD Point Density of Taxi and Visual Analysis of OD Flow

  • XIN Rui ,
  • AI Tinghua , * ,
  • YANG Wei ,
  • FENG Tao
Expand
  • School of Resource and Environmental Sciences, Wuhan University, Wuhan 430079, China
*Corresponding author: AI Tinghua , E-mail:

Received date: 2015-04-30

  Request revised date: 2015-05-29

  Online published: 2015-10-10

Copyright

《地球信息科学学报》编辑部 所有
Fold

Abstract

It is very difficult to analyze every vehicle trajectory carefully due to the huge number of data. Therefore, it is necessary to divide the space of one city into a collection of smaller areas, among which we can analyze and exploit the vehicle trajectories. Unfortunately, the existing partitioning methods have many disadvantages which may hinder the progress of our study. For example, some traditional partitioning methods based on the Euclidean distance don’t take into account the spatial characteristics of the roads in the city, which may cause a variety of man-made rigid division. Meanwhile, some other partitioning methods ignore the density distribution of taxi’s track points. With further research on trajectory data, the use of traditional space partitioning methods has difficulty meeting the demands of spatio-temporal trajectory data analysis. As a result, we propose a new Voronoi subdivision algorithm on road network which considers the density of taxi’s OD points and the behavior characteristics of taxis. The main body of the algorithm consists following steps. First, the road network should be divided into a series of edges by their intersections. After that, the edges of the road network are subdivided into small linear units. Next, we produce n×n sized regular grids as the space constraints and choose the generating elements in every grid to make them distributing uniformly in space. Then, we can set different speed values for different generating elements and let them spread to the surrounding roads at different speed. Finally, we can get the road network partitioning results consistent with the density distribution of OD points. A series of city sub-regions can be obtained based on the result of network partitioning. Then, we can analyze the track data in these sub-regions with the help of spatio-temporal data visualization methods, such as color sorting, flow graphs, constructing graph structure, etc. At last, we developed an experimental system to generate the network Voronoi diagram, on which we verify the algorithm and analysis methods presented in this paper by testing with the real Beijing taxi trajectory data of one day. Results of these experiments showed that the information about the trajectory data can be obtained intuitively with the help of network Voronoi diagram and the use of various visualization methods for spatio-temporal data.

Key words： trajectory data; network Voronoi diagram; spatial division; spatial analysis

Cite this article

XIN Rui , AI Tinghua , YANG Wei , FENG Tao . A New Network Voronoi Diagram Considering the OD Point Density of Taxi and Visual Analysis of OD Flow[J]. Journal of Geo-information Science, 2015 , 17(10) : 1187 -1195 . DOI: 10.3724/SP.J.1047.2015.01187

1 引言

出租车在城市交通系统中承担了极其重要的运输任务,为城市的发展和居民的生活带来极大的便利。目前,许多城市的出租车安装了GPS设备,每天都会产生海量的轨迹数据,如果能对这些数据进行有效的挖掘、研究,将有助于发现出租车流动规律,深刻了解城市交通的运转,指导出行计划的制定,以及出租车司机经营方针的优化。近年来,针对出租车轨迹数据的研究引起了学术界的广泛关注,并产生了一系列的研究成果[1-5]。由于出租车轨迹数据具有海量、非结构化、时空特性,对所有的轨迹进行精细分析研究所耗费的代价是难以估量和承受的。本文以城市空间的区域为单位对出租车轨迹的OD点,以及由OD点所形成的OD流进行分析,研究出租车与区域间的流动交互情况,利用OD点及OD流所展现出的特征来探讨出租车在各区域的流动模式。
空间剖分问题（即如何进行区域的划分）是GIS中的经典问题,针对不同的研究需求,对同一片区域会有不同的剖分方案。文献[6]提出了弹性多尺度空间划分方法,首先以细粒度对整个空间平面进行等尺度划分,随后进行最邻近空间网格单元的合并最终生成空间划分子区域集合。文献[7]将研究区域划分成细小规则格网集合,以规则格网作为网络的节点,采用社区分割算法以出租车数据完成对城市区域的剖分。文献[8]提出先提取轨迹的特征点进行聚类,然后利用聚类中心点生成泰森多边形以划分空间区域。文献[9]提出借助Delaunay三角网进行OD点的聚类,而后利用聚类结果进行空间划分。文献[10]中用到2种空间划分方法：一种直接利用城市行政区来进行空间划分;另一种以OD点的空间聚类进行空间划分。文献[11]将社区作为交通分析区域（TAZ）,将各交通分析区进行合并以产生适合研究分析的区域。文献[12]针对格网数据提出一种先将临近的属性相似不规矩格网依次合并后在目标函数的约束下进行剖分的方法。
上述研究对空间的剖分方法主要有2种类型：一种利用城市现有的行政区域或社区等对空间进行剖分;另一种则是结合实验数据人为对空间区域进行剖分。然而,出租车移动行为很大程度上受道路网的约束,所以,轨迹具有明显沿道路分布的特点。而上述提及方法在内的许多传统空间剖分方法,在研究出租车行为问题时都存在以下缺陷：有的方法没有顾及空间内的道路网特征,剖分往往都基于均质的欧氏空间而忽略了车辆行为大部分发生于道路网络空间这一重要事实,剖分时对道路网络的切割具有任意性,不利于研究发生在道路上的出租车行为;另一些剖分方法没有深入考虑轨迹数据本身的类型和特点,往往导致人为分割。例如,文献[7]在探究出行模式和城市结构时,将城市区域划分为细小规则格网,然后再进行空间剖分。然而,当研究与道路密切相关的出租车行为时,由于此方法未充分顾及道路因素而不再适合。
文献[11]中交通分析区域（TAZ）通常以城市中存在的社区等作为划分子单位,有时甚至将道路作为划分边界,这样相当于对道路进行纵向切割而非横向切割,掩盖了部分道路车流的方向信息,不利于研究OD流此类与车流方向关系密切的车辆跨区域流动问题。文献[12]中提到的方法针对网格数据,有时需对原始数据进行处理,且此方法也没有考虑空间中的网络特征。对空间进行Voronoi剖分是经典的空间剖分方法,现有Voronoi空间划分方法较多采用欧氏直线距离度量,将分析区域理想化为各向同性的均质空间,忽略了空间运动所依赖的传导方式及空间差异性[13]。针对这种情况,许多学者研究基于网络的Voronoi图进行空间的划分。文献[14]和[15]介绍了网络空间Voronoi图的概念及其分类。文献[15]-[17]介绍了网络Voronoi图在选址、物流配送等方面的应用。文献[19]对比使用欧氏距离的普通Voronoi图和网络距离的网络Voronoi图确定商业零售网点市场域时的不同效果。网络Voronoi剖分在网络空间进行,借助网络的连通性通过沿网络边扩散实现区域分割,在进行路网剖分的时候以网络空间中的路径距离代替欧氏距离,能充分顾及城市空间中的道路分布情况、车辆移动行为,这对于研究分析发生于道路网络空间的车辆移动等问题十分有利。
OD流是移动轨迹在几何和语义两方面进行综合概括的结果,包含丰富的方向和位置信息,可反映城市中人、物流的动态特征,而且隐含城市中各区域的联通情况,对其进行有效地挖掘分析,有助于了解城市的动态变化。文献[9]通过研究OD流数据来挖掘运动的时空模式,文献[8]和文献[10]将轨迹数据进行化简,使之成为连接所有途经区域的有向流再对其进行可视化分析,文献[4]通过挖掘出租车轨迹OD流的语义信息探索城市内人的移动和区域特征。然而,上述OD流的生成大部分是基于欧氏空间下划分的区域,并未考虑城市中道路网的空间分布特征,因此,对于研究具有明显沿道路分布特征的出租车轨迹数据是不适合的。
本文提出了空间约束条件下顾及出租车OD点分布密度的网络Voronoi剖分,利用其剖分的结果对城市中各子区域的出租车OD流进行研究分析,并使用北京城区一天的出租车GPS数据,在北京主干道网络上进行实验,取得了满意的结果。

2 道路网的Voronoi剖分

2.1 道路网剖分概述

本文对路网进行的Voronoi剖分,将结合出租车的OD点数据进行,在道路网上选择若干合适的发生元作为扩散起点,各发生元以合适的步长沿路网向周围邻接路段进行扩散,逐渐将路网分割成若干子网络。理想的扩散结果是：OD点密集区域所对应的发生元子网络覆盖范围较小,而OD点稀疏区域所对应的发生元子网络覆盖范围较大。最终以各发生元的扩散结果作为路网剖分的结果。

2.2 路网数据的预处理

原始道路网数据中的道路长短不一,不利于对各发生元的扩散速度进行控制,需对数据进行预处理。借鉴网络图栅格化的思想,对道路网的路段进行加密剖分,以剖分后的细分基础线性单元定义网络空间中的栅格,建立网络图的栅格数据结构[20]：首先,将所有的道路交叉点设定为分割节点,通过分割节点切割道路,生成道路弧段（图1）。然后,将道路弧段细分为基础线性单元集,即网络单元栅格集（图2）,发生元扩散时的单位步长即为一个网络单元栅格。
Fig. 1 Cutting the roads by division nodes

图1 通过分割节点切割道路

道路网的边经栅格化处理后,定义3种类型的标记来描述路网栅格单元在扩散过程中的角色状态：（1）路网栅格单元的ID;（2）覆盖它的Voronoi发生元的ID;（3）标识是否已被某发生元覆盖的标记。为方便路网的剖分操作,需根据栅格单元和栅格单元的端点建立栅格单元与节点间的邻接关系,根据节点和与节点相邻的栅格单元建立节点与栅格单元间的邻接关系,从而完成边-节点和节点-边的拓扑结构建立,明确栅格单元与节点间的双向邻接关系。
Fig.2 Split the road segments into small linear units

图2 道路弧段等分为基础线性单元集

Fig. 3 Use the grid as spatial constraints

图3 使用格网进行空间约束

2.3 发生元的确定

发生元（即路网扩散的初始点）的位置,将直接影响路网剖分后各子网的相对位置,如果发生元过于聚集,会使整片区域上各子网的位置相对集中,可能导致子网的分布上产生严重的倾斜,与各子网所覆盖的OD点分布密度不相符。为了防止这种现象发生,本文在空间上设置约束条件,将整个路网覆盖的区域划分成n×n的规则格网（图3）,n的大小视研究的分辨率而定,从每个格网中确定发生元,从而让发生元的分布相对均衡（图4）。将每个格网中的OD点映射到相应的道路段上,然后,统计每条道路段上OD点的数目,选择格网中OD点最多的道路段,以此道路段的中心点作为发生元。在OD点分布稀疏的地方,可相应减少发生元的数量,即有些格网内可不设发生元。
Fig. 4 Determine the generating elements

图4 确定发生元

发生元确定后需制定发生元的扩散步长,即此发生元的扩散速度。为了达到使OD点密集区域所对应的发生元子网络覆盖范围较小,而OD点稀疏区域所对应的发生元子网络覆盖范围较大的目的。本文统计了上述建立的每个规则格网中OD点的数目,用式（1）来确定每个格网内对应发生元的扩散步长。
f x = 3 , b 1 ≤ x ≤ b 2 2 , b 2 ≤ x ≤ b 3 1 , b 3 ≤ x ≤ b 4 (1)
式中,x代表格网内的OD点数目;f(x)为格网内对应发生元的扩散步长。利用格网内部的OD点数目,使用自然间断点分级法将规则格网分为3级,得到各级格网OD点数目边界值b1、b2、b3、b4（其中,b1<b2<b3<b4）,为各级格网内的发生元设定相应步长。根据式（1）,对于拥有较多OD点的格网,其对应的发生元扩散速度较慢,反之,对于内部OD点数量较少的格网,其对应的发生元扩散速度较快。发生元位置及扩散步长确定后,就可进行发生元的扩散继而生成道路网络上的Voronoi图。
Fig. 5 Generating element spread to the surrounding area by one step

图5 发生元向四周进行一个步长的扩散

Fig. 6 Generating element spread horizontally by one step

图6 发生元水平进行一个步长的扩散

2.4 网络Voronoi图生成

网络Voronoi图的生成是发生元沿网络上的路径进行扩散的结果,其扩散的主体算法如下：
（1）发生元的初始化
对于每一个发生元,找寻距离其最近的网络单元栅格作为初始网络单元栅格,将初始单元栅格的两个端点加入对应发生元的当前点集合,并将对应发生元的ID赋给初始单元栅格作为其覆盖发生元ID。同时,将是否已被发生元覆盖属性标记改为是,从而完成发生元的初始化,所有的发生元此刻都属于活跃状态。
（2）发生元的一轮扩散
① 对于一个活跃的发生元,新建一个临时当前点集合,用发生元当前点集合中的每一个节点搜寻此节点邻接的网络单元栅格,判断搜寻到的网络单元栅格是否已有发生元覆盖。如果是,则停止该支路的扩散;如果否,则将这条单元栅格的另一个端点加入此发生元的临时当前点集合,并将对应的发生元ID写入此单元栅格的覆盖发生元ID标记中。同时,将此单元栅格的是否已被发生元覆盖标记改为是。完成当前点集合所有节点的搜寻后,如果临时当前点集合为空,说明此发生元已找不到可扩散的相邻单元栅格,则停止此发生元的扩散,即取消它的活跃状态;如果临时当前点集合不为空,则用发生元的临时当前点集合覆盖其当前点集合。
② 至此,一个发生元结束一个步长的扩散。对于扩散速度大于一个步长的活跃发生元,转向步骤① 重复进行下一个步长的扩散,直到完成所有步长的扩散,对于扩散速度等于一个步长的发生元则等待下一轮的扩散。
③ 当所有发生元完成相应步长的扩散,判断是否还存在活跃发生元,如果存在则转向步骤②,如果不存在,则算法结束,完成对道路网络的Voronoi剖分。
通过上述算法将整个道路网络剖分为一系列子道路网,继而完成对城市区域的剖分,对城市区域出租车流动模式的研究,将以这些城市子区域为对象而进行。

3 城市各区域出租车流动模式研究的相关方法

3.1 OD流的生成

对城市各区域出租车流动模式的分析挖掘工作,需基于出租车的OD流进行,OD流是由载客出租车移动起始位置指向终止位置的流线,是移动轨迹高度综合的结果。为便于研究,需使OD流包含出租车移动的区域信息。提取所有载客出租车轨迹的OD点,结合网络剖分算法所得到的区域剖分结果,将OD点根据空间位置映射到相应的区域内,这样每个OD点都获得了对应的空间区域信息,将属于同一条出租车轨迹的O点和D点所对应的区域按照移动方向进行串接,即可得到此轨迹对应的OD流,对所有载客轨迹都进行同样的处理即可完成全部OD流的提取工作。结合可视化技术及相关分析方法,可对OD流进行一系列的研究。
Fig. 7 Generating element spread vertically by two steps

图7 发生元垂直进行2个步长的扩散

3.2 OD流可视化及分析方法

3.2.1 OD流分析方法
首先将研究对象限定在网络剖分得到的单个城市区域上,对各区域内的出租车OD流进行研究分析。为了从时间和空间展开对OD流的分析,要对各区域的OD流数据按时间段进行划分,得到几个有代表性时间段的OD流集合,分时段对这些OD流数据进行分析。对于每个城市区域,结合它的空间位置和与其相关联的OD流方向信息,可统计此区域在各时段的出租车流入量Tin和流出量Tout,将这些信息可视化可大致看出各区域出租车的总体流通情况并发现各时段流入量或流出量的极值区域,观察各时段极值区域的分布,有助于研究如交通热点区域的时间变化规律等问题。借鉴文献[21]中的相关思想引入公式Tin-Tout/（Tin+Tout）和Tout-Tin/（Tin+Tout）对每个区域的流入量和流出量等参数进行综合分析,即可得到每个区域与车流量相关的综合统计信息如净流入量、净流出量等,通过地图可视化手段表现出来,可直观地发现属于出租车输入状态的区域和属于出租车输出状态的区域,不仅可为城市交通管理提供经验信息,而且通过分析区域输入输出状态随时间变化的规律,还能考察以出租车为出行方式的乘客在此区域的流动规律,从而大致推断区域的功能类型。
3.2.2 OD流可视化
城市中的各个区域并非静态孤立的,而是通过各种联通方式动态联系在一起。在各区域间穿梭的出租车的移动行为,正是区域间相互联系的一种体现。当出租车在某个区域内移动时,其OD流的起始点与终止点对应同一片区域,当对应的2个区域不同时,即表示出租车在不同区域间移动,这条OD流就代表了2个区域间的一次联通,连接2个区域的OD流数量越多,说明这2个区域间的联通性越好,即区域间联通频繁。有时候需探究区域间联系的紧密度,发现频繁联通的区域对,通常根据各区域间的车流量统计信息生成OD矩阵等统计表,然而图表统计的形式缺少地理位置上的直观表达,在信息传输的过程中很难让读者建立空间上的联系,需要借助一些可视化手段将数据所隐含的空间信息表达出来。
首先,对有联通关系的区域进行OD流数量统计,然后,选择合适的OD流可视化方法进行表达分析。在进行可视化方法选择时,需尽可能地将区域间OD流信息表达全面,通过构造流向图可达到这一目的。指定某一区域作为考察的目标区域,找寻与目标区域有车流联通关系的区域,用有向箭头表达区域间OD流的方向,用边的宽度表达区域间OD流数量。通过流向图可将从目标区域出发到达不同终点区域的车流方向和车流量同时展现出来,以此考察目标区域向其他区域的车流输出情况,也可展现从其他区域出发到达目标区域车流的方向和流量,考察其他区域向目标区域的车流输入情况。借助流向图,在挖掘与目标区域有联通关系区域的同时,还可直观地发现它们之间联通的频繁程度,推断目标区域内以出租车为出行方式乘客的主要移动方向。
3.2.3 OD流拓扑图
为宏观地考察各城市区域间的联通及联通频繁度,借鉴文献[22]引入图的思想,将各时段不同区域的车流信息映射成图的各种属性如节点大小、边的宽度,通过图中节点、边的变化反映各区域OD点数目及区域间联通度的改变,通过拓扑图的各种形态变化如收缩、扩张、变形(图8),宏观反映城市区域间车辆流动模式的改变。依据上述的路网剖分算法,根据各时段的OD点数据,可得到每个时段对应的路网剖分结果,即城市子区域集合。对于每个时段的子区域集合,提取各区域的中心点,通过这些中心点建立区域集合的拓扑图结构,用每个区域中心点的大小表示区域内OD点的数量,用连接相邻区域中心点的边的宽度表示区域间车流量的大小。借助OD流拓扑图不仅能观察各区域OD点数量的相对大小,还能发现联通频繁的邻接区域。观察不同时段图属性的变化,可直观地了解与之对应的车流信息的变化,在考察各邻接区域车流量随时间变化的同时,还可从整体上观察区域间流动模式的改变。
Fig. 8 Structural changes of the topology graph

图8 拓扑图的结构变化

4 实验与分析

4.1 算法实验

为验证本文提出的算法与分析结果,本文在P4/2G/1G/Win7环境下,采用C#编程语言开发了网络Voronoi图的生成实验系统,在此系统的支持下对北京市城区的主要道路进行了网络剖分模拟,并在路网剖分结果的基础上,进行城市子区域出租车时空流动模式的分析。
实验数据为北京城区的主道路网数据和2012年11月1日（星期四）一天的出租车轨迹数据,其中,出租车轨迹数据包括车辆标识、触发事件、运营状态、GPS时间、GPS经度、GPS纬度、GPS速度、GPS方位、GPS状态等信息。从出租车轨迹数据中提取375 000个OD点,参与网络剖分的道路网由2508条道路链组成,用3×3、4×4、6×6共3种类型的规则格网,分别作为确定网络扩散发生元位置的空间约束。图9为3种类型格网限制下路网剖分的效果图。
Fig. 9 Road network division under different constraints

图9 不同格网约束条件下的路网剖分

选取6×6规则格网约束下生成的区域剖分结果,并选择有代表性的几个时段：早晨（7:30-8:30）、中午（12:00-13:00）、下午（17:30-18:30）和晚上 （23:00-24:00）。统计每个时段内各区域出租车的总流入量Tin与总流出量Tout,分别映射成地图上各区域不同深浅的颜色。图10可直观地发现不同时段城市中出租车流入量大的区域（深红色的区域）和流入量小的区域（浅红色的区域）。图11可发现不同时段出租车流出量大的区域（深蓝色的区域）和流出量小的区域（浅蓝色的区域）。通过对时空数据综合分析,能得到各时段高流入量区域的分布变化规律或某区域流出量随时间的变化情况等一系列信息。对各时段出租车流入量和流出量数据进行联合分析,可能会发现更深层次的信息：出租车流入量大并且流出量也大的区域,可能是一个交通枢纽区域;在清晨的出租车流出量大而流入量小,在傍晚流入量大而流出量小,这可能预示该区域内有较多的居民区[23]。
Fig. 10 Taxi inflows at different time periods

图10 各时段出租车流入量

Fig. 11 Taxi outflows at different time periods

图11 各时段出租车流出量

使用公式Tin-Tout/（Tin+Tout）和Tout-Tin/（Tin+Tout）计算某一区域出租车净流入率和净流出率,并将相应的计算结果映射到地图上,研究属于出租车输入或输出状态的时段和区域。由图12各时段区域的净流入率渲染图可容易地发现净流入率大的时段和区域（深红色区域）,这些区域即属于出租车输入区域,同时也可找到属于出租车输出状态的时段和区域（深绿色区域）。通过对某一区域不同时段状态的连续观察,可发现目标区域随时间不同其输入输出状态的交替变化情况。
Fig. 12 Taxi net inflow rates at different time periods

图12 各时段出租车净流入率

指定一个城市区域作为目标区域建立流向图（图13）。通过流向图的箭头指向可标明与目标区域有联通关系的区域,通过边的宽度可反映区域间车流量的大小。从流向图中可发现,一般乘坐出租车多倾向于进行中短距离出行,而选择乘出租车进行远距离出行的乘客则较少,这与人们的日常生活经验相符。
Fig. 13 Regional flow charts

图13 区域流向图

根据各时段得到的剖分区域集合,提取每个区域的中心点,通过这些中心点建立区域集合的拓扑图结构。如图14所示,用每个区域中心点的大小表示区域内OD点的数量,用连接相邻区域中心点的边的宽度表示区域间车流量的大小。从图中可找寻那些联通频繁的邻接区域,观察不同时段流量图的变化,可从整体上发现区域间流动模式的改变。从图中可以看出,早晨7:30-8:30,图结构比较复杂,存在很多较宽的边,这预示着此时城市中出租车业务繁忙,各区域间出租车流动频繁。12:00-13:00,图结构变得比上个时段简单,即出租车的业务量有相应的减少,而图结构也发生了相应的变化,这是因为出租车OD点的聚集位置发生了变化,从而影响区域划分结果,导致了图结构形态的改变,所以从图结构的变化中可发现出租车供求热门区域的变化情况。17:30-18:30,图结构又变得复杂,宽度较大的边数量增多,各区域间的联通频繁度又达到了一个高峰。最后23:00-24:00,可明显发现图结构达到一天中最简单的状态,并且这个时段的图发生了较大的收缩,从这些现象可推断出此时城市中各区域联通度的降低和出租车业务量的减少,并且出租车业务范围收缩到了城市中心区域附近。
Fig. 14 Graphs of regional traffics at different time periods

图14 各时段区域流量图

4.2 实验结果分析

基于道路网络对空间进行的剖分与以欧氏距离对空间剖分的结果有很大的差别,由于未考虑道路分布等因素,将整个城市空间视为均质的,所以,基于欧氏距离的Voronoi图分割往往具有任意性,其分割子区域边界光滑,并且无法体现其内部OD点数目等车流信息情况。而考虑了道路分布的网络Voronoi剖分,则将城市中车辆行为等因素考虑在内,由于发生元在各路段的扩散状态不同,使得剖分子区域的边界呈现锯齿状,剖分区域的形状、大小等与其内部的车流数据信息有很强的相关性。由于规则格网的约束,各发生元分布相对均匀,达到了从城市空间中不同位置开始扩散剖分道路网的目的,从而避免了剖分结果区域分布倾斜影响后继的研究分析。不同发生元进行网络扩散所覆盖的区域范围有明显不同,实现了OD点密集处剖分子区域覆盖面积较小,而OD点稀疏处剖分子区域覆盖面积较大的理想目标。相比传统的空间剖分方法,道路网络的Voronoi剖分不仅顾及了出租车轨迹点沿道路分布的空间特征还考虑了轨迹点密度的不同分布。
网络Voronoi剖分算法,基于道路网络进行扩散计算,将扩散的最终结果作为城市空间剖分的结果。其中,需建立道路网络的栅格数据结构,确定网络栅格单元与节点间的拓扑邻接关系,并用到了索引进行相邻网络单元栅格的搜寻。算法的时间消耗主要在不同发生元对相邻的网络单元栅格的搜索上,所以,应当对道路网数据建立高效的数据结构,便于路网扩散时相邻网络单元栅格的搜索。针对同一份路网数据,当发生元的数目增多,且对道路弧段的剖分粒度更细时,算法的时间消耗会上升。因此,根据实验需求制定合适的发生元数目和使用适当的道路弧段剖分粒度,能在取得满意实验精度的同时减少算法时间。
对城市区域间出租车时空流动模式的挖掘,是道路网Voronoi剖分的一个应用,通过网络剖分得到的子区域顾及了城市中的道路特征和OD点的分布密度,对于研究城市区域的车辆流动有明显的优势。结合各种可视化分析方法,从不同的角度展示城市区域中出租车的流动情况,用以观察出租车与城市区域的交互。通过加入时间信息的表达对不同时段各区域出租车轨迹形成的OD流进行分析,从时间和空间2个方面挖掘出租车的移动信息,从而直观地发现关于出租车流动的时空动态特征。
通过算法设计与实验分析可得出以下结论：
（1）该网络空间剖分算法思想直观,这种路网扩散的算法可加入多种约束条件,从而满足不同的应用需求,如密集人群疏散、物流配送扩散等。
（2）可视化分析的加入能给轨迹数据研究带来很大的便利,多种时空可视化方法的综合运用在直观地进行数据展示的同时,能让观察者发现轨迹数据中潜在的有价值信息。

5 结语

随着各种VGI数据的日益流行,出租车轨迹数据将会被更多的人重视并加以研究利用。本文利用从出租车轨迹数据中提取的OD点和北京城区的路网数据,结合空间约束条件给出了顾及出租车OD点分布密度的网络Voronoi剖分算法,并在该算法生成结果的基础上,对城市区域的出租车OD流进行挖掘分析。本研究使用自定义的约束条件对道路网进行剖分处理,随着更多面向需求的约束条件的加入和更加丰富的数据挖掘分析方法的应用,相信会取得更多令人满意的成果,这是今后需深入研究的方向。

The authors have declared that no competing interests exist.

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
Wang Z, Yuan X.Urban trajectory timeline visualization[C]. 2014 International Conference on Big Data and Smart Computing (BIGCOMP), IEEE, 2014:13-18.

[2]
Zheng K, Zheng Y, Xie X, et al.Reducing uncertainty of low-sampling-rate trajectories[C]. 28th International Conference on Data Engineering (ICDE), IEEE, 2012:1144-1155.

[3]
Veloso M, Phithakkitnukoon S, Bento C.Urban mobility study using taxi traces[C]. Proceedings of the 2011 international workshop on Trajectory data mining and analysis, ACM, 2011:23-30.

[4]
Zhang W, Li S, Pan G.Mining the semantics of origin-destination flows using taxi traces[C]. Proceedings of the 2012 ACM Conference on Ubiquitous Computing, ACM, 2012:943-949.

[5]
张健钦,仇培元,杜明义.基于时空轨迹数据的出行特征挖掘方法[J].交通运输系统工程与信息,2014,14(6):72-78.

[6]
王亮,胡琨元,库涛,等.基于多尺度空间划分与路网建模的城市移动轨迹模式挖掘[J].自动化学报,2015,41(1):47-58.

[7]
Liu X, Gong L, Gong Y, et al.Revealing travel patterns and city structure with taxi trip data[J]. Journal of Transport Geography, 2015,43:78-90.

[8]
Andrienko N, Andrienko G.Spatial generalization and aggregation of massive movement data[J]. IEEE Transactions on Visualization and Computer Graphics, 2011,17(2):205-219.

[9]
Guo D, Zhu X, Jin H, et al.Discovering spatial patterns in origin-Destination mobility data[J]. Transactions in GIS, 2012,16(3):411-429.

[10]
Andrienko G, Andrienko N.Spatio-temporal aggregation for visual analysis of movements[C]. IEEE Symposium on Visual Analytics Science and Technology, 2008:51-58.

[11]
Yang S, Liu X, Wu Y J, et al.Can freeway traffic volume information facilitate urban accessibility assessment?: Case study of the city of St. Louis[J]. Journal of Transport Geography, 2015,44:65-75.

[12]
Guo D, Wang H.Automatic region building for spatial analysis[J]. Transactions in GIS, 2011,15(s1):29-45.

[13]
谢顺平,冯学智,鲁伟.基于道路网络分析的Voronoi 面域图构建算法[J].测绘学报,2010,39(1): 88-94.

[14]
Okabe A, Satoh T, Furuta T, et al.Generalized network Voronoi diagrams: Concepts, computational methods, and applications[J]. International Journal of Geographical Information Science, 2008,22(9):965-994.

[15]
Okabe A, Boots B, Sugihara K, et al.Spatial tessellations: concepts and applications of Voronoi diagrams[M]. Chichester, England: John Wiley & Sons, 2009.

[16]
谢顺平,冯学智,都金康.基于网络Voronoi 图启发式和群智能的最大覆盖空间优化[J].测绘学报,2011,40(6):778-784.

[17]
谢顺平,冯学智,都金康.网络Voronoi 图启发的粒子群空间优化建模[J].地球信息科学学报,2013,15(6):846-853.

[18]
涂伟,李清泉,方志祥.基于网络Voronoi 图的大规模多仓库物流配送路径优化[J].测绘学报,2014,43(10):1075-1082.

[19]
王新生,余瑞林,姜友华.基于道路网络的商业网点市场域分析[J].地理研究,2008,27(1):85-92.

[20]
艾廷华,禹文豪.水流扩展思想的网络空间Voronoi 图生成[J].测绘学报,2013,42(5):760-766.

[21]
Guo D, Zhu X, Jin H, et al.Discovering spatial patterns in origin-Destination mobility data[J]. Transactions in GIS, 2012,16(3):411-429.

[22]
Zhou Y, Fang Z, Thill J C, et al.Functionally critical locations in an urban transportation network: Identification and space-time analysis using taxi trajectories[J]. Computers, Environment and Urban Systems, 2015,52:34-47.

[23]
Pei T, Wang W, Zhang H, et al.Density-based clustering for data containing two types of points[J]. International Journal of Geographical Information Science, 2015,29(2):1-19.

Options
Outlines

/

〈 〉