王迎 赵建军 李兴菊 聂红梅

摘 要：交通大数据的应用和发展为现代车辆路径规划带来了机遇和挑战。因此，了解交通大数据概念、路网匹配、路径规划算法、交通信息预测等方面的研究现状和研究特点，对明确未来路径规划研究方向和发展趋势显得尤为重要。首先介绍交通大数据概念及轨迹数据预处理方法，归纳总结国内外在路网匹配上的各种匹配算法及其优缺点;然后，阐述常用路径规划算法，其中包括传统经典算法与当下流行的智能算法;随后对交通信息预测研究方法和各种预测模型进行简要概括;最后指出车辆路径规划现阶段存在的问题，并展望未来研究方向。

关键词：智能交通;路径规划;交通大数据;行驶车辆;路网匹配;交通信息预测

DOI：10. 11907/rjdk. 201374

中图分类号：TP301 文献标识码：A 文章编号：1672-7800（2020）010-0050-05

Abstract： The application and development of traffic big data brings new opportunities and challenges to modern vehicle route planning. Therefore， it is particularly important to understand the concept of traffic big data， the research status and characteristics of road network matching， route planning algorithm， and traffic information forecasting for the research direction and development trend of future route planning. In this regard， the concept of traffic big data and the preprocessing of trajectory data are introduced firstly. Secondly， the various matching algorithms for road network matching at home and abroad and the advantages and disadvantages of each algorithm are summarized. Then， the common route planning algorithm including traditional classical algorithms and current popular intelligent algorithms are elaborated. The following are brief summaries of research methods and various predictive models for traffic information prediction. Finally problems existing at the current stage of vehicle route planning are pointed out and the prospects for future research are presented.

Key Words： intelligent transportation; route planning; traffic big data; driving vehicles; road network matching; traffic information forecast

0 引言

近年來随着大数据、人工智能、物联网等技术的快速发展，智慧城市（Smart City）和智慧交通（Smart Traffic）逐步走入大众视野，其中智能交通在智慧城市中扮演着重要角色。一方面车辆成为人们日常生活中不可或缺的重要交通工具，让公众出行变得便利;另一方面车辆需求变大，导致交通拥堵、交通事故频发，使公众人身和财产安全受到侵害。智能交通的出现为车辆行驶提供了安全、可靠、灵活的路径规划。在现阶段，全球定位系统（GPS）、地理信息系统（GIS）、电子计算机技术及大数据技术等系统技术的融合为车辆路径规划提供了重要支撑，从而一定程度上降低了交通拥堵、交通事故的发生率，为智慧城市的实现作出了重要贡献。

目前城市道路建设的速度无法匹配交通流增长速度，现有道路建设已不能满足公众出行畅通、交通安全的需求。智能交通系统（Intelligent Transportation Systems，ITS）应运而生，并逐步成为当下交通领域研究热点。车辆路径规划是智能交通系统重要研究方向之一，国内外学者在该方面已取得了丰硕成果。车辆路径规划通过分析大量历史与当前交通信息数据预测未来交通情况，从而为用户提供更好的交通行驶体验。其研究内容包括交通信息预测、路网模型和路径规划算法等。综上所述，随着大数据平台的兴起、人工智能的发展、设备性能的提升，进行新技术下车辆路径规划研究迫在眉睫。

1 交通大数据

1.1 交通大数据特征

交通大数据是智能交通系统基础，研究和分析交通大数据是实现智能交通系统的重要环节。传统交通数据特征有3V [1]、4V[2]、5V[3]，与传统交通数据不同，交通大数据有6V特征[4]，如表1 所示。

众多学者[5-7]从交通安全、交通监测、交通车辆行驶效率、公交基础建设、运营管理及出行预测等方面研究了大数据对智能交通的作用。交通大数据的出现不仅为智能交通系统的实现提供重要的技术支撑，而且也为车辆路径规划和信息预测提供巨大的数据保障。

1.2 轨迹数据

轨迹数据属于交通大数据，其数据丰富性和多样性符合交通大数据的6V特征，即体量大（Volume）、速度快（Velocity）、多源（Variety）、难辨识（Veracity）、价值密度低（Value）、可视化（Visualization）。当轨迹数据为分析对象时，数据特征和处理技术架构等有价值的信息是关注重点。

轨迹数据是通过对1个或多个移动对象运动过程的采样而形成的数据信息，一般包括GPS定位数据、时间数据、速度数据等。轨迹数据来源广泛，不仅可通过卫星定位、手机APP信息、通信服务基站、流动公交等途径获取，还可通过RFID技术、图像识别技术等方式获取，例如出租车、公交车等交通工具的活动轨迹数据可通过车载GPS 技术获取。

轨迹数据采样受设备、采样等因素影响，其数据特点[8]如表2所示。

1.3 数据预处理

数据是进行各项工作的基础，由于轨迹数据来源多样且复杂，因而存在许多非人为的误差或错误。为了得到更准确且有价值的数据，需对轨迹数据进行必要的数据清洗工作[9]。

轨迹数据清洗是为了剔除数据中的冗余点与噪音点。车辆在静止和行驶状态下会产生大量冗余点。有基于停留区域的轨迹数据挖掘，例如对旅游路线热点区域和路线进行推荐[10]，挖掘其中热点区域和剔除冗余采样点;有基于速度的行为模式挖掘，其关注重点是基于速度划分的行为模式[11];有基于用户行为模式的挖掘，通过基于速度的出行模式划分，获取用户行为模式与习惯[12]。而噪音点是数据接收设备异常导致的错误数据，例如，行驶车辆进入地下停车场或进入隧道涵洞干扰卫星定位而导致的接受信号偏差。噪音点会影响数据分析准确性。常用轨迹数据清洗处理方法还有噪音滤波（Noise Filtering）[13-14]、停留点检测（Stay Point Detection）[15-16]等。

2 路网匹配

2.1 概述

路网匹配指轨迹数据与数字地图结合，将卫星定位坐标下的采样序列转换成路网坐标序列，将GPS轨迹点匹配到实际路网上[17]。路网匹配不仅有利于对相应交通大数据进行分析挖掘，还可辅助解决智慧城市交通问题。首先浮动车每天可收集到大量包含车辆和用户信息的卫星定位坐标序列和车载数据，然后通过使用大数据处理车辆轨迹数据，挖掘出有价值的信息。路网匹配在一定程度上能反映车辆行驶状态信息及行驶路径，便于了解当前交通情况、交通流量、交通流速等，从而为车辆行驶提供有价值的参考，存在巨大的科研和应用价值。另外，位置服务和移动社交网络越来越普及，衍生了丰富的应用，如常用线路查找[18]、道路交通监管[19]、智慧城市规划[20]、地理位置信息网络[21]等已开始使用轨迹数据，以提高服务质量。但是，由于轨迹数据质量较差，如果不对其进行路网匹配，将无法正确显示于道路上。经过路网匹配后，轨迹数据采样点会映射到一个路网中。路网匹配对于评估交通流、车辆导航、车辆行驶路线预测等具有重要作用。

2.2 算法

路网匹配是较为复杂的问题，已积累多种相关算法。有关路网匹配的算法也是目前研究热点。根据轨迹数据涉及的信息，现有常用路网匹配算法如表3所示，其中隐马尔可夫路网匹配算法是目前算法研究热点。

3 路径规划

3.1 概述

路径规划在交通领域应用广泛，如GPS 导航、GIS 系统路径规划、城市路网规划等[34]。路径规划核心是算法，在过去的几十年中，算法已取得巨大进展，由传统算法发展至目前人工智能算法[9]。由于算法特点和适用范围各不相同，应充分考虑其特点，才可选取合适的路径规划算法。

3.2 路径规划算法

3.2.1 Dijkstra 算法

Dijkstra 算法是典型的最短路径算法，由Dijkstra[35]于1959年提出。该算法通过所有节点正向遍历比较得到最短路径，适用于道路权值为非负的最短路径问题[36]，能得出某个点到其它点的最短路径。该算法对最短路径的计算较为准确，其鲁棒性能也较好，但是该算法需经过多次遍历，导致节点多、耗时长、占用空间大。

3.2.2 Floyd算法

Floyd算法是求最短路径的经典算法之一，由Floyd于1962年提出，可读性和理解性较好。该算法可以正确处理有向图的最短路径问题，时间复杂度为[O（n3）]，实际效果较Dijkstra 算法更好，改进后也可求无向图最短路径[37]。

3.2.3 Lee算法

Lee算法较早用于电路路径追踪[38]，该算法适用于轨迹数据实时变化的路径规划，代价相对较小。理论上只要存在最佳路径，该算法基本可找到该条最佳路径[39]，但是相对复杂多层的路径，其占用空间很大。

3.2.4 蚁群算法

蚁群算法（Ant Colony Algorithm，ACA）是Marco Dorigo在1991年提出的一种用来搜寻优化路径的概率型隨机搜索算法。其思想是整个蚁群集体构成待优化的解空间，模拟蚂蚁觅食途中会留下信息素，较短路径的蚂蚁释放信息素较多。随着时间的推移，在相同时间内最短路径上蚂蚁释放的信息浓度高。在正反馈作用下，信息素浓度高的最短路径很快会被发现[40]。该算法计算机易于实现，鲁棒性较强，但容易陷入局部最优解。

3.2.5 神经网络算法

神经网络算法（Neural Network Algorithm，NNA）是模拟动物的神经网络信息传递，通过逻辑性思维推理过程的一种算法。该算法也是人工智能中常用的一种，其信息是分布式存储的，信息处理是通过类似神经元之间的相互作用动态处理。但是路径规划路网复杂多变，很难用数学公式进行描述，通过改进可以实现路径规划。如小波神经网络算法，该算法是将小波分析与神经网络结合，通过小波分析对高低频信号进行处理找到其信号特征值，并将这个信号特征值输入于神经网络进行下一步神经网络算法处理[41]。

3.2.6 遗传算法

遗传算法（Genetic Algorithm，GA）是最早由Holland教授于1975年提出的一种人工智能算法[42]。该算法模拟生物进化论思想，并融合了适者生存的概念。遗传算法根据待优化问题的目标函数构造相应适应度函数，再对其进行初始化、评价和遗传操作。遗传算法具有快速随机搜索能力，鲁棒性好，扩展性强，但是编程较为复杂，算法搜索速度较慢。

3.2.7 粒子群算法

粒子群算法（Particle Swarm Optimization，PSO）是Eberhart&Kennedy提出的一种新的进化算法，也称为鸟群觅食算法。该算法从规律性鸟群集体活动中得到启发，通过个体对信息的共享使整个群体运动从无序化到有序化的演变，最终获得最优解。粒子群算法常被用于求解机器人或车辆路径规划问题[43]。该算法原理简单、参数少、易操作实现、计算速度快，而且具有记忆功能，但是对种群大小不十分敏感，易陷入局部最优解。

3.2.8 A*算法

A*算法是一种静态网络中求最短路径的启发式搜索算法。A*算法如果能找到一个合适的启发函数，即可加快最短路径搜索速度，进而提高最短路径搜索精度。A*算法是一种最佳优先算法，较适合求解最短路径，鲁棒性也较强，但是易忽略本身节点限制，不过后续可通过增加节点进行改进[44]。

4 交通信息预测

准确的交通信息预测是智能交通领域的重要研究内容。近些年，在基于大数据的车辆路径规划相关研究中，对车辆数据发掘并作出交通信息预测成为热点。

目前，有许多预测方法被广泛用于交通信息预测并取得了不错的效果，如卡尔曼滤波方法[45]、时间序列方法[46]、神经网络法[47]、马尔可夫预测[48]及灰色预测理论等[49]，上述各方法又可建立多种预测模型。其中时间序列方法在车辆交通流预测研究应用中使用较多，是交通流预测研究热点。较早提出的预测模型有自回归模型（AR）、自回归滑动平均模型（ARMA）、滑动平均模型（MA）[50]等。这些模型具有计算精度高、应用规模大、实时性好等优点，但有时无法准确反映交通状况的不确定性，抗干扰能力较差。因此，通常选取多种预测模型组合，使其优缺点互补，以最合适的预测模型进行交通信息预测。如马尔可夫预测模型经常与小波理论、BP神经网络等模型组合，这些模型在交通信息预测方面也有不错的效果。除此之外，结合人工智能算法的混合模型[51]、组合预测理论[52]、混沌理论[53]等也被广泛应用于交通信息预测。交通信息预测为减少交通堵塞、提高道路利用率、适时实施交通管制及城市环境保护提供了强有力的技术支持，具有重要的现实意义。

5 结语

本文对基于大数据的车辆路径规划关键环节，包括交通大数据处理、路网匹配、路径规划算法、交通信息预测的国内外研究情况进行了重点介绍。传统静态车辆路径规划系统发展相对较成熟，基于实时动态的车辆路径规划、城市交通路网规划、城市交通轨迹数据挖掘等是现代智能交通系统研究热点，因此结合人工智能、大数据平台的动态车辆路径规划备受重视。随着人工智能算法、大数据挖掘、无线通信、北斗卫星导航等技术的进一步成熟，基于交通大数据的智能车辆路径规划将得到更加长足的发展，但同时交通数据安全不容忽视，如何建立完善的隐私保护机制是大数据时代的新挑战。

参考文献：

[1] LANEY D. 3D data management： controlling data volume， velocity and variety[J].  META Group Research， 2001， 949（6）： 1-4.

[2] CHEN M， MAO S W， ZHANG Y， et al. Big data related technologies， challenges and future prospects series[M].  NewYork：Springer， 2014.

[3] 程学旗， 靳小龙， 王元卓，等.  大数据系统和分析技术综述[J].  软件学报， 2014， 25（9）： 1889-1908.

[4] 陆化普，孙智源， 屈闻聪.  大数据及其在城市智能交通系统中的应用综述[J]. 交通运输系统工程与信息， 2015， 15（5）： 45-52.

[5] 岳建明，袁伦渠. 智能交通发展中的大数据分析[J]. 生产力研究， 2013， 251（6）： 137-138，165.

[6] TAO S， CORCORAN J， MATEO-BABIANO I， et al. Exploring bus rapid transit passenger travel behavior using big data[J]. Applied Geography， 2014， 53（53）： 90-104.

[7] SUN J， ZHANG C， ZHANG L H， et al. Urban travel behavior analyses and route prediction based on floating car data[J].  Transportation Letters， 2014， 6 （3）： 118-125.

[8] 高強，张凤荔， 王瑞锦， 等.  轨迹大数据： 数据处理关键技术研究综述[J]. 软件学报， 2017， 28（4）： 959-992.

[9] 李建明. 浮动车数据挖掘及其在路径规划中的应用[D].  沈阳： 沈阳航空航天大学， 2016.

[10] ZHENG Y， XIE X. Learning travel recommendations from user-generated GPS traces[J]. ACM Transactions on Intelligent Systems &Technology， 2011， 2（1）： 389-396.

[11] LI S， PETER R S. Review of GPS travel survey and GPS data-processing methods[J].  Transport Reviews， 2014， 34（3）： 316-334.

[12] STENNETH L， WOLFSON O， YU P S， et al. Transportation mode detection using mobile phones and GIS information[C]. Chicago：ACM Sigspatial International Symposium on Advances in Geographic Information Systems， 2011.

[13] LEE W C， KRUMM J. Computing with spatial trajectories[M]. New York：Springer，2011.

[14] HIGHTOWER J， BORRIELLO G. Particle filters for location estimation in ubiquitous computing： a case study[C].  Nottingham： The 6th International Conference on Ubiquitous Computing， 2004.

[15] WANG Y， ZHENG Y， XUE Y. Travel time estimation of a path using sparse trajectories[C].  New York： Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data mining， 2014.

[16] QI G， PAN G， LI S， et al. How long a passenger waits for a vacant taxi-Large-scale taxi trace mining for smart cities[J].  Green Computing & Communications， 2013： 1029-1036.

[17] JENSEN C S， TRADISAUSKAS N. Map matching[J].  Encyclopedia of Database Systems， 2016： 1692-1696.

[18] LI X， HAN J， LEE J， et al. Traffic density-based discovery of hot routes in road networks[C]. Boston：The 10th International Symposium on Advances in Spatial and Temporal Databases，2007.

[19] YUAN Y F， VAN L H， VAN W F， et al. Network-Wide traffic state estimation using loop detector and floating car data[J].  Journal of Intelligent Transportation Systems， 2014， 18（1）： 41-50.

[20] YUAN N J， ZHENG Y， XIE X， et al. Discovering urban functional zones using latent activity trajectories[J]. IEEE Transactions on Knowledge and Data， 2015， 27（3）： 712-725.

[21] ZHENG Y， WANG L， XIE X， et al. GeoLife： managing and understanding your past life over maps[C].  Beijing： The 9th International Conference on Mobile Data Management， 2008.

[22] BERNSTEIN D， KORNHAUSER A. An introduction to map matching for personal navigation assistants[J].  Geometric Distributions， 1996， 122（7）： 1082-1083.

[23] TAYLOR G， BLEWITT G， STEUP D， et al. Road reduction filtering for GPS-GIS navigation[J].  Transactions in GIS， 2001， 5（3）： 193-207.

[24] YIN H， WOLFSON O. A weight-based map matching method in moving objects databases[C].  Chicago： The 16th International Conference on Scientific and Statistical Database Management， 2004.

[25] BLAZQUEZ C， VONDEROHE A. Simple map-matching algorithm applied to intelligent winter maintenance vehicle data[J].  Journal of the Transportation Research Board， 2005， 1935（1）： 68-76.

[26] BRAKATSOULAS S， PFOSER D， SALAS R， et al. On map-matching vehicle tracking data[J].  International Conference on Very Large Data Bases， 2005， 2： 853-864.

[27] NADINE S， KAY W A. Map matching of GPS traces on high-resolution navigation networks using the multiple hypothesis technique （MHT）[J].  Working Paper Transport and Spatial Planning， 2009， （10）： 568-588.

[28] QUDDUS M A， NOLAND R B， OCHIENG W Y. A high accuracy fuzzy logic based map matching algorithm for road transport[J].  Journal of Intelligent Transportation Systems， 2006， 10（3）： 103-115.

[29] OBRADOVIC D， LENZ H， SCHUPFNR M. Fusion of map and sensor data in a modern car navigation system[J].  Journal of Signal Processing Systems， 2006， 45（1）： 111-122.

[30] XU H， LIU H C， TAN C W， et al. Development and application of an enhanced Kalman filter and global positioning system error-correction approach for improved map-matching[J].  Journal of Intelligent Transportation Systems， 2010， 14（1）： 27-36.

[31] CHERIF S， EL-NAJJAR M E， FRANCOIS C. A road matching method for precise vehicle localization using hybrid Bayesian network[J].  Journal of Intelligent Transportation Systems， 2008， 12（4）： 176-188.

[32] NEWSON P， KRUMM J. Hidden Markov map matching through noise and sparseness[C].  Seattle： The 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems， 2009.

[33] LOU Y， ZHANG C， ZHENG Y， et al. Map-Matching for low-sampling-rate GPS trajectories[C].  Seattle： The 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems， 2009.

[34] JOHN K. Probabilistic modeling of traffic lanes from GPS traces[C].  San Jose： The 18th ACM Sigspatial International Conference on Advances in Geographic Information Systems， 2010.

[35] DIJKSTRA E W. A note on two problems in connection with graphs[J].  Numerische Mathematik， 1959， 1（1）：269-271.

[36] JAVED A， SEJOON L. Congestion-aware traffic routing system using sensor data[C].  Anchorage： The 15th International IEEE Conference on Intelligent Transportation Systems， 2012.

[37] 周程. 物流配送路徑优化策略研究[J].  武汉理工大学学报， 2005， 29（5）： 797-800.

[38] LEE C Y. An Algorithm for path connections and its applications[J].  Electronic Computers， 1961， 10（3）： 346-365.

[39] JOHN F， PETER R. Adaptive routing for road traffic[J].  IEEE Computer Graphics and Applications， 2000， 20（3）： 46-53.

[40] YU Z K， NI M F， WANG Z Y. Dynamic route guidance using improved genetic algorithm[J].  Mathematical Problems in Engineering， 2012， 2013（1）： 1-6.

[41] LI Y， WANG R， XU M. Rescheduling of observing spacecraft using fuzzy neural network and ant colony algorithm[J].  Chinese Journal of Aeronautics， 2014， 27（3）： 678-687.

[42] 尹元韬，王焱. 遗传算法改进策略研究进展[J]. 信息技术与信息化，2010（3）： 40-45.

[43] CALABRESE. Real-time urban monitoring using cell phones： a case study in Rome[J].  IEEE Transactions on Intelligent Transportation Systems， 2010， 12（1）：141-151.

[44] RAJESH K B， NGUYEN X K. Real-time trip information service for a large taxi fleet[C]. Bethesda： Proceedings of the 9th international conference on Mobile systems， applications and services， 2011.

[45] 石曼曼.  基于卡尔曼滤波的短时交通流预测方法研究[D].  成都： 西南交通大学， 2012.

[46] SMITH B L， DEMETSKY M J. Traffic flow forecasting： comparison of modeling approaches[J]. Journal of Transportation Engineering， 1997， 123（4）： 261-266.

[47] MARK S D， MARK R C. Short-term inter-urban traffic forecasts using neural networks[J].  International Journal of Forecasting， 1997， 13（1）： 21-31.

[48] 胡枫.  基于马尔科夫模型的短时交通流预测研究[D].  南京： 南京邮电大学， 2013.

[49] 许伦辉， 傅惠.  交通信息智能预测理论与方法[M].  北京： 科学出版社， 2009.

[50] 顾国民， 李未， 蔡家楣.  城市综合应急指挥系统的车辆路径规划研究与实现[D].  杭州：浙江工業大学， 2005.

[51] BAHER A， HIMANSHU P， WILL R. Short-term traffic flow prediction using neuro-genetic algorithms[J]. Intelligent Transportation Systems Journal， 2002， 7（1）： 3-41.

[52] 沈国江， 王啸虎， 孔祥杰.  短时交通流量智能组合预测模型及应用[J].  系统工程理论与实践， 2011， 31（3）： 561-568.

[53] 薛洁妮， 史忠科.  基于混沌时间序列分析法的短时交通流预测研究[J].  交通运输系统工程与信息， 2008， 8（5）： 68-72.

（责任编辑：江 艳）