Method and algorithm for map-matching trips to POIs
A method, system and computer program product for map-matching a probe to a point-of-interest (POI) during a trip by a vehicle in a region are disclosed. The method includes identifying POIs in the region; determining, for probes in the region, a latitude location of the probes, a longitude location of the probes and a data collection time stamp for the probes; determining, for each of the probes in the region, a proximity between the probes and the POIs within a predetermined radius of the probes; determining, for each of the POIs, a POI geographic coverage area; calculating an observed POI probability from the proximity and the POI geographic coverage area; and using a Hidden Markov Model to sequentially process the observed POI probability from a predetermined number of probes of the trip and to predict a most likely POI at which the probes are clustered.
1 . A computer-implemented method for map-matching a probe to a point-of-interest (POI) during a trip by a vehicle in a region, the method comprising: identifying one or more POIs in the region; determining, for one or more probes in the region, a latitude location of the one or more probes, a longitude location of the one or more probes and a data collection time stamp for the one or more probes; determining, for each of the one or more probes in the region, a proximity between the one or more probes and the one or more POIs within a predetermined radius of the one or more probes; determining, for each of the one or more POIs, a POI geographic coverage area; calculating an observed POI probability from the proximity and the POI geographic coverage area; and using a machine learning model to sequentially process the observed POI probability from a predetermined number of probes of the trip and to predict a POI at which the one or more probes is clustered.
2 . The method of claim 1 , where using the machine learning model comprises using a Hidden Markov Model (HMM).
3 . The method of claim 1 , where the predetermined number of probes of the trip comprises the first 10 probes of the trip or the last 10 probes of the trip.
4 . The method of claim 1 , where the predetermined radius is 30 meters.
5 . The method of claim 1 , where the POI geographic coverage area comprises a POI polygon area.
6 . The method of claim 2 , where using the HMM further comprises inputting state transition probabilities to the HMM based on probabilities that the vehicles traversed more than one POI during the trip.
7 . The method of claim 1 , where the one or more probes comprise at least one of a GPS device, a mobile wireless device, a wearable device, a vehicle telematics sensor, a cellular geolocation device or a combination thereof.
8 . A system for map-matching a probe to a POI during a trip by a vehicle in a region, comprising: at least one memory configured to store computer executable instructions; and at least one processor configured to execute the computer executable instructions to: identify one or more POIs in the region; determine, for one or more probes in the region, a latitude location of the one or more probes, a longitude location of the one or more probes and a data collection time stamp for the one or more probes; determine, for each of the one or more probes in the region, a proximity between the one or more probes and the one or more POIs within a predetermined radius of the one or more probes; determine, for each of the one or more POIs, a POI geographic coverage area; calculate an observed POI probability from the proximity and the POI geographic coverage area; and use a machine learning model to sequentially process the observed POI probability from a predetermined number of probes of the trip and to predict a POI at which the one or more probes is clustered.
9 . The system of claim 8 , where the computer executable instructions to use the machine learning model comprise computer executable instructions to use a Hidden Markov Model (HMM).
10 . The system of claim 8 , where the predetermined number of probes of the trip comprises the first 10 probes of the trip or the last 10 probes of the trip.
11 . The system of claim 8 , where the predetermined radius is 30 meters.
12 . The system of claim 8 , where the POI geographic coverage area comprises a POI polygon area.
13 . The system of claim 9 , where the computer executable instructions to use the HMM further comprise computer executable instructions to input state transition probabilities to the HMM based on probabilities that the vehicles traversed more than one POI during the trip.
14 . The system of claim 8 , where the one or more probes comprise at least one of a GPS device, a mobile wireless device, a wearable device, a vehicle telematics sensor, a cellular geolocation device or a combination thereof.
15 . A computer program product comprising a non-transitory computer readable medium having stored thereon computer executable instructions, which when executed by one or more processors, cause the one or more processors to carry out operations for map-matching a probe to a POI during a trip by a vehicle in a region, the operations comprising: identifying one or more POIs in the region; determining, for one or more probes in the region, a latitude location of the one or more probes, a longitude location of the one or more probes and a data collection time stamp for the one or more probes; determining, for each of the one or more probes in the region, a proximity between the one or more probes and the one or more POIs within a predetermined radius of the one or more probes; determining, for each of the one or more POIs, a POI geographic coverage area; calculating an observed POI probability from the proximity and the POI geographic coverage area; and using a machine learning model to sequentially process the observed POI probability from a predetermined number of probes of the trip and to predict a POI at which the one or more probes is clustered.
16 . The computer program product of claim 15 , where the operations for using the machine learning model comprise operations for using a Hidden Markov Model (HMM).
17 . The computer program product of claim 15 , where the predetermined number of probes of the trip comprises the first 10 probes of the trip or the last 10 probes of the trip.
18 . The computer program product of claim 15 , where the predetermined radius is 30 meters.
19 . The computer program product of claim 15 , where the POI geographic coverage area comprises a POI polygon area.
20 . The computer program product of claim 16 , where using the HMM further comprises inputting state transition probabilities to the HMM based on probabilities that the vehicles traversed more than one POI during the trip.