IBM IoT Connected Vehicle Insights - Public

Analytics & Cognitive Feature in CVI Series: Part-3 Trajectory Pattern Analysis

By SHOICHIRO WATANABE posted Mon October 19, 2020 12:13 AM

  
Mark as Inappropriate

Analytics & Cognitive Feature in CVI Series: Part-3 Trajectory Pattern Analysis


Trajectory pattern analysis overview

  • You can identify and analyze Origin/Destination (O/D) and route patterns from historical driving trips.
    • Identify driver’s mobility pattern in terms of origin location/area and destination location/area with temporal clustering 
    • Identify driver’s mobility pattern in terms of trajectory routes the driver usually take
  • The huge amount of historical trajectory data could be useful for interesting business use cases on the basis of trajectory pattern analysis, for example
    • Driving risk assessment in insurance industry
    • Car pooling / sharing in the smarter city
    • Route monitoring and recommendation in fleet management


Trajectory pattern example

  • The following diagram shows a simple example of the O/D and route patterns of a vehicle (vehicle-001) taken from historical trips. In this example, Trajectory Pattern Analysis identifies two O/D patterns:
    • An O/D pattern from Home (Origin-1) to Office (Destination-1) that has two route patterns.
      • One route is mined from 36 historical trips.
      • Another route is mined from 24 historical trips.
    • An O/D pattern from Home (Origin-1) to Shopping mall (Destination-2) that has one route pattern.
      • Another route is mined from 12 historical trips.
  • On the other hand, the route from Home (Origin-1) to Gas station (Destination-3) is not identified as patterned route. This is because there does not exist enough historical trips (in this case, there are only 2 historical trips).


Driving diversity metrics

Trajectory Pattern Analysis also calculates some driving diversity metrics for each vehicle as listed in the following table. You can use these metrics to judge the driving characteristics of a driver.
Metrics name Description
Rare O/D ratio The ratio of the number of trips that are not covered by O/D patterns to the total number of input trips.
Rare mileage ratio The ratio of the mileage that is not covered by route patterns to the total mileage of the input trips.
Rare trip ratio The ratio of the number of trips that are not covered by route patterns to the total number of input trips.

Architecture of Trajectory Pattern Analysis



Algorithm overview: how to extract trajectory pattern

O/D (Origin/Destination) pattern

  • Firstly, historical trips are clustered based on O/D similarity per vehicle
    • Origin is equivalent to start of each trip and destination is equivalent to end of each trip
  • O/D similarity is calculated by time stamp and position (longitude/latitude) data
    • Time difference of origin's (start's) time stamp
    • Spatial distance between origin's (start's) longitude/latitude and destination's (end's) longitude/latitude
    • Start/end information is managed on Trip Summary (Trip start/end) in HBase

Route pattern

  • Each extracted O/D pattern include multiple historical trips
    • Actual historical data is managed on Historical Probe in HBase
  • Then, included historical trips are clustered into patterned route based on route similarity
  • Route similarity
    • Route similarity between 2 trips (One is X and another is Y) is roughly represented by this formula:
      • Intersection(Trip-X, Trip-Y) / Sum(Trip-X, Trip-Y)
  • In below diagram, there are total 24 links and 14 nodes as simplified example.


  • As a simplified example, we assume 4 historical trips in a O/D pattern. And each historical trip (Trip-1~Trip4) has each route represented by unique link id which can be converted from probe data
    • Trip-1: L1, L6, L11, L17, L22
    • Trip-2: L1, L6, L11, L17, L20, L23
    • Trip-3: L2, L7, L12, L18, L23
    • Trip-4: L3, L8, L10, L12, L18, L23

  • Therefore, the similarity between 2 trips are roughly calculated as follows
    • Trip-1 and Trip-2 similarity
      • Intersection(Trip-1,Trip-2)/Sum(Trip-1,Trip-2) = (L1,L6,L11,L17)/(L1,L6,L11,L17,L20,L22,L23) = 4/7 = 0.57
    • Trip-1 and Trip-3 similarity
      • Intersection(Trip-1,Trip-3)/Sum(Trip-1,Trip-3) = 0 (no intersection)
    • Trip-1 and Trip-4 similarity
      • Intersection(Trip-1,Trip-4)/Sum(Trip-1,Trip-4) = 0 (no intersection)
    • Trip-2 and Trip-3 similarity
      • Intersection(Trip-2,Trip-3)/Sum(Trip-2,Trip-3) = (L23)/(L1,L2,L6,L7,L11,L12,L17,L18,L20,L23) = 1/10 = 0.10
    • Trip-2 and Trip-4 similarity
      • Intersection(Trip-2,Trip-4)/Sum(Trip-2,Trip-4) = (L23)/(L1,L3,L6,L8,L10,L11,L12,L17,L18,L20,L23) = 1/11 = 0.09
    • Trip-3 and Trip-4 similarity
      • Intersection(Trip-3,Trip-4)/Sum(Trip-3,Trip-4) = (L12,L18,L23)/(L2,L3,L7,L8,L10,L12,L18,L23) = 3/8 = 0.37

  • In trajectory pattern analysis, we define above similarities and utilize DBScan algorithm to execute clustering
  • And we have another threshold if each cluster has minimum number of historical trips
  • If each cluster has enough number of historical trips, it is considered to be a patterned O/D and a patterned route
    • In this example, Trip-1 and Trip-2 could be one cluster (=one patterned route) and Trip-3 and Trip-4 could be another cluster (=another patterned route) if the minimum route similarity threshold is set to 0.3 and the minimum number of trips is set to 2

Summary

  • Trajectory pattern analysis can extract O/D patterns and route patterns from historical driving trips
  • Trajectory pattern analysis can calculate driving diversity metrics to judge the driving characteristics of each driver

References

Notice

  • Information in this blog is based on CVI SaaS V3.1. Information is subject to change in the future.

Revision History

  • 2020-10-19: Initial release
0 comments
12 views

Permalink