An adaptive Markov chain algorithm applied over map-matching of vehicle trip GPS data
Markov chains have frequently been applied to match the probable routes with a set of GPS trip data that a pilot vehicle is emitting over a specific graph road network. This class of map-matching (MM) algorithms presently demonstrates and involve statistical and ad-hoc measures to drive the Markov c...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2021-07-01
|
| Series: | Geo-spatial Information Science |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1080/10095020.2020.1866956 |
| _version_ | 1819125241220169728 |
|---|---|
| author | Bilge Kaan Karamete Louai Adhami Eli Glaser |
| author_facet | Bilge Kaan Karamete Louai Adhami Eli Glaser |
| author_sort | Bilge Kaan Karamete |
| collection | DOAJ |
| description | Markov chains have frequently been applied to match the probable routes with a set of GPS trip data that a pilot vehicle is emitting over a specific graph road network. This class of map-matching (MM) algorithms presently demonstrates and involve statistical and ad-hoc measures to drive the Markov chain transitional probabilities in picking the best route combinations constrained over the graph road network. In this study, we have devised an adaptive scheme to modify the Markov Chain (MC) kernel window as we move along the GPS samples to reduce the mistakes that can happen by the use of narrower MC widths. The measure for temporarily increasing the MC window width is chosen to be the ratio between the geodesic distance of current route to the actual geodesic distance between each pair of GPS samples. This adaptive use of MC has shown to have hardened the results significantly with tolerable computational cost increase. The details of the overall algorithm are depicted by the example routes extracted from various vehicle trips and the results are shown to validate the usefulness of the algorithm in practice. |
| first_indexed | 2024-12-22T07:37:00Z |
| format | Article |
| id | doaj.art-54a2e29b499445c89fd84597aa83283a |
| institution | Directory Open Access Journal |
| issn | 1009-5020 1993-5153 |
| language | English |
| last_indexed | 2024-12-22T07:37:00Z |
| publishDate | 2021-07-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | Geo-spatial Information Science |
| spelling | doaj.art-54a2e29b499445c89fd84597aa83283a2022-12-21T18:33:52ZengTaylor & Francis GroupGeo-spatial Information Science1009-50201993-51532021-07-0124348449710.1080/10095020.2020.18669561866956An adaptive Markov chain algorithm applied over map-matching of vehicle trip GPS dataBilge Kaan Karamete0Louai Adhami1Eli Glaser2Kinetica DB IncKinetica DB IncKinetica DB IncMarkov chains have frequently been applied to match the probable routes with a set of GPS trip data that a pilot vehicle is emitting over a specific graph road network. This class of map-matching (MM) algorithms presently demonstrates and involve statistical and ad-hoc measures to drive the Markov chain transitional probabilities in picking the best route combinations constrained over the graph road network. In this study, we have devised an adaptive scheme to modify the Markov Chain (MC) kernel window as we move along the GPS samples to reduce the mistakes that can happen by the use of narrower MC widths. The measure for temporarily increasing the MC window width is chosen to be the ratio between the geodesic distance of current route to the actual geodesic distance between each pair of GPS samples. This adaptive use of MC has shown to have hardened the results significantly with tolerable computational cost increase. The details of the overall algorithm are depicted by the example routes extracted from various vehicle trips and the results are shown to validate the usefulness of the algorithm in practice.http://dx.doi.org/10.1080/10095020.2020.1866956hidden markov chain (hmc)map-matching (mm)graph networks |
| spellingShingle | Bilge Kaan Karamete Louai Adhami Eli Glaser An adaptive Markov chain algorithm applied over map-matching of vehicle trip GPS data Geo-spatial Information Science hidden markov chain (hmc) map-matching (mm) graph networks |
| title | An adaptive Markov chain algorithm applied over map-matching of vehicle trip GPS data |
| title_full | An adaptive Markov chain algorithm applied over map-matching of vehicle trip GPS data |
| title_fullStr | An adaptive Markov chain algorithm applied over map-matching of vehicle trip GPS data |
| title_full_unstemmed | An adaptive Markov chain algorithm applied over map-matching of vehicle trip GPS data |
| title_short | An adaptive Markov chain algorithm applied over map-matching of vehicle trip GPS data |
| title_sort | adaptive markov chain algorithm applied over map matching of vehicle trip gps data |
| topic | hidden markov chain (hmc) map-matching (mm) graph networks |
| url | http://dx.doi.org/10.1080/10095020.2020.1866956 |
| work_keys_str_mv | AT bilgekaankaramete anadaptivemarkovchainalgorithmappliedovermapmatchingofvehicletripgpsdata AT louaiadhami anadaptivemarkovchainalgorithmappliedovermapmatchingofvehicletripgpsdata AT eliglaser anadaptivemarkovchainalgorithmappliedovermapmatchingofvehicletripgpsdata AT bilgekaankaramete adaptivemarkovchainalgorithmappliedovermapmatchingofvehicletripgpsdata AT louaiadhami adaptivemarkovchainalgorithmappliedovermapmatchingofvehicletripgpsdata AT eliglaser adaptivemarkovchainalgorithmappliedovermapmatchingofvehicletripgpsdata |