基于出租车经验路径相似性的路径规划方法

邓 悦 孟俊贞 赵东保

(1. 华北水利水电大学 测绘与地理信息学院, 河南 郑州 450046;2. 华北水利水电大学 地球科学与工程学院, 河南 郑州 450046)

0 引言

基于位置服务技术和定位技术的快速发展,海量出租车轨迹数据被记录下来。这些数据含有重要的历史经验知识,如出租车司机在考虑路径距离、道路等级、动态路况和周围环境等情况下得到的行驶经验和城市交通网中出租车的行驶规律等信息。如何从出租车轨迹中提取有价值的路径信息已成为一个研究热点。

传统路径规划算法没有考虑到出租车轨迹数据的经验知识,一般都是通过计算车辆在基于城市路网的时间最短路径和空间最短路径[1-3],并将符合时间和空间距离最短路径是为最流行推荐路径。近年来,在国内外车辆导航研究中,人们开始更加重视交通状况及驾驶员经验等因素。一些学者[4-6]从出租车轨迹数据中提取到大量有历史经验的信息,并基于出租车轨迹的路径规划算法,获取实际行驶过程中的最流行路径。文献[7-8]根据大量的出租车全球定位系统(global positioning system，GPS)数据找出聚集区,确定候选车站集并简化为有效公交车路线,从中选取最理想交通路线。文献[9]通过研究出租车司机经验建立经验知识模型并基于此模型实现经验道路等级的划分,然后结合司机驾驶的经验提出基于出租车司机经验知识建模的路径规划算法。文献[10]基于出租车经验知识利用贝叶斯分类器对路网分层后得到分层路网,然后使用分层路径规划算法实现层次路径规划。文献[11]基于潜能模型并考虑到人口分布、交通路网特征、兴趣点分布等因素,提出城市可达性的计算方法。文献[12]以交通情况和司机行驶信息为基础构建云系统并通过计算得到同时满足个性化和实际情况的最短路径,该系统可以预测未来一段时间内交通情况。文献[13]基于出租车经验知识的基础,提出一种深度Q-learning算法,得到不同时间段内OD(交通起止点)间最快路径。

本文从出租车轨迹数据中筛选到有效的轨迹数据,并将其地图匹配[14-15]到城市道路网中得到车辆行驶路径,通过计算两个道路节点间路径相似度得到相似度均值最大的路径。综合行驶路径数量、路径通行时间和路径长度三个影响因素分析上述路径是否为最流行推荐路径。

1 算法思路

人们出行一般选择距离最短或者时间最短的路径,但出租车司机会在考虑路径通行时间和空间外,把路段拥堵程度、车流量、红绿灯、道路等级等外界因素也考虑在内。能够选择在某一时间段内较通畅且到达目的地时间和路径相对较短的路径。本文通过分析出租车的轨迹数据进一步了解道路网结构,并结合出租车司机的经验知识得到两个道路节点间与其他行驶路径相似度最大的路径,结合行驶路径数量、路径通行时间和路径长度这三个指标综合分析确定上述路径是否为最流行推荐路径。以下是技术路线:

首先,将获取到的原始GPS轨迹点数据进行预处理,从轨迹中剔除噪声数据(包括定位漂移导致的定位异常的轨迹点、不随时间变化的轨迹点和速度为0的轨迹点等)。

然后,在现有道路网的基础上,将筛选后的出租车轨迹点数据匹配到相应路段上,得到出租车行驶路径。

接着,把最大公共子序列作为衡量轨迹间相似性的度量,计算道路节点间所有行驶路径的相似度,得到与其他路径相似度最大的路径,将其初步定位推荐路径。

最后,结合行驶路径数量、路径通行时间和路径长度这三个指标分析上述路径是否为最流行推荐路径。

技术路线如图1所示。

图1 技术路线

2 概念定义

出租车轨迹数据进行挖掘分析前,给出如下定义:

(1)定义1(轨迹)。将移动对象产生的轨迹点按照时间先后顺序排序组成序列,即轨迹Tj={P1,P2,…,Pq}。

(2)定义2(道路网)。道路网是一个图,由道路节点和路段组成。定义为G=(N,S),其中N={N1,N2,…,Nn}是道路网中n个道路节点的集合,S={s1,s2,…,sm}是道路网中m个路段的集合。

(3)定义3(行驶路径)。由一系列连续路段所组成的车辆行驶轨迹称为行驶路径,即R={s1,…,sn}。

(4)定义4(地图匹配)。将一系列有序的轨迹点关联到道路网上形成行驶路径的过程称为地图匹配。

3 出租车路径相似性分析的路径规划

3.1 最大公共子序列计算路径相似度

不同的出租车司机，基于经验知识在任意两个道路节点间，会产生不同的行驶路径,但大多数出租车司机会选择路况较好,距离较短的行驶路径。本文通过计算两个道路节点间所有出租车历史轨迹的相似度,得到除本身外与其他所有行驶路径相似度最大的路径,并对所有行驶路径长度和热点路段图中包含的行驶路径车流量进行分析,进一步判断上述路径是否为最流行推荐路径。

用最长公共子序列衡量轨迹间相似性,最长公共子序列是在一个序列集合中查找所有序列中最长子序列的问题。最长公共子序列只需保持子轨迹与原字符串相对顺序一致,并不要求连续,如两个字符串“abcadf”,“acbad”的最长公共子序列为“abad”。用道路节点代替字符串后得到路径的最长公共子序列,具体步骤如下:

(1)筛选候选路径。出租车轨迹经地图匹配后得到行驶路径,从中筛选道路节点N1与道路节点N2之间的所有行驶路径。

(2)计算任意两个行驶路径之间的最大公共子序列。在此使用动态规划求解最大公共子序列,公式(1)为动态规划的递归方程,二维数组dp[i][j]表示行驶路径L1的i位路段和行驶路径L2的j位之前的最大公共子序列的长度。

(1)

式中,dp[i][j]中最大的数便是L1,L2的最大公共子序列的长度。

(3)计算行驶路径间相似度。两个行驶路径间相似度可由最大公共子序列决定,轨迹间相似性计算公式为

(2)

式中,lLCS为两条行驶路径的最大公共子序列长度;lL1、lL2分别为两条路径长度;msi为两条路径的相似度。

(4)初步得到最流行推荐路径。计算每条行驶路径与其他行驶路径间相似度均值并排序,相似度均值较大的几条路径。计算公式如式(3)

(3)

式中,k为道路节点N1与道路节点N2之间所有行驶路径数量。

3.2 可靠性分析

根据相似度得到相似度均值较大的路径后,结合行驶路径数量、路径通行时间和路径长度进一步分析上述路径中哪一条为最流行推荐路径。给定两个道路节点A,B,从A开始到B终止的路径数量,即行驶路径数量。路径通行时间和路径长度采用同一种无量纲归一化处理,以所有路径中第j条行驶路径Rj={S1,…,Sh}(0

式中,TSh、TS1表示出租车在Sh、S1道路节点处时间;TRj表示两个道路节点间所有路径中第j条路径的通行时间;Min(T)表示路径中通行时间最短路径的时间。路段长度的无量纲归一化处理方法为

(6)

式中,li表示路径中路段长度;Min(E)表示路径中长度最短路径的长度。

根据行驶路径数量和路径通行时间、路段长度的无量纲归一化后的值,根据出租车在两小时内的数据量,设定两个道路节点间行驶路径数量的阈值为K,若行驶路径数量小于K,表明这两个道路节点间样本数量不足,且相似度均值最大的行驶路径不具备代表性;反之,继续分析路径通行时间和长度这2个影响因素,无量纲归一化处理后路径通行时间的值和路径长度的值均在0～1之间,2个值越趋近1,表明路径通行时间越少和路径的长度越短。综合相似度均值和无量纲归一化处理后路径通行时间值和路径长度值,得到最流行推荐路径。

4 实验比较和分析

实验数据主要包括道路网数据和出租车GPS轨迹数据,本文使用的道路数据是南京市交通道路电子地图,路段数为9 332,道路节点数为5 849。出租车GPS轨迹数据为南京市出租车2010年1月19日17:00至19:00的轨迹数据,有约8 000条有效轨迹,约20 200 000个GPS轨迹点,采样时间间隔为30 s。

根据出租车轨迹数量,将两个道路节点间行驶路径数量阈值定为10条。如图2所示,任选两个道路节点,从出租车的经验轨迹数据中提取到的起始和终止道路节点相同行驶路径有10条等于阈值,表明给定的道路节点间的相似度均值最大的路径具有代表性。图2中路径3、4、5表示的是同一条路径。其余每条行驶路径虽有不同,也存在重叠路段。

图2 出租车行驶路径

根据第3章中基于最大公共子序列计算出租车经验路径相似度,得到这两个道路节点内所有行驶路径与其他路径的相似度均值Mavg如表1所示。由表1可以得,与Mavg值超过0.35的路径分别为路径3、4、5、8,其中3、4、5表示的是同一条路径。

为得到最流行推荐路径,需结合路径通行时间和路径长度进行分析,表2为路径行驶时间和路径长度及两者无量纲归一化后结果。由表2可得,对比路径通行时间,路径3的通行时间最短。表示同一条路径的路径4,5通行时间归一化值均大于0.85,表明相比其他路径,路径4,5的通行时间也相对较短。对比路径长度,路径8的长度最短。表示同一条路径的3,4,5长度归一化值为0.98趋近于1,表明路径3,4,5的长度也较短。综合上述影响因素,最流行推荐路径为相似度均值最大的路径3、4、5所表示的同一条路径。

5 结束语

本文通过对出租车采集的历史轨迹数据统计和分析,研究行驶过程中出租车司机对道路路段选择的经验知识,通过计算两个道路节点间所有路径的相似度均值得到相似度均值较大的路径,结合两个道路节点间出租车行驶路径数量、每个路径通行时间和路段长度综合分析得到出租车的最流行推荐路径。本文对南京市道路网和出租车数据进行实验,结果表明,本文路径规划算法得到的最流行推荐路径,代表性强,通行时间和通行距离也较短,更加符合人们认知的出行方式。