Travel time estimation of a path using sparse trajectories
Travel time estimation of a path using sparse trajectories
复制标题
DOI：
10.1145/2623330.2623656
复制
发表时间：
2014-08
期刊：
影响因子：
--
通讯作者：
Yilun Wang;Yu Zheng;Yexiang Xue
中科院分区：
文献类型：
--
作者：
Yilun Wang;Yu Zheng;Yexiang Xue
在本文中，我们提出了一个城市范围内的实时模型，用于估计行程时间的任何路径（表示为一个序列的连接路段）在真实的时间在一个城市，根据GPS轨迹的车辆在当前的时隙和一段时间的历史，以及地图数据源。虽然这在许多流量监控和路由系统中是一项战略上重要的任务，但由于以下三个挑战，该问题尚未得到很好的解决。第一个是数据稀疏性问题，即，在当前时隙中，许多路段可能不被任何装备有GPS的车辆行驶。在大多数情况下，我们也无法找到一个精确遍历查询路径的轨迹。第二，对于具有轨迹的路径的片段，它们是使用（或组合）轨迹来估计对应的行进时间的多种方式。找到最佳组合是一个具有挑战性的问题，受制于路径的长度和穿过该路径的轨迹的数量之间的权衡（即，支持）。第三，我们需要即时回答用户可能在给定城市的任何部分发生的查询。这需要一个高效、可扩展和有效的解决方案，可以实现全市范围的实时旅行时间估计。为了解决这些问题，我们用三维张量来模拟驾驶员在不同路段、不同时段的行程时间。结合从轨迹和地图数据中学习的地理空间，时间和历史背景，我们通过上下文感知的张量分解方法填充张量的缺失值。然后，我们设计并证明了一个目标函数来模拟上述权衡，我们找到了最佳的串联轨迹估计通过动态规划解决方案。此外，我们建议使用频繁的轨迹模式（从历史轨迹挖掘），按比例缩小的候选人的级联和后缀树为基础的索引，以管理在当前时隙接收的轨迹。我们基于大量的实验来评估我们的方法，使用超过32，000辆出租车在两个月内生成的GPS轨迹。结果表明，我们的方法超越基线方法的有效性，效率和可扩展性。
In this paper, we propose a citywide and real-time model for estimating the travel time of any path (represented as a sequence of connected road segments) in real time in a city, based on the GPS trajectories of vehicles received in current time slots and over a period of history as well as map data sources. Though this is a strategically important task in many traffic monitoring and routing systems, the problem has not been well solved yet given the following three challenges. The first is the data sparsity problem, i.e., many road segments may not be traveled by any GPS-equipped vehicles in present time slot. In most cases, we cannot find a trajectory exactly traversing a query path either. Second, for the fragment of a path with trajectories, they are multiple ways of using (or combining) the trajectories to estimate the corresponding travel time. Finding an optimal combination is a challenging problem, subject to a tradeoff between the length of a path and the number of trajectories traversing the path (i.e., support). Third, we need to instantly answer users' queries which may occur in any part of a given city. This calls for an efficient, scalable and effective solution that can enable a citywide and real-time travel time estimation. To address these challenges, we model different drivers' travel times on different road segments in different time slots with a three dimension tensor. Combined with geospatial, temporal and historical contexts learned from trajectories and map data, we fill in the tensor's missing values through a context-aware tensor decomposition approach. We then devise and prove an object function to model the aforementioned tradeoff, with which we find the most optimal concatenation of trajectories for an estimate through a dynamic programming solution. In addition, we propose using frequent trajectory patterns (mined from historical trajectories) to scale down the candidates of concatenation and a suffix-tree-based index to manage the trajectories received in the present time slot. We evaluate our method based on extensive experiments, using GPS trajectories generated by more than 32,000 taxis over a period of two months. The results demonstrate the effectiveness, efficiency and scalability of our method beyond baseline approaches.