Map Matching Algorithm Based On Hidden Markov Model and Genetic Algorithm

Gang Wu; Yu Jing Qiu; Guo Ren Wang

doi:10.3969/j.issn.1005-3026.2017.04.004

Map Matching Algorithm Based On Hidden Markov Model and Genetic Algorithm

Gang Wu, Yu Jing Qiu^*, Guo Ren Wang

^*Corresponding author for this work

Northeastern University China

Research output: Contribution to journal › Article › peer-review

11 Citations (Scopus)

Abstract

A new map matching algorithm was proposed on the basis of the hidden Markov model and the genetic algorithm. Firstly, the HMM probability matrix was initialized. Then, the parameters were learned by using the forward-backward algorithm, and a set of road sections was predicted by using the Viterbi algorithm. Finally, taking section sequence as population, the optimal section sequence was obtained by using the genetic algorithm. By using the taxi GPS data from Beijing in 2012 to test the traditional algorithm based on hidden Markov model and the proposed algorithm, the results showed that the traditional algorithm based on hidden Markov model has a matching accuracy below 90% and the proposed algorithm has a matching accuracy above 90%.

Original language	English
Pages (from-to)	472-475
Number of pages	4
Journal	Dongbei Daxue Xuebao/Journal of Northeastern University
Volume	38
Issue number	4
DOIs	https://doi.org/10.3969/j.issn.1005-3026.2017.04.004
Publication status	Published - 1 Apr 2017
Externally published	Yes

Keywords

Genetic algorithm
Hidden Markov model
Map matching
Matching accuracy
Road network data

Access to Document

10.3969/j.issn.1005-3026.2017.04.004

Cite this

@article{52c8bfccfe2640999146e3743df2d577,

title = "Map Matching Algorithm Based On Hidden Markov Model and Genetic Algorithm",

abstract = "A new map matching algorithm was proposed on the basis of the hidden Markov model and the genetic algorithm. Firstly, the HMM probability matrix was initialized. Then, the parameters were learned by using the forward-backward algorithm, and a set of road sections was predicted by using the Viterbi algorithm. Finally, taking section sequence as population, the optimal section sequence was obtained by using the genetic algorithm. By using the taxi GPS data from Beijing in 2012 to test the traditional algorithm based on hidden Markov model and the proposed algorithm, the results showed that the traditional algorithm based on hidden Markov model has a matching accuracy below 90% and the proposed algorithm has a matching accuracy above 90%.",

keywords = "Genetic algorithm, Hidden Markov model, Map matching, Matching accuracy, Road network data",

author = "Gang Wu and Qiu, {Yu Jing} and Wang, {Guo Ren}",

year = "2017",

month = apr,

day = "1",

doi = "10.3969/j.issn.1005-3026.2017.04.004",

language = "English",

volume = "38",

pages = "472--475",

journal = "Dongbei Daxue Xuebao/Journal of Northeastern University",

issn = "1005-3026",

publisher = "Northeast University",

number = "4",

}

TY - JOUR

T1 - Map Matching Algorithm Based On Hidden Markov Model and Genetic Algorithm

AU - Wu, Gang

AU - Qiu, Yu Jing

AU - Wang, Guo Ren

PY - 2017/4/1

Y1 - 2017/4/1

N2 - A new map matching algorithm was proposed on the basis of the hidden Markov model and the genetic algorithm. Firstly, the HMM probability matrix was initialized. Then, the parameters were learned by using the forward-backward algorithm, and a set of road sections was predicted by using the Viterbi algorithm. Finally, taking section sequence as population, the optimal section sequence was obtained by using the genetic algorithm. By using the taxi GPS data from Beijing in 2012 to test the traditional algorithm based on hidden Markov model and the proposed algorithm, the results showed that the traditional algorithm based on hidden Markov model has a matching accuracy below 90% and the proposed algorithm has a matching accuracy above 90%.

AB - A new map matching algorithm was proposed on the basis of the hidden Markov model and the genetic algorithm. Firstly, the HMM probability matrix was initialized. Then, the parameters were learned by using the forward-backward algorithm, and a set of road sections was predicted by using the Viterbi algorithm. Finally, taking section sequence as population, the optimal section sequence was obtained by using the genetic algorithm. By using the taxi GPS data from Beijing in 2012 to test the traditional algorithm based on hidden Markov model and the proposed algorithm, the results showed that the traditional algorithm based on hidden Markov model has a matching accuracy below 90% and the proposed algorithm has a matching accuracy above 90%.

KW - Genetic algorithm

KW - Hidden Markov model

KW - Map matching

KW - Matching accuracy

KW - Road network data

UR - http://www.scopus.com/inward/record.url?scp=85021235725&partnerID=8YFLogxK

U2 - 10.3969/j.issn.1005-3026.2017.04.004

DO - 10.3969/j.issn.1005-3026.2017.04.004

M3 - Article

AN - SCOPUS:85021235725

SN - 1005-3026

VL - 38

SP - 472

EP - 475

JO - Dongbei Daxue Xuebao/Journal of Northeastern University

JF - Dongbei Daxue Xuebao/Journal of Northeastern University

IS - 4

ER -

Map Matching Algorithm Based On Hidden Markov Model and Genetic Algorithm

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this