PaperlayerView exact revision on arXiv

Source-linked AI summary

A Simple Baseline for Travel Time Estimation using Large-Scale Trip Data

Hongjian Wang, Zhenhui Li, Yu-Hsuan Kuo, Dan Kifer

arXiv:1512.08580v1cs.LGcs.CY

TL;DR

Travel time estimation must predict origin-destination travel times from sparse, large-scale trajectory data, where route-based approaches can require difficult reconstruction and substantial computation. The paper proposes a simple neighbor-based method that uses similar historical trips, temporal and spatial traffic references, and outlier filtering. Across NYC and Shanghai datasets, it outperforms route-based methods and online map services, while offering a fast baseline for travel-time estimation.

  • Problem

    Travel time estimation seeks to predict travel time between an origin and destination from large-scale trajectory data, despite route-based methods' complexity and sparse observations.

  • Method

    The method estimates a query trip using neighboring historical trips, adjusts them for temporal and spatial traffic dynamics, and filters outliers.

  • Results

    The method outperforms Bing Maps by 33% on more than 150 million Manhattan trips, a route-based method by 19%, and Baidu Maps by 17% on Shanghai data, while running 40 times faster than the route-based method.

  • Takeaways & Limitations

    Large-scale historical trip data can support an efficient and effective origin-destination travel-time baseline for applications such as trip planning and urban transportation analysis.

Abstract

from arXiv · show

The increased availability of large-scale trajectory data around the world provides rich information for the study of urban dynamics. For example, New York City Taxi Limousine Commission regularly releases source-destination information about trips in the taxis they regulate. Taxi data provide information about traffic patterns, and thus enable the study of urban flow -- what will traffic between two locations look like at a certain date and time in the future? Existing big data methods try to outdo each other in terms of complexity and algorithmic sophistication. In the spirit of "big data beats algorithms", we present a very simple baseline which outperforms state-of-the-art approaches, including Bing Maps and Baidu Maps (whose APIs permit large scale experimentation). Such a travel time estimation baseline has several important uses, such as navigation (fast travel time estimates can serve as approximate heuristics for A search variants for path finding) and trip planning (which uses operating hours for popular destinations along with travel time estimates to create an itinerary).

I. INTRODUCTION

The paper addresses origin-destination travel time estimation using large-scale historical trip data, avoiding route reconstruction. It argues that a simple neighbor-based baseline can outperform more complex route-based methods and online map services while supporting applications such as trip planning and urban transportation analysis.

  • 173 million NYC taxi trips illustrate how large-scale trajectory data can support urban-flow analysis and individual travel-time prediction.
  • Route-based methods first identify an optimal route and then estimate travel time for its segments, but GPS imprecision makes historical paths difficult to recover.
  • Spatial and temporal sparsity leave many road segments without sufficient observations for accurate, dynamically varying travel-time estimates.
  • The proposed neighbor-based method directly uses trips with similar origins and destinations, avoiding route computation and providing a simple accuracy baseline.
  • Temporal speed references address sparsity by adjusting trips from different times before averaging their travel times.
  • On more than 150 million Manhattan trips, the method outperforms Bing Maps by 33%; on Shanghai data, it outperforms a route-based method by 19% and Baidu Maps by 17%, while running 40 times faster than the route-based method.
  • Although it does not provide specific routes, the method remains useful for trip planning and estimating city commuting efficiency when only travel time is needed.

III. PROBLEM DEFINITION

The problem is to estimate a query trip's travel time from its origin, destination, and departure time using historical trips without intermediate locations. The approach defines spatially similar neighbors, aggregates their travel times, adjusts for temporal traffic variation, and filters noisy records.

  • Each trip is represented by origin, destination, starting time, distance, and travel time, with intermediate locations assumed unavailable.
  • Given a query origin, destination, and departure time, the goal is to estimate its travel time from a historical trip database.
  • Neighboring trips are those whose origins and destinations are spatially close to the query trip, using Euclidean distance.
  • A baseline estimates travel time by averaging the travel times of neighboring trips.
  • Distance-based weights can include a wider range of trips, but this increases computation and does not necessarily improve performance, so the method uses a hard distance threshold.
  • The method weights neighboring trips with scaling factors derived from speed references so their travel times reflect dynamic traffic conditions, while filtering outliers to reduce noise.

IV. CAPTURING THE TEMPORAL DYNAMICS OF TRAFFIC CONDITIONS

The method adjusts neighboring-trip travel times using temporal speed references, addressing traffic variation across trip start times. Experiments show that scaling reduces variance and brings predictions closer to actual travel times.

  • Temporal speed references adjust neighboring-trip travel times to account for different traffic conditions at different starting times.A trip at 2 a.m. should be adjusted relative to a neighboring trip at 5 p.m. because traffic speeds differ substantially.
  • Average-speed ratios provide a feasible approximation of individual-trip speed ratios for scaling neighboring travel times.The fitted relationship is close to y = x, although individual-trip speeds have greater variance than average speeds.
  • Scaling reduces the variance of neighboring-trip travel times and fills the gap between historical trips and rush-hour target trips.Figure 4 illustrates both variance reduction and correction of underestimation for a rush-hour query.
  • The predictor produces estimates close to actual travel times in the evaluation shown in Figure 5.The prediction-versus-actual relationship is close to the identity line.

A. Relative Temporal Speed Reference

The relative temporal speed reference folds time into a periodic window, such as a week, and averages trips within each relative time slot. This provides denser speed estimates while preserving recurring traffic patterns.

  • The method assumes average speed follows a regular daily or weekly pattern and folds time into a relative window of T slots.With hourly slots and a weekly pattern, T = 7 × 24 = 168.
  • Relative speed references represent each time slot by the average speed of trips assigned to that slot.Trips are grouped into the same relative slot as the neighboring trip to compute its reference speed.
  • Folding trips into a relative window alleviates sparsity by providing more observations for each average-speed estimate.The paper also states that the approach reduces computation overhead.
  • The weekly reference shows similar weekday rush-hour patterns, while weekend morning traffic is lighter than usual.The reference is illustrated in Figure 2.

B. Absolute Temporal Speed Reference

The absolute temporal speed reference captures traffic conditions for specific time slots rather than only recurring relative slots. Because future-slot speeds are unknown, the method forecasts them using historical speed patterns and ARIMA.

  • The relative reference is limited when traffic deviates from regular daily or weekly patterns, such as during national holidays.Christmas-week traffic is described as better than usual during daytime on December 25.
  • The absolute reference partitions the timeline into fixed intervals and computes average speed for each historical time slot.The example uses one-hour intervals.
  • Future absolute-slot speeds are estimated from prior speeds, seasonality, and random noise.The forecasting target is the next value in the observed average-speed time series.
  • ARIMA is used to forecast the seasonal difference of the average-speed time series.This models deviations from the periodic pattern rather than applying ARIMA directly to the original speed series.

1) Overview of the ARIMA Model:

The paper uses ARIMA to model and forecast seasonal differences in traffic speed. The model combines autoregressive, integrated, and moving-average components, with orders estimated from time-series observations.

  • ARIMA(p, d, q) models a time series using autoregressive, integrated, and moving-average components.The parameters p, d, and q specify the orders of these three components, respectively.
  • Autocorrelation and partial autocorrelation functions help estimate the ARIMA order parameters from observed time-series values.The model coefficients can then be learned using standard methods such as least squares.
  • Because average speed has a strong weekly pattern, the method first computes seasonal differences and then applies ARIMA to them.The seasonal period T can represent one week.
  • The resulting model is a special case of the broader Seasonal ARIMA framework.
  • For first-order differencing, the model uses Y_t − Y_(t−1) to represent the change between successive seasonal-difference values.The paper treats the final noise term as having zero expectation when forming the estimator.

C. The Effect of Geographic Regions

Traffic patterns vary across geographic region pairs, so region-specific temporal references can improve travel time estimation. The refined references better match actual speed ratios than a single global temporal reference.

  • Motivation: Region pairs exhibit distinct traffic patterns, with residential-to-business regions showing stronger peak-hour variation than tourist areas.For (A, B), average speeds are 22.7 mph at 4:00 a.m. Thursday and 8.5 mph at 12:00 p.m. Wednesday; for (C, D), the corresponding speeds are 11.2 mph and 7.0 mph.
  • Region-specific references: The method partitions the map into K neighborhoods and estimates an average speed V_i→j(s) for each origin-destination neighborhood pair and start time.Each pair-specific reference uses trips whose origins and destinations fall within the corresponding neighborhoods.
  • Evaluation: Region-based temporal references produce a linear-fit slope closer to 1 and a larger R2, indicating better approximation of actual speed ratios.The comparison is made against the temporal reference without region refinement.

D. Time Complexity Analysis

The approach supports offline preprocessing and online neighbor-based estimation, with worst-case online complexity O(α · N). The section also describes filtering anomalous trips using feature correlations and a robust linear model.

  • Preprocessing: Preparing N training trips through raster grid partitioning takes O(N) time and can be performed offline.The experiment uses a 50-meter by 50-meter grid to retrieve neighboring trips efficiently.
  • Online retrieval: Neighbor retrieval takes O(N/h) time under uniform distribution but has worst-case complexity O(α · N) because trip counts across grids follow a long tail.Here, h is the number of grids and α · N is the number of trips in the densest grid; α = 0.01 in NYC.
  • Estimation: After neighbor retrieval, calculating a query trip's travel time takes O(|N(q)|), while temporal speed references can be computed offline.Relative speed references take O(N), and ARIMA prediction takes O((p + q) · d) online time.
  • Complexity result: The overall worst-case online computation is O(α · N), and multithreading can further accelerate batch queries.This bound is driven by retrieving neighbors from the densest grid.
  • Outlier filtering: The outlier filter uses correlations among distance, time, and endpoint separation to identify anomalously fast, slow, or detour trips.A robust linear model assigns each trip an estimated outlier probability and removes the top p·N trips.

1) NYC Taxi:

The NYC evaluation uses a large 2013 taxi dataset, summarizes its trip distributions, and compares several travel-time estimators under error metrics designed to handle anomalous trips.

  • Dataset: The NYC dataset contains 173,179,771 taxi trips from 2013, including 132,766,605 Manhattan trips and 127,534,711 trips after outlier filtering.Each trip records pickup and dropoff locations and times, distance, fare, and related attributes.
  • Dataset statistics: About 56% of NYC trips last less than 10 minutes and about 99% last less than 30 minutes.Mean and median trip times are 636 seconds and 546 seconds, while mean and median distances are 1.935 miles and 1.6 miles.
  • Comparison dataset: The Shanghai dataset contains over 300 million GPS records from 2,600 taxis and yields 5,815,470 processed trips.Trips are extracted from consecutive GPS records with passenger occupancy equal to 1.
  • Methods: Evaluation compares linear regression, neighbor averaging, temporally weighted neighbors, region-aware temporal references, segment-based estimation, and subpath-based estimation.The temporally weighted methods include relative-time and ARIMA-based absolute temporal references.
  • Metrics: Median absolute error and median relative error are included because anomalous trips can distort ordinary error summaries.The median is applied to the vector of per-trip errors.

C. Parameter Setting

The neighbor threshold τ balances estimation confidence against neighbor similarity, with τ=3 selected because it provides broad coverage while maintaining low error. Temporal, spatial, and historical-data choices further affect accuracy and coverage.

  • Threshold selection: MAE is lowest when τ ranges from 3 to 6, reflecting a balance between confidence from more neighbors and errors from less-similar neighbors.
  • Threshold selection: τ=3 is selected because it provides 99% testing-trip coverage while balancing neighbor similarity and estimation confidence.At τ=0, only 32% of trips are predictable; τ=3 is therefore used in subsequent experiments.
  • Model factors: Temporal factors reduce MAE by nearly 20%, with TEMPabs improving over AVG by about 35 seconds.TEMPabs also outperforms TEMPrel because traffic does not strictly follow weekly patterns, including irregular days such as holidays.
  • Model factors: Adding the region factor further improves performance, although sparse regional traffic makes absolute regional references less accurate.Relative regional references can produce better results when they make the data denser.
  • External comparison: TEMPabs+R outperforms BING by 67 seconds on 260k testing trips.BING underestimates 64.53% of trips without traffic information and overestimates 75.02% when queried with matching time and weekday conditions.
  • Training-data size: Using one month of training data is sufficient for stable performance, while coverage increases from 95.16% with one week to 99.20% with one month.Additional data reduce MAE, but gains become less obvious beyond one month in this experimental setting.

3) Performance w.r.t. trip features.:

Performance varies with trip duration, distance, and neighbor count because these factors affect dynamic sensitivity, available neighbors, and the relationship between absolute and relative error. Spatial weighting of neighbors does not improve the evaluated method.

  • Trip time: Longer trips have higher MAEs, while MREs are high for both short and long trips.Short trips are more sensitive to dynamic conditions such as traffic lights, whereas long trips usually have fewer neighbors.
  • Trip distance: TEMPrel+R becomes worse than AVG for trips longer than 8 miles because long-distance trips have fewer neighboring trips.
  • Neighbor count: MAEs decrease as the number of neighbors increases, but MREs increase because short trips tend to have more neighbors and higher relative errors.
  • Spatial weighting: Adding endpoint-distance weights increases TEMPabs+R MAE from 107.705s to 112.392s on 500k trips.The result suggests that assigning neighbor weights from endpoint distances requires more careful design.
  • Shanghai evaluation: The Shanghai comparison evaluates neighbor-based, SEGMENT, SUBPATH, AVG, and Baidu methods on a testing set of 2,138 trips.The testing set is adjusted to reduce bias caused by selecting trips with complete segment values.
  • Shanghai evaluation: TEMPrel is 21 seconds better than SUBPATH in MAE, while AVG is 17 seconds better than BAIDU.The neighbor-based method significantly outperforms the other evaluated methods in Table II.
  • Shanghai evaluation: Shanghai results omit TEMPrel+R and TEMPabs+R because the dataset is substantially sparser than the NYC data.TEMPabs is also omitted because the two-month Shanghai data contain missing days needed for complete ARIMA estimation.

2) Applicability of Segment-based Method and Neighbor-based Method:

The neighbor-based method is more applicable than segment-based estimation when historical trajectories are sparse or endpoint-only, while filtering outliers improves reliability and the method supports fast online queries.

  • Applicability: 49.9% of Shanghai trips have at least one neighbor, compared with 12.5% having historical values for every road segment.Among 435,887 trips, 217,585 satisfy the neighbor condition, whereas only 54,530 satisfy the segment condition.
  • Applicability: Segment-based estimation requires historical data for every individual road segment, whereas neighbor-based estimation requires only one neighboring trip.
  • Outlier filtering: Outliers reduce estimation accuracy when present in training data and make evaluation less reliable when present in testing trips.The paper estimates that 7% of NYC records are outliers after applying several filters.
  • Outlier filtering: The NYC outlier study identifies 6.36% anomalous training trips and 7.00% anomalous testing trips.
  • Runtime: The online query time is 1.505 ms per trip on average and can reach 0.26 ms per trip with eight threads.Neighbor finding is the most time-consuming online component, while estimation takes 0.02 ms with eight threads.
  • Overall scope: The method combines neighboring historical trips with temporal and spatial traffic factors and outlier filtering across two large real-world datasets.
Loading 1512.08580v1…