Simple Map-Matching Algorithm Applied to Intelligent Winter Maintenance Vehicle Data

Abstract

Intelligent winter maintenance vehicles are equipped with automatic vehicle location (AVL) technology, including differential Global Positioning System (DGPS) receivers and various additional sensors that collect equipment status and material use data. DGPS data points are associated with the nearest roadway centerline by calculating minimum perpendicular distances between each roadway centerline representation and the DGPS data points. Highly accurate roadway centerline maps and DGPS measurements are not always available. Thus, spatial mismatches may occur at converging and diverging roadways, divided highways, and intersections. Decision makers use winter maintenance performance measures to evaluate achievement of goals and objectives and to improve winter maintenance operations in public agencies. These performance measures are sensitive to spatial mismatches, which need to be resolved before calculations are done. This paper presents a simple map-matching algorithm that resolves spatial ambiguities by determining the correct roadway centerline on which the vehicle is traveling. The algorithm computes shortest paths between snapped DGPS data points using network topology and turn restrictions. A path is considered viable, and locations for the snapped DGPS data points correct, if similarity exists between values of calculated and recorded vehicle speeds. If a path is not feasible, DGPS points are snapped to alternative roadway centerlines contained within their buffers, shortest paths are recalculated, and speeds are again compared. Examples are presented to illustrate the implementation and effectiveness of the algorithm.

Get full access to this article

View all access options for this article.

References

Fekpe

E. S.

, Windholz

, Beard

, and Novak

. NCHRP Report 506: Quality and Accuracy of Positional Data in Transportation. TRB, National Research Council, Washington, D.C., 2003.

French

Map Matching Origins, Approaches and Applications.

Proc., 2nd International Symposium on Land Vehicle Navigation, 1989, pp. 91–116.

Morisue

, and Ikeda

. Evaluation of Map-Matching Techniques. Vehicle Navigation and Information Systems Conference Record, Toronto, Canada, 1989, pp. 23–28.

Zhao

Vehicle Location and Navigation Systems. Artech House, Inc.,

Norwood, Mass.,

1997.

Czerniak

NCHRP Synthesis of Highway Practice 301: Collecting, Processing, and Integrating GPS Data into GIS. TRB, National Research Council, Washington, D.C., 2002.

White

, Bernstein

, and KornHauser

. Some Map Matching Algorithms for Personal Navigation Assistants. Transportation Research Part C: Emerging Technologies, Vol. 8, No. 1, 2000, pp. 91–108.

Huang

L.-J.

, Kao

W.-W.

, and Oshizawa

. A Fuzzy Logic Based Map-Matching Algorithm for Automotive Navigation Systems. IEEE Round-table Discussion on Fuzzy and Neural Systems and Vehicle Applications. Institute of Industrial Science, Tokyo, Japan, 1991.

Kim

, and Kim

J. H.

. Adaptive Fuzzy-Network-Based C-Measure Map-Matching Algorithm for Car Navigation System. IEEE Transactions on Industrial Electronics, Vol. 48, No. 2, 2001, pp. 432–441.

, Haseyama

, and Kitajima

. A Map Matching Method with the Innovation of the Kalman Filter. Institute of Electronics, Information and Communication Engineers (IEICE) Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. 79-A, No. 11, 1996.

10.

Mar

, and Leu

J.-H.

. Simulations of the Positioning Accuracy of Integrated Vehicular Navigation Systems. IEEE Proceedings: Radar, Sonar and Navigation, Vol. 143, No. 2, 1996, pp. 121–128.

11.

Sun

, and Cannon

. Reliability Analysis of an ITS Navigation System. Proc., IEEE Conference on Intelligent Transportation Systems, 1997, pp. 1040–1046.

12.

Kim

, Lee

G.-I.

, and Lee

J. G.

. Efficient Use of Digital Road Map in Various Positioning for ITS. Record—IEEE PLANS, Position Location and Navigation Symposium, 2000, pp. 170–176.

13.

Zhao

, Ochieng

W. Y.

, Quddus

M. A.

, and Noland

R. B.

. An Extended Kalman Filter Algorithm for Integrating GPS and Low Cost Dead Reckoning System Data for Vehicle Performance and Emissions Monitoring. Journal of Navigation, Vol. 56, 2003, pp. 257–275.

14.

Quddus

M. A.

, Ochieng

W. Y.

, and Zhao

. A General Map Matching Algorithm for Transportation Telematics Applications. GPS Solutions, Vol. 7, No. 3, 2003, pp. 157–167.

15.

Gustafsson

, Gunnarsson

, Bergman

, Forssell

, Jansson

, Karlsson

, and Nordlund

. Particle Filters for Positioning, Navigation, and Tracking. IEEE Transactions on Signal Processing, Vol. 50, No. 2, 2002, pp. 425–437.

16.

Crisan

, and Doucet

. A Survey of Convergence Results on Particle Filtering Methods for Practitioners. IEEE Transactions on Signal Processing, Vol. 50, No. 3, 2002, pp. 736–746.

17.

Lamb

Avoiding Explicit Map Matching in Vehicle Location.

6th ITS World Congress, Toronto, Canada, 1999.

18.

Doherty

S. T.

, Noel

, Gosselin

M.-L.

, Sirois

, and Ueno

. Moving Beyond Observed Outcomes: Integrating Global Positioning Systems and Interactive Computer-Based Travel Behavior Surveys. In Transportation Research Circular E-C026: Personal Travel: The Long and Short of It. TRB, National Research Council, Washington, D.C., 2001, pp. 449–466.

19.

Joshi

A New Approach to Map Matching for In-Vehicle Navigation Systems: The Rotational Variation Metric.

Proc., IEEE Conference on Intelligent Transportation Systems, 2001, pp. 33–38.

20.

Pyo

J. S.

, Dong-Ho

, and Sung

T. K.

. Development of a Map Matching Method Using the Multiple Hypothesis Technique. Proc., IEEE Intelligent Transportation Systems Conference, Oakland, Calif., 2001.

21.

Taylor

, Blewitt

, Steup

, Corbett

, and Car

. Road Reduction Filtering for GPS–GIS Navigation. Transactions in GIS, Vol. 5, No. 3, 2001, pp. 193–207.

22.

Taylor

, Uff

, and Al-Hamadani

GPS Positioning Using Map-Matching Algorithms, Drive Restrictions Information and Road Network Connectivity.

GIS Research in the UK: Proc., GIS Research UK 9th Annual Conference, Glamorgan, Wales, 2001, pp. 114–119.

23.

Greenfeld

J. S.

Matching GPS Observations to Location on a Digital Map. Presented at 81st Annual Meeting of the Transportation Research Board, Washington, D.C., 2002.