城市交通轨迹处理的创新实验教学实践

徐秀娟，　赵小薇，　许真珍，　马瑞新，　贾　棋

(大连理工大学 软件学院， 辽宁 大连 116620)

0　引　言

大学生创新项目是国家为了进一步促进人才培养模式改革而提出的本科生项目，旨在强化创新创业能力训练，增强学生的创新能力和在创新基础上的创业能力[1-2]。学生可以自主选题或者选择教师从科研项目中抽取出的前沿课题形成一个项目进行研究，从项目选题开始跟随教师的指导，由学生进行项目背景调研和分析、设计项目的解决思路、分析与处理实验数据，最终完成整个项目的开发[3]。参与学生对科研有浓厚兴趣、学有余力、具备初步科研和动手能力，学校鼓励学科交叉融合，鼓励学生跨学科、跨学院申报大学生创新项目。通过开展大学生创新项目，重点培养学生将课本知识应用到实践的能力，从而提高大学生的创新能力[4-5]。

数据分析与处理是软件工程教学中不可缺少的实验，具有传统软件工程教学的局限性。城市交通轨迹作为近年来新产生的一类流数据，其数据特性与传统小数据有较大差异[6]。本城市交通轨迹方面的科研课题，引导本科生提出自己的想法，在老师指导下完成了5项大学生创新项目，本文将结合城市交通轨迹数据处理项目分析大学生在创新项目的学习过程中如何提高分析问题和解决问题的创新能力。

1　交通数据处理设计概念

目前国内大部分城市的出租车都已装备GPS，用来记录出租车的行驶轨迹。出租车是大城市覆盖范围较广、常用的交通工具，出租车轨迹数据具有定位精度高、连续性强的特点，且没有手机数据涉及的隐私问题，因此不仅在学术界还是在工业界，正成为一种相当重要的城市交通轨迹数据源[7]。

针对城市交通轨迹数据处理相关项目背景和研究意义与前景[8-9]，初期在获取了几个城市的出租车数据后进行了简单的统计和查询处理，为后续的具体计算与分析奠定基础。同时为了对数据进行更好地处理，学生需要接触并学习SQL Server，通过数据库对大量数据进行分析与提取。借助某城市出租车GPS数据[10]提供的行车轨迹，学生绘制了城市主要的交通路线图，如图1所示；并且根据图示路线的深浅大致推测出各条道路的车流量；随后学生又进一步对每个小时的数据进行了相应的分析，给出每个小时出租车走过的路线图，观察不同的时间段出租车分布地域的不同。

图1　某市一天的交通轨迹图

在此基础上，图2展示了城市交通轨迹数据处理流程图。在获取轨迹数据后，首先进行数据的采集和预处理；然后进行基本的数据挖掘操作，获取频繁路径；最后进行交通拥堵的检测，以及可视化程序结果。

创新实验项目组成员通过笔者给予的国内外相关资料，初步掌握了城市交通轨迹数据的特点，在一般数 据挖掘知识的基础上，认识到了轨迹数据流的特性，扩展了视野。相关的大学生创新项目采取渐进式教学方法[11]，主要进行了如下的实验：基于轨迹数据的打车时间计算实验；基于轨迹数据的拥堵检测实验；以及基于轨迹数据的拥堵可视化实验。

图2　城市交通轨迹数据处理流程图

2　大学生交通数据处理创新实验

2.1　基于城市交通轨迹数据处理的打车时间计算实验

本项目主要研究大规模的GPS数据的压缩和转换，以期望得到一个供动态查询所用的离线模型[12]。首先对数据进行预处理，得到某天的轨迹图。在实时动态查询过程中，利用离线模型计算打车概率与等待时间。本项目的研究内容分为三大模块：离线预处理模块、离线图模型和在线处理模块。

离线预处理包括文件分块、热点扫描、偏好轨迹处理3个步骤。① 针对输入文件进行分块处理：首先按照一周中的每天将文件分为7块，其次根据每天的数据计算差异度，最后根据差异度进行文件分块并用差值法存储文件。② 根据每辆出租车的行驶路线提取扫描热点区域；将打车概率的计算问题转化为一条轨迹上在这个时间段恰好会有几条有效轨迹覆盖到查询地点上。在预处理轨迹时，将轨迹抽象成由地点和时间拼接成的模式串作为算法使用的数据结构。对于数据分析时还要扫描出大量出租车都会经过的热门地区。③ 研究快速偏好轨迹处理算法。需要将对应每辆车的数据点映射到热点上，以求解得到全部的轨迹模式串。

离线图模块构造部分处理出在线查询时参考的频繁轨迹图模型。该模块主要研究频繁轨迹图模型构建与相关数据结构的设计与存储。根据离线预处理的结果，离线得到轨迹模式串的频繁模式子串。由于需要计算某一时间某一地点的打车概率以及等待时间，因此需要根据有效轨迹图的数据特征，设计一个能够有效地压缩存储空间的数据结构，如按时间分层的多重邻接表。多重邻接表将构造的有效轨迹图存储起来建立成一个图。频繁轨迹图得到的是一个图模型所转化成的离线参考数据模型，这个离线模型的大小需要有效压缩数据，并且在压缩过程中保证有效数据不丢失。

在线处理模块中针对每次查询输入，搜索轨迹图模型，进行打车概率与等待时间计算。首先根据用户提供的查询地点，定位到离线模型对应的热点区域。其次根据用户提供的时间信息，运用搜索算法求出这段时间内可以到达查询点的轨迹数。再次经过分析可知，打车概率是符合泊松分布的概率，可根据轨迹数对泊松分布进行参数估计。最后，通过泊松分布计算出打车概率，并根据几何分布计算出等待时间。

2.2　基于交通数据处理的交通流预测实验

随着城市化进程的推进，城市人口增加、道路增长率远低于汽车增长率等因素均造成了一系列交通问题，其中最为突出问题是交通拥堵问题。交通拥堵已经成为制约社会发展和城市经济的瓶颈，它直接影响了城市的整体运转效率，在城市发展过程中的短板效应日益明显。该问题与学生日常生活非常接近，学生对此类问题兴趣浓厚。经过调研后，学生发现要研究交通拥堵问题，首先应该做好交通拥堵的预防，即本项目期待能够根据道路数据中路段一段时间的交通状况预测分析出未来一段时间的该路段交通拥堵情况。在此基础上，对可能出现的拥堵情况通过媒体宣传或交通广播进行预警，来避免一定的拥堵情况。

本项目中从交通数据处理(即离线数据处理)和交通拥堵识别判断(即在线监控)两方面进行设计交通拥堵算法[13]。交通数据处理中，通过分离空间数据和实时数据分别采用不同方式压缩来提高压缩率和准确率。交通拥堵识别判断中，选取交通拥堵的特征参数(平均车速、密度、交通流量)，构造公式根据交通数据分别计算参数值。在大部分系统处理过程中，并不需要所有的数据都参与处理，所以，如何选取适应量轨迹数据也是离线数据处理中比较重要的部分。因此，对数据采集中收集到的数据进行预处理，即对离线数据处理，才能更高效地实现交通信息化。

拥堵识别包括地图信息分块、轨迹信息压缩、交通拥堵识别3个模块。① 地图信息分块：由于实际地图中所收集到的数据数量比较大，不适合进行算法实现结果测试。在不改变数据真实性的前提下，可对实际地图数据进行分块处理，形成相对较小的数据集，来进行调用并实现相应测试功能。② 轨迹信息压缩：对于交通拥堵处理、判断，除地图数据之外，还需车辆轨迹信息。对于轨迹来说，某些点是多余的点，增加了轨迹应用系统的负荷同时也提高了数据存储的代价。这些点完全可以选取特征点来替代表示。通过有效的轨迹数据压缩，能够减少数据存储成本，并且能够保持轨迹的效用。值得注意，车辆GPS轨迹信息中包含了实时信息和空间路径，两个数据具有不同的特性，所以本文采取的压缩方法包括：无损空间数据压缩和有限误差实时数据压缩。③ 交通拥堵识别：在描述道路交通状况时，根据数据分析，对特征参数的影响程度进行权值分析。选取特征参数速度、密度、流量，即每路段每小时行驶多少千米、每千米行驶多少辆车及平均每小时有多少辆车来测算道路通行状况，判断路况信息。其中，速度低、密度大、流量小的路段设定为拥堵路段。

本项目的实验数据来源于2011年1月新加坡最大出租车公司通过车载GPS所记录的数据[14]。总数据包括46.5万条道路轨迹，约1.5万辆出租车，总数据共9.26 GB。在线监控部分通过平均车速、交通流量、交通密度3个特征参数实现了交通拥堵模式判别。利用VISSIM软件，仿真一条长为1.2 km的单行单车道路段，分别在400 m、800 m及1 200 m处放置检测器，路段分为A、B和C段，方向由A驶向C。设定初始流量为2 000pcu/h，期望车速为60 km/h，由检测器分别检测0～2、2～4、4～6、6～8 min内的车辆平均速度、密度及交通流量，结果如表1所示。

表1　各路段平均车速、密度、交通流量

从表中可见，路段A从2～4 min开始出现一般拥堵状况；6 min时交通拥堵现象最为明显；8 min时，交通拥堵现象出现好转，道路状况有所改善。路段B在4～6 min开始出现一般拥堵状况；8 min时交通拥堵现象最为明显；0～8 min过程中，道路状况由畅通逐渐拥堵。路段C在6 min出现拥堵现象，且该时刻拥堵现象最为明显，一直持续到8 min。交通拥堵流从路段A逐步蔓延到路段B、C；6 min时，由于路段A拥堵明显，而路段B车辆大部分已经驶入路段C，故在此时刻，路段A、C拥堵现象最为明显；6～8 min时，由于路段A拥堵现象好转，路段C拥堵持续，故路段B驶入车增量大于驶出车增量，出现拥堵现象较为明显。综合路段A、B和C，该仿真路段交通状况由通畅、一般拥堵到较拥堵变化，如图3所示。

输入监控时间段，获取该时段按时分类轨迹数据， 根据数据中车辆轨迹判断所经过的道路，并将数据存储到道路集中。由公式分别计算出道路集中各道路的平均车速、密度、交通流量，再计算出综合测度值。如果综合测度值属于较拥堵、一般拥堵或者非常拥堵，则在地图中表示出该路段；否则不做处理。最后可视化的图形如图4所示。

图3路段A、B、C综合阈值

图4　交通拥堵识别模式应用

2.3　基于城市交通拥堵系统的可视化实验

基于获取的城市交通轨迹数据，学生开发了城市交通拥堵系统，从而更好地理解城市交通轨迹数据的意义，从多个角度图形化展示城市的交通状况，提高了学生分析问题的能力。

通过折线图的形式展示北京市全路网全天的交通指数走势。学生将道路交通指数划分为5个级别，取值范围为[0,10]，指数越大表示拥堵的程度越严重，各级别分别为畅通(0～2)、基本畅通(2～4)、轻度拥堵(4～6)、中度拥堵(6～8)和严重拥堵(8～10)，同时用绿、黄、橘、红、深红5种不同颜色对应5种不同级别拥堵等级，使结果更加直观。图5大致反映当天北京市全路网的交通情况，在0：00～6：00这一时间段内北京市路网交通状况处于畅通的状态，而在9：00～18：00之间北京市路网交通状况大部分处于基本畅通的状态。同时可以明显看出，在早上7：00前后和下午19：00前后北京市出现两个交通拥堵高峰期，全市的交通状况基本处于轻度拥堵和中度拥堵的状态。

路网概况主要分析全路网以及各环路、各级别道路的交通拥堵情况。用户自选时间段点击查询，系统用过拥堵检测算法，将分析结果通过地图库显示在地 图上，主要道路的拥堵程度通过对应颜色显示出来。

图5　路网指数

图6展示的是北京市某天8：30～8：35这5 min内北京市各个主要路段的交通拥堵情况，这里主要使用的是基于行程时间比算法来检测交通拥堵程度，可以看出，在8：30这个时间段北京各主要路段基本还是处于畅通状态，而各别的路段处于不同程度的拥堵，但大部分拥堵的路段还是位于四环以内。

图6　一天内路网概况

路网评估模块负责分析全路网的交通拥堵程度，而道路评估模块负责对特定道路的拥堵分析，主要有道路路况、速度评估、密度评估、流量评估和道路指数这5个功能。

其中，流量评估是对特定道路全天各时段的流量分析，并通过柱状图呈现结果。本系统将根据道路流量(辆/车道)不同划分道路服务水平为5个级别，分别为1级(0～84)、2级(84～157)、3级(157～262)、4级(262～336)和5级(大于336)，其中1级代表道路服务水平处理最理想状态，而5级表示道路服务水平处于不理想状态。如图7所示流量评估，用户选择查询北四环中路的流量评估，系统通过统计数据库中各个时段北四环中路通过的浮动车数量得出结果，并通 过柱状图展示结果。可以看出该道路在8：00～21：00

图7　北京市北四环中路交通流量评估

这段时间服务水平一直处于不太理想的状态，而凌晨7：00前该道路通过的车流量则较少。

对于检测道路拥堵程度所采用的基于行程时间比的道路交通指数，实际上可以理解为拥堵时延指数，其意义为在拥堵状态下车辆出行所耗费的时间比在非拥堵状态下车辆出行所耗费时间的倍数。如图8道路指数所示，用户选择查询北四环东路的交通指数，系统通过计算各个时段北四环东路的交通指数，并把结果用折线图展示出来。从图中可以看出，北四环东路在8：30和17：30出现两个交通指数高峰，意味着在这两个时间段该道路的大多数路段处于严重拥堵状态，车辆的实际行驶速度会比理想状态下慢很多。

图8　道路指数

3　创新实验效果

近3年来，获国家级大学生创新项目2项(基于移动轨迹数据的推荐算法，基于城市交通数据的拥堵算法设计与实现)和校级大学生创新项目3项(T-Catching基于移动轨迹的全局最优路线检索工具，大规模移动数据的打车推荐算法研究，基于移动数据的拥堵信息预测算法)。其中，国家级大学生创新项目发表1篇期刊学术论文“Taxi-RS: Taxi-Hunting Recommendation System Based on Taxi GPS Data”[13]，并且其中一位成员通过推免清华大学研究生；校级大学生创新项目发表1篇会议论文“A Novel Algorithm for Urban Traffic Congestion Detection Based on GPS Data Compression”[15]。相关软件著作权7项。总计30余位学生受益。

此外，基于创新项目开发的“基于城市交通轨迹数据的信息可视化软件”获得了辽宁省教育厅第二十届教育教学信息化大奖赛二等奖，该可视化软件应用到课程的设计中，作为教学课件丰富了课程的教学案例，展示给学生从而激发更多的学生参与到创新项目中。

4　结　语

通过参与城市交通轨迹数据处理相关的创新实验，项目组成员的创新思维、设计思维、实践思维和沟通能力都得到了有效地提升，同时也加深了学生将理论知识应用到实际的能力。同时，城市交通轨迹数据处理创新实验也将笔者的科研项目很好地融合到课程教学中，解决了进行数据挖掘、软件工程等课程实验时学生对于科研理论理解与实际脱节的问题。这些项目对于培养解决实际社会需求的工程人才进行了一次有效的探索。

参考文献(References)：

[1]吴远征, 倪杰, 董玉婷. 基于多维动态创新模型的大学生创新创业提升策略[J].实验室研究与探索, 2016, 35(2): 205-210, 240.

[2]贾棋,王祎,许真珍,等.以大学生科技竞赛为牵引的创新实验班建设[J]. 实验技术与管理, 2015, 32(4): 29-32.

[3]刘清,高金东,何原野. 基于创新试验培养大学生综合能力[J]. 实验室研究与探索, 2016, 35(1): 141-145.

[4]张运楚, 姜爱民, 徐红东, 等. 高校实验教学中创新教育现状与对策[J].实验室研究与探索, 2016, 35(2): 224-228, 240.

[5]汤佳乐, 程放, 黄春辉, 等. 素质教育模式下大学生实践能力与创新能力培养[J].实验室研究与探索, 2013, 32(1): 88-89, 135.

[6]陈宝权,曾琼.大数据时代的城市计算[J].中国计算机学会通讯, 2016, 12(6): 8-12.

[7]杜龙兵, 徐书克. 浅析大学生创新性实验计划项目[J].实验室研究与探索, 2012，31(2): 82-84.

[8]禹晓辉,于自强,陈勐.城市时空大数据的研究与应用现状[J].中国计算机学会通讯, 2016, 12(6): 20-26.

[9]陆旻,王祖超,袁晓如,等. 城市移动数据知微探秘[J].中国计算机学会通讯, 2016, 12(6): 32-39.

[10]Yuan Nicholas Jing, Zheng Yu, Xie Xing,etal. T-drive: Enhancing driving directions with taxi drivers’ intelligence[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(1): 220-232.

[11]张博. 基于云计算的出租车轨迹数据挖掘研究[D]. 西安: 西安电子科技大学. 2014.

[12]赵小薇,许真珍,田琳琳,等. 渐进式教学在软件工程建模课程中的应用探索[J]. 计算机教育, 2015(20): 49-52.

[13]Xu Xiujuan, Zhou Jianyu, Liu Yu,etal. Taxi-RS: Taxi-hunting recommendation system based on taxi GPS data[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(4): 1716-1727.

[14]Song Renchu, Sun Weiwei, Zheng Baihua,etal. PRESS: A novel framework of trajectory compression in road networks [C]∥In Proceeding of the 40th International Conference on Very Large Data Bases, 2014, 7(9):661-672.

[15]Xu Xiujuan, Gao Xiaobo, Zhao Xiaowei,etal. A novel algorithm for urban traffic congestion detection based on GPS data compression [C]∥In Proceeding of 2016 IEEE International Conference on Service Operations and Logistics, and Informatics, 2016: 107-112.