I need to analyze data uploaded from vehicle GPS devices to detect travel patterns and then attempt to learn about the normal travel patterns for that vehicle so that predictions can be made about maintenance, refueling etc. Some vehicles are domestic (exhibiting normal home->work->home travel patterns) and some are commercial with scheduled routing.
I have loaded the GPS lats and longs to a database, and then constructed an ST_LineString with the data points for each vehicle (approx 1k points per vehicle per day).
Vehicles will never have identical travel patterns (GPS accuracy, irregular ping times etc) and the patterns will be visible as subsets of pings – for example a one hour commute between point A (home) and point B (work) between 8am and 9.30am each morning, Mon-Fri.
Now the difficult part – I am considering the options. I have to write this in a database procedural language using the usual toolbox of procedures, cursors, iteration etc. I could use Python if it is helpful – I’m a database guy trying to think laterally and spatially.
A travel pattern could be identified by
(i) a similar sequence of points that can differ by a tolerance (say +/- 300 meters)
(ii) parking locations – if a car is parked at the same location for 8 hours a day
(iii) temporal- the vehicle starts at trip at 0830 every day, +/- 10 minutes.
I am planning to write a procedure that checks for each of these patterns for each point (or set of n points) by comparing it with all other points (or set of points) by iterating through the pings for each day in sequence.
The easiest use case is to find recurrences of a vehicle parked at the same place each day. Detecting similar movement patterns is more complex. What could be a technique for this?
0
This is a general form of pattern recognition, and pattern recognition is hard – it was under scientific research for years.
I think the first thing you need to do here is to find formal definitions for all “travel patterns” you want to identify – I guess those examples are only the tip of the iceberg. Your definitions (2) and (3) are easy cases, but I guess they are not so interesting.
Case (1) is IMHO not a real pattern definition, but I guess you want to detect a pattern like “the same route is repeated at regular time intervals on a daily or weekly basis”. But here the problem starts – what time intervals do you want to compare? What if the driver makes a detour at some days going out of your 300m radius? Do you want to identify the top 10 routes taken by each car over the year (and why)? Are two routes identical regardless of their time stamp, or should the time stamp matter? Is the direction of the route important, or not?
So my first advice is: start asking yourself the right questions – analyse the problem more in depth, not from a technical point of view (“what things are easy to compare”), but from the domain point of view (“what do I really want to know”)?
One point you mentioned is “maintenance and refueling”. For these things IMHO the routes are typically irrelevant. The general statistical information should be more interesting (how many miles/kilometers per year was the car on the road), the exact routes are neglectable.
For the problem of route comparing, without the temporal component: I would suggest not to compare “single points”. Your points describe a 2D path, and you need a metrics to compare those paths, regardless of the number of points on that paths. There are some scientific papers on that topic, looking at google for “comparing two paths distance” will show up some of them.
Adding the temporal component could be seen as a 3D extension of the 2D problem, but I guess it will be easier when you start with the 2D case, and when you can identify paths which are similar on the plane, you can add some time comparisons afterwards.