Making GPS Data Usable: TollGuru’s Advanced Map Matching Algorithm

A city’s skyline stretches out, each building telling its own tale of ambition and progress. Within an iconic tower, a product manager stands, gazing at screens awash with a sea of GPS tracks, each a lifeline in the vast expanse of logistics. This isn’t just about tracking vehicles to know their real-time locations. It’s about upholding commitments and ensuring transparency.

In the pulsating heart of the city’s logistics, InDrive’s bid-based pricing models hinge on precise toll expenses.
Trucking executives, custodians of vast fleets, grapple with the colossal task of ensuring shippers pay their exact toll amounts. Every cent counts, and every route taken is a piece of the financial puzzle.
In a different part of the city, the Revel engineer’s desk is a hive of activity. Drivers crisscrossing the cityscape rely on Revel to ensure they’re reimbursed for every toll paid.
Central to all these stories is one truth: the sanctity of the route taken. It’s not about the start or the end or the predicted route. It is about the route taken — every entrance, every exit, and the road in between. It’s about capturing the very essence of the journey, ensuring that mileage, insurance claims, tolls and fuel expenses align perfectly with the road traveled.
And in this intricate ballet of data, logistics, and finance, TollGuru orchestrates the symphony, ensuring that every movement, every cost, is validated with unerring precision.

Let’s dive into the intricacies of TollGuru map matching algorithm.

Hidden Markov Model (HMM): The Backbone of Map Matching

HMMs and Viterbi algorithms are to TollGuru map matching what foundations are to a skyscraper. They are used to predict a vehicle’s probable road path using the improved GPS data.

In our initial explorations with customer data, we saw that multi-path propagation (signals bouncing off buildings leading to inaccurate GPS points) poses significant challenges for map matching in urban areas (urban canyons). Similarly low sampling is a challenge in tunnels, etc. We found that the HMM can help mitigate some of these challenges by considering the likelihood of transitions between road segments. HMM-based map-matching exploits the Viterbi algorithm to find the optimized road link sequence.

Here are the states and observations in map matching context:

• Roads are the hidden actors (states)
• GPS points, the observable outcomes (observations)
• Through iterative processes, HMMs forecast the most likely route.

For the tech enthusiasts, here’s a quick dive into the algorithm details:

• Observation Sequence O=o₁,o₂. . .oₜ where o are the GPS traces
• State Sequence S=s₁,s₂. . .sₜ where s are the road segments and t is the total number of segments. We build a graph from the OSM road network with nodes and edges. Nodes around the observations are the potential candidates for states.
• Emission Probability P(oₜ | sₜ) — The likelihood that a given GPS point oₜ is observed on the road segment sₜ.
  - This probability is influenced by the distance between the road segment and the GPS point, as road segments considerably distant from a GPS point are less likely to produce that GPS observation
  - To account for GPS inaccuracies, we factor in the error radius for each observation. Our approach involves calculating the emission probability based on the nearest road segment, while considering GPS errors as Gaussian, providing a more accurate representation of real-world GPS data
• Transition Probability P( sₜ₊₁| sₜ) — The likelihood of moving from one road segment one road segment sₜ to another road segment sₜ₊₁.
  - It is determined by considering the distance between these segments, with closer segments having higher probabilities.
  - We also factor in timestamps, ensuring that only feasible transitions within a time frame are considered, thus improving the accuracy of the map matching process.
• Viterbi is a recursive programming algorithm for finding the most likely sequence of hidden states
  - The objective is to find the actual road segments that have the maximum probability given the observations.
  - Vₜ,ₖ = max(Vₜ₋₁,ₖ x P(s | sₜ) P(oₜ | sₜ) ) Here Vₜ,ₖ is the probability of the most probable state sequence responsible for the first t observations that have k as its final state.

TollGuru Enhancement to the Base Model

We improve the base model by including multi-dimensional emission probabilities, context-aware transition probabilities and using updated maps.

In order to compute emission probabilities, TollGuru incorporates multi-dimensional emission probabilities — information on vehicle heading direction, road directionality (determining whether a road is bidirectional or unidirectional), and distance.

TollGuru improves precision by anchoring transition probabilities to road topology. Transition values are modulated based on whether GPS points lie on the same road or transition between different road segments.

TollGuru uses automated pipelines for ingesting daily OpenStreetMap (OSM) changes, ensuring up-to-date road information. Using the latest map data allows TollGuru to match against the latest road topology.

Accuracy: Comparing TollGuru map match results

While the base map matched algorithms have been found to perform extremely well by many researchers, we found that the enhanced TollGuru algorithm outperforms commercially available algorithms from other mapping providers.

In the first example, we compare map matched routes from one of the most popular commercial mapping services with TollGuru. In this example, the mapping service adds a route that was not traversed by a driver. There is a toll plaza on the route and if this route is used as a basis, an incorrect toll is calculated. In other words, wrong map matching leads to a false positive toll scenario.

Example 1: New Jersey Turnpike, New Jersey

A driver traveling on NJ Turnpike took a break at a rest area, before continuing along the turnpike. You can correctly map-matched route on the left in the following figure.

TollGuru map matching (left) creates accurate route leading to accurate toll, fuel, and distance calculations

The mapping service on the other hand generates a route that leads the driver to exit through a toll plaza and return back to the rest area. In order to return to the rest area, the route covers a lane that is not accessible to the general public. This resulted in an incorrect toll calculation.

The following figure shows both the mapmatched routes (TollGuru — orange color, mapping service- purple color) on the same map. As you can imagine, wrong map matching leads to higher distance (mileage), higher fuel consumption estimate and wrong toll expenses.

Map-matched routes from TollGuru (orange) and mapping service (purple)

Original GPS tracks shows that the driver passed through rest area on to NJ Turnpike

Example 2: Tri-state Tollway, Illinois

In the second example, the mapping service doesn’t route exit to the correct lane leading to missing out on a toll. It is an example of False Negative.

As you can see from the GPS track, the driver traveling along the Tri-state Tollway exits near Halstead St but continues straight and encounters a toll booth (see image below).

GPS track shows that the driver exits mainline but doesn’t exit the toll road

As you can see in the image below, the mapping service, map matched the GPS points to the mainline and resulted in missing the toll location. The TollGuru map matching provides the correct route and successfully encountered the toll booth.

Map-matched routes from the mapping service and TollGuru

You can see the impact of wrong map matching in the image below. While TollGuru map matched route led to correct toll calculations, the map matched route from the mapping service led to a False Negative and wrong reimbursement to a driver.

TollGuru route (left) follows the actual route leading to accurate toll calculations

Let’s wrap up with our recommendations to collect better GPS data

Recommendations for Better GPS Data

Based on our experience, we suggest that the GPS device has a clear line of sight to the sky. But if possible, balance frequency with data size. We recommend avoiding limitations with time based sampling or distance based sampling methods. If possible, use better algorithms to collect GPS data such as the Ramer-Douglas-Peucker algorithm.

However, many of our customers use third-party services to collect, process and provide GPS data. They do not have a way to control the quality of the GPS data

How does TollGuru deal with bad GPS data

We employ several automated methods to make GPS data better before using the map matching algorithms.

TollGuru uses advanced signal processing methods — wavelet decomposition to decompose the signal to isolate and reduce noise, polynomial regression to smoothen trajectory paths — to refine GPS data. We also use statistical methods and density-based spatial clustering (e.g., DBSCAN) to identify and remove anomalous readings. This is especially useful for dealing with clusters.

Further, we consider the timestamps and standard deviation of the GPS measurement to ignore outliers from wrong GPS measurements. If a point is inaccessible within the time interval or if it doesn’t lie within the standard error, it’s ignored.

For GPS data that contains measurements such as vehicle speeds we use Kalman filters to predict and correct GPS states (position, velocity) to optimize the trajectory estimation and reduce noise.

These approaches make noisy GPS data better for TollGuru algorithms that use Hidden Markov Models combined with Viterbi algorithms as a base.

Conclusion

We started amidst a city skyline, emblematic of ambition and progress. The stakes? A ride-hails’ bid accuracy, trucking fleet managers cost allocations, and a ride-share accurate driver reimbursement. For all this to work, we need better map matched routes. TollGuru fills the gap. If your organization needs an unparalleled precision in map matching, reach out to TollGuru. Let us be the craftsman that shapes your narratives with unmatched accuracy. Your journey deserves nothing less.

Don’t get trolled by tolls: Avoid common polyline endpoint pitfalls

Time-Aware Polyline Endpoints: Updated Toll Polyline API for Accurate Tolls