1 引言

高速(Origin-Destination, OD)数据是指高速路网内从特定的起点到终点之间出行信息的相关数据, 如起点到终点之间的通行流量、旅行时间等数据. 高速OD数据中包含了高速公路整体路网的运行状态、高速公路出行特征、车流量的时空分布等多方面重要信息, 对高速公路的规划、管理、维护及养护、衡量区域经济发展状况及地区间的社会经济交流具有重要的参考意义.

传统高速公路OD数据的获取方法大多采用定期调查的方式, 通过特定的数据收集方式(甚至人工)得到一定时期内的高速OD数据, 往往需要耗费大量时间和人力, 而且数据的精度难以保证^[1-3]. 此外, 一些研究人员在高速公路断面通行量检测系统基础上通过广义最小二乘法估算的方法来估计时变的OD数据^[4]. 高速公路收费数据由于需要根据车辆进出收费站信息来收取费用, 其中蕴含了OD分析所需要的时空信息, 而且收费数据十分准确. 因此, 相对于前述方法, 其可用来生成更加精细化、更加全面的高速公路OD数据.

高速公路收费数据中包含了特定车辆进入某收费站的时间和离开另一收费站的时间, 可以看作是一种收费站点之间天然的OD数据. 基于高速公路收费数据可以计算得到收费站点之间在任意时间周期内的出行量、旅行时间等OD数据, 也可以针对不同车辆类型的细分得到各类车辆独自的OD数据. 然而, 由于高速公路出行的不断增加, 高速公路收费数据规模也越来越大, 一个大省的收费数据一个月可达到数亿条, 而收费站点也接近1000个, 意味着由此建立的一个OD矩阵有百万数据. 如果按照1小时的时间周期建立OD数据矩阵, 并且针对出行量、旅行时间等不同指标和不同车辆类型分别统计, 则一天需要生成数百个OD数据矩阵. 因此, 无论是在OD数据矩阵的计算方面还是OD数据矩阵的存储方面都对高速公路信息系统建设带来了极大的挑战. 张晶等提出, 处理海量数据, 必然要面对巨大的计算量, 一般的解决方法是采用分布式计算, 将计算任务分配到多台机器上并行处理, 从而提高运算速度^[5].

以Hadoop为代表的大数据技术的出现为高速公路OD数据的计算和存储提供了新的技术思路, Hadoop是一个在集群上处理海量数据的开源代码框架, 它具有分割大规模数据、合理分配任务并执行的特性, 在很多大型网站上已经得到了应用, 是目前最广泛应用的开源云计算平台^[6,7]. 本文将首先给出基于收费数据的高速公路OD数据逻辑表示模型和计算方式定义, 在此基础上进而研究了基于MapReduce的统计车辆平均旅行时间和统计车流量的2种OD矩阵生成算法和基于HBase的高速公路OD数据矩阵列式存储模型, 其中, 统计车辆平均旅行时间的OD矩阵可以掌握高速公路车辆的行驶情况, 统计车流量的OD矩阵可以更加清晰的反应出该路段的拥堵情况, 通过实验结果对比得出结论, 给出总结.

2 高速公路OD矩阵定义 2.1 定义

定义1. 收费站s, 高速公路上所有的收费站所在位置, 定义为S=(s₁, s₂,···, s_n), s=(id, type), s∈S, 其中id是收费站的编号, type为收费站类别, 进站口type的值为0, 出站口type的值为1.

定义2. 车辆收费数据L, 车辆收费数据是指高速公路各个收费站点捕获的车辆收费数据, 定义为L={l₁, l₂, ···, l_n}, l=( ${{{v}}_i}$ , ${{s}}_{{k}}^i$ ), 其中 ${{{v}}_i}$ 代表车辆的车牌号码, ${{s}}_{{k}}^i$ 表示车辆v_i经过收费站点 ${{{s}}_{{k}}}$ 的时间, ${{{s}}_{{k}}}$ 表示车辆 ${{{v}}_i}$ 经过的收费站点.

定义3. 车辆类别VType, 车辆分为多种类别, 如大货车, 大客车, 小汽车等, 不同类型的车辆使用不同类型的编号.

定义4. 车辆OD矩阵D, 高速公路上的车辆进站点和出站点为行和列构成的矩阵, 定义为D=(d₁, d₂, d₃, ···, d_n), 这里每一个 ${{{d}}_m}$ 可表示为 ${{{d}}_m}$ =( ${{a}}_{11}^m$ , ${{a}}_{12}^m$ , ${{a}}_{13}^m$ , ···, ${{a}}_{{{ij}}}^m$ , ···, ${{a}}_{{{nn}}}^m$ ), 其中m表示时间段区间( ${{{t}}_a}$ , ${{{t}}_b}$ ), 矩阵每一个元素的值 ${{{a}}_{ij}}$ 为车辆的出行时间、速度、数量等对车辆的不同度量, 体现为不同形式的值.

基于以上定义, 将高速公路OD矩阵划分为静态OD矩阵和动态OD矩阵, 其中, 静态OD矩阵的元素 ${{{a}}_{ij}}$ 代表某段时间以收费站点 ${{{s}}_{{i}}}$ 为起点, ${{\rm{s}}_j}$ 为终点的车辆交通出行量; 而动态OD矩阵是一个矩阵序列, 与时间的相关性远大于静态OD矩阵, 动态OD矩阵的每一个元素 ${{a}}_{{{ij}}}^m$ 表示以收费站点 ${{{s}}_{{i}}}$ 为起点, ${{{s}}_j}$ 为终点在时间段m内的交通出行量.

2.2 OD矩阵生成规则

高速公路OD数据最明显的内容即为车辆驶入驶出高速的时间和地点, 为了能够明显的反应高速公路车辆行驶情况, 将收费数据生成几类OD矩阵, 例如统计高速公路车辆旅行时间的OD矩阵, 统计车流量的OD矩阵, 统计两站点间车流量和平均旅行时间的OD矩阵, 统计不同车型的行驶速度的OD矩阵等, 本文中主要研究其中两类, 第一类为统计高速公路所有类型车辆旅行时间的OD矩阵; 第二类为统计高速公路所有类型车流量的OD矩阵. 其中各参数的含义如下:

(1)统计量(statistics): 该OD矩阵对应的表统计的指标, 即高速公路所有车型的平均旅行时间和车流量.

(2)时间区间(period): 用于表明统计对象的时间属性, 一个时间区间由一个开始时间点(startInstant)和一个结束时间点(endInstant)构成.

(3)进站点(stationIN): 车辆驶入高速的站点位置编号.

(4)出站点(stationOUT): 车辆驶出高速的站点位置编号.

(5)值(value): 度量统计量的值, 例如2493秒(旅行时间OD矩阵)或479辆(车流量OD矩阵).

2.2.1 统计高速公路车辆旅行时间OD矩阵

该矩阵是统计一定时间内出站车辆与其进站点间的平均旅行时间. 该OD矩阵计算所需的车辆信息要通过数据中的出站时间进行筛选. 在计算平均时间前需要将符合时间的车辆收费数据过滤掉车牌号等无效信息, 保留进出站时间. 平均旅行时间需要把所有进出站点相同的车辆旅行时间作平均计算. 将平均旅行时间放入OD矩阵中, 便于更直观、更方便的掌握高速公路整体路网的运行状态, 便于对高速公路进行调控. 统计高速公路车辆旅行时间的OD矩阵的逻辑模型如图1所示.

统计旅行时间OD矩阵的计算流程如图2所示.

第1步. 设置统计数据的时间段.

第2步. 读取一条数据 根据统计的时间间隔判断该数据的出站时间是否在该时间间隔内.

第3步. 如果是在时间间隔内, 查找该数据对应的车辆的进出站时间和进出站ID. 否则判断是否有未遍历到的数据, 若仍有未遍历到的数据, 则读取另一条数据, 否则重新设置统计数据的时间段.

第4步. 取出站时间满足统计时间间隔的完整数据, 用进出站时间计算该条数据的旅行时间.

第5步. 找到该路线所有车辆的旅行时间并求平均值, 将旅行时间平均值放入OD矩阵中.

2.2.2 统计高速公路车流量OD矩阵

该矩阵是统计一段时间间隔内两进出点间车辆数目. 该OD矩阵计算所需的的车辆信息需要过滤掉收费信息中的员工编号、进站栏位等等无效信息, 再依据数据中的进出站时间筛选. 该OD矩阵需要的车流量信息需要通过依据进出站点名称筛选统计两进出站点间流量. 将流量放进OD矩阵中能够更加清晰、直观的反应两进出站口间车流量情况, 车辆拥堵状况, 方便及时对高速车流量进行调控, 减少拥堵情况, 降低事故发生机率. 统计高速公路车流量的OD矩阵的逻辑模型如图3所示.

统计车流量OD矩阵的计算流程如图4所示.

第1步. 设置统计数据的时间间隔.

第2步. 读取一条数据, 根据统计的时间间隔判断该数据的出入站时间是否在该时间间隔内.

第3步. 如果是在时间间隔内, 查找该数据对应的车辆的进出站ID和时间、车辆牌照信息. 否则判断是否有未遍历到的数据, 若仍有未遍历到的数据, 则读取另一条数据, 否则重新设置统计数据的时间段.

第4步. 取进出站时间满足统计时间间隔的完整数据, 将相同路径的车流量叠加, 最终车流量放入流量OD矩阵中.

3 基于HBase的OD数据存储模型

HBase是Hadoop家族中的NoSQL数据库, 是一个高可靠性、高性能、列存储、可伸缩、支持实时读写、面向联机事物处理、分布式的大型数据存储系统. 底层的Hadoop分布式文件系统HDFS具有高容错性且可以被部署在低价的硬件设备之上^[8,9].

HBase表主要由以下几部分构成:

表(table): HBASE在表中组织数据, 表名是字符串和字符的组合.

行(row): 表中数据按水平划分为多行, 每行由唯一的rowkey确定.

行健(rowkey): 是行的唯一标识数据, 没有数据类型, 一般是一个字节数组.

列族(Column Family, CF): 数据在竖直方向划分成多个列族, 列族要预先定义, 且不容易修改, 每行数据都拥有相同的列族, 但是可能有些行的数据为空, 列族是字符串和字符的组合.

列限定符(Column Qualifier, CQ, 也叫列标识): 数据在列族中的位置是通过列标识指定的, 每行的列标识可以不同, 列标识没有数据类型, 一般是一个字节数组.

单元(cell): 单元是行健(rowkey)、列族(column family)、列限定符(column qualifier)的组合, 这些存储在单元中的数据被称为单元数据.

时间戳(timestamp): 单元数据是有版本的, 每一个单元数据对应一个版本, 由时间戳来指定.

统计高速公路车辆旅行时间的OD矩阵在HBASE中存储模型如表1所示. 将设置的时间段、进站ID、出站ID作为RowKey, 将车辆的平均旅行时间作为value.

统计高速公路车流量的OD矩阵物理模型如表2所示. 将设置的时间段、进站ID、出站ID作为rowkey, 将车流量作为value.

4 OD矩阵计算在大数据环境下的实现 4.1 旅行时间OD矩阵计算方法在MapReduce下的实现

MapReduce计算框架由Input, Map, Shuffle, Reduce, Output 5个部分组成.

Input阶段: 读入数据并设置统计时间段.

Map阶段: 读取所有输入数据, 对每行数据进行解析. 以“出站时间+进站点+出站点”作为key, 计算旅行时间作为value.

Shuffle阶段: key值相同的value会存入一组, 传送到Reduce.

Reduce阶段: 针对每个key, 统计value的个数count, 并计算value和sum, 计算value均值sum/count作为新输出value.

Output阶段: 以key-value的方式输出计算结果, 最终的key为“出站时间+进站点+出站点”, value为“平均旅行时间”.

该算法实现的流程如图5所示, 伪代码如算法1所示.

算法1. 旅行时间OD矩阵计算方法

输入: 高速流量数据

输出: 旅行时间OD统计信息

1. function MAP(key, value, context)

2.　items = value.split("r");

3.　timeIn = items[4];

4.　timeOut = items[7];

5.　key = items[7].split(":")[0] + items[3] + items[6];

6.　odTime = timeOut – timeIn;

7.　context.write(key, odTime);

8. end function

9. function REDUCE(key, Iterable<ODTime>, context)

10.　count = 0;

11.　totaltime = 0;

12.　avg = 0;

13.　for ODTime TIME: L do

14.　　totaltime = totaltime + TIME.getTOTALTIME();

15.　　count + +;

16.　end for

17.　avg = totaltime/count;

18.　context.write(key, avg)；

19. end function

4.2 车流量OD矩阵计算方法在MapReduce下的实现

车流量OD矩阵计算方法的实现与旅行时间类似. 主要区别在Reduce阶段, 需要对进出站的时间进行过滤.

Input阶段: 读入数据并设置统计时间段.

Map阶段: 读取所有输入数据, 对每行数据进行解析. 以“出站时间+进站点+出站点”作为key, 旅行时间作为value.

Shuffle阶段: key值相同的value会存入一组, 传送到Reduce.

Reduce阶段: 针对每个key, 统计value的个数count, count作为新输出value.

Output阶段: 以key-value的方式输出计算结果, 最终的key为“出站时间+进站点+出站点”, value为“车流量数”.

该计算方法的流程如图6所示, 伪代码如算法2所示.

算法2. 车流量OD矩阵计算方法

输入: 高速流量数据

输出: 车流量OD统计信息

1. function MAP(key, value, context)

2.　items = value.split(",");

3.　timeIn = items[4];

4.　timeOut = items[7];

5.　key = items[7].split(",")[0] + items[3]+ items[6];

6.　odTime = timeOut – timeIn;

7.　context.write(key, odTime);

8. end function

9. function REDUCE(key, Iterable<ODTime>, context)

10.　count = 0;

11.　totaltime = 0;

12.　for ODTimoTIME : L do

13.　　totaltime = totaltime + TIME .getTOTALTIME();

14.　　count + +;

15.　end for

16.　context.write(key, count);

17. end function

5 实验评价 5.1 实验环境

本文中生成OD矩阵所需的高速公路的收费数据数据量庞大, 但是对实时性要求不高, 所以选用在Hadoop集群环境下使用MapReduce分布式离线计算框架进行实验. 集群包含3个节点, 其中1个主节点, 2个从节点, 每个节点的CPU都为4核, 运行内存16 GB, 主机硬盘2 TB.

5.2 实验数据

实验数据为河南省高速2018年的真实收费数据. 该数据记录了300余个高速公路出入口, 全年的车辆出入情况, 共计10 743万余条记录. 每条数据的记录形式如表3所示, 包含车牌号、驶入站点、驶出站点、驶入时间、驶出时间等12个属性.

为了方便进行实验和性能评估, 需要对数据进行过滤和清洗. 数据中最核心的属性就是车牌号, 所以按照标准的车辆牌照字符要求: 正规的车辆牌照应该为7位有效字符, 第一位为省份汉字简称, 第二位为大写英文字母形式的省内区域代号, 后五位应该是大写英文字母和数字的组合. 根据上述要求, 可能出现的不规范数据问题有如下几项:

(1) 车辆牌照第一个字符不是省份汉字简称.

(2) 省份汉字简称多余1个.

(3) 车辆牌照中出现非法字符, 如: 小写字母, 特殊符号等.

(4) 车辆牌照位数不足.

(5) 无牌照信息.

包含上述任何一条的数据将被认为是不符合要求的数据, 将这些数据过滤掉. 本文中提到的实验只需要各种类车辆在时间和空间上的信息, 所以将过滤后的数据进行进一步的压缩, 只保留车牌号、驶入站点、驶出站点、驶入时间、驶出时间和车辆类型这六个属性, 其他属性对于本次实验来说并非必要数据, 所以将其余属性去除以保证在程序运行和计算过程没有额外的不必要消耗, 保证程序运行性能.

5.3 计算模型评价

实验对生成旅行时间OD矩阵和车流量OD矩阵所用时间进行了评价. 在相同的硬件条件下, 控制输入时数据的规模, 统计计算所用时间.

5.3.1 旅行时间OD矩阵

实验测试不同的统计天数统计车辆平均旅行时间的OD矩阵计算效率如表4所示, 实验证明, 数据量越大的情况下, 计算效率越高.

5.3.2 车流量OD矩阵

实验测试不同的统计天数统计车流量的OD矩阵计算效率如表5所示, 实验证明, 当数据量增大时, 计算效率增高.

5.4 存储模型评价

对于存储模型的设计, 主要考虑设计的模型占用的物理存储空间大小. 传统的存储方式主要是基于MySQL的关系型数据存储模式,这种存储方式不适合存储海量的数据, 需要多个表进行存储才便于对数据的处理, 而本文采用基于HBase的列式存储模式, 数据量相对较小时, 两种存储方式差别并不大, 而数据量较大时, 本文设计的存储方式节省物理存储空间. 如表6所示, 当存储时间长度为7天的数据时, 本文设计的存储方式只比传统存储方法节省3%的物理存储空间, 当存储时间长度为一年的数据时, 本文设计的存储方式比传统存储方式节省近10%的物理存储空间.

两种存储方式的对比情况如图7所示.

6 总结

高速公路经过长时间的发展, 已经形成了比较健全的路网结构, 信息化的建设已经逐步成型, 并覆盖到高速公路的许多业务领域, 现有的高速公路运营系统对于海量数据的处理效率低下, 本文从大数据分析的角度实现了生成车辆OD矩阵的过程, 将生成的矩阵存入HBase中, 并对存储的效率和存储空间进行了分析, 以便于后续对生成的OD矩阵进行聚类等分析.