Global Positioning System Reference
In-Depth Information
3. Decision-rule topological map-matching algorithm
3.1 Description
The decision-rule topological map-matching algorithm determines the correct roadway
centerline for vehicle travel by obtaining feasible shortest paths between snapped GPS data
points in post-processing mode. The algorithm selects all roadways within a buffer around a
GPS data point and snaps the point to the closest roadway by obtaining the minimum
perpendicular distance from the data point to each roadway. Figure 3 illustrates that GPS
data points 1 and 2 (shown as circles) are snapped to ramp 2 because it is the closest
roadway contained with the buffers around the points. Subsequently, the shortest path
(displayed with a bold arrow) is obtained between the two snapped GPS data points S1 and
S2 (shown as squares). Only paths that follow allowable traffic directions and allowable
turns are employed. The travel speed between these two snapped GPS points is determined
by the length of the shortest path and the difference in time stamps for the points. The
computed speed is compared to the average of the speeds at the data points collected by the
vehicle while traveling. If the computed speed is within a specified tolerance of the average
recorded speed, then the obtained shortest path is viable and the snapped locations for
points 1 and 2 are accepted as correct.
GPS Data Point
Nearest
Perpendicular Road
Point
Fig. 3. Example of Snapping to the Correct Roadway for Two GPS Data Points Using the
Map-Matching Algorithm
The map-matching algorithm advances to GPS data point 3, snaps this point to the closest
roadway centerline within its buffer, and calculates the shortest path between snapped
point S2 and the newly-snapped GPS data point S3. If the path between S2 and S3 is not
feasible because the speed comparison yields a large disparity, then the algorithm
determines if feasible routes exist between the preceding and subsequent points bounding
the GPS data points of concern, as illustrated in the example of Figure 4. This example
shows that there is no feasible path between snapped points S2 and S3 when network
topology and turn restrictions are employed. Therefore, the map-matching algorithm looks
Search WWH ::
Custom Search