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

• The whole architecture was mostly mentioned in previous blog series
  • See Analytics & Cognitive Feature in CVI Series: Part-1 CVI Analytics Overview & Data Schema for Analytics about the data flow
• One point to mention here is Trip Summary (Trip start/end) data which is managed in HBase
  • Actually, this trip summary data is managed on CVI
  • This trip summary data manages the start and end information of each trip
    • start longitude/latitude/time stamp and so on which equivalent to origin information
    • end longitude/latitude/time stamp and so on which equivalent to destination information
  • See Driving Behavior plug-in data model (Restricted content for entitled IBM customers) for the detail of trip summary data

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.
  • CVI has this kind of road network loaded from map data
  • Each link has unique id from L1 to L24
    
    • Actually, each node also has unique id in CVI but they are omitted in this example
  • From position data (longitude/latitude), DMM enriches link information including link id to probe data
    
    • See Analytics & Cognitive Feature in CVI Series: Part-1 CVI Analytics Overview & Data Schema for Analytics about the data flow

• 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
  • See DBScan algorithm
• And we have another threshold if each cluster has minimum number of historical trips
  • See TrajectoryPattern.job on Driver Behavior API to update algorithm parameters
• 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

• Analytics & Cognitive Feature in CVI Series: Part-1 CVI Analytics Overview & Data Schema for Analytics
• Analytics & Cognitive Feature in CVI Series: Part-2 Driving Behavior Analysis

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

#IBMAssetandFacilitiesManagementConnectedVehicleInsights-Public
#Sustainability