# How to derive vehicle paths from timestamped location data?

I've got a bunch of location data for snow plows. There's a unique id for every plow, a timestamp, and x & y coordinates.

Instead of knowing where hundreds street plows were at one minute intervals, I'd like to know which streets have been plowed.

I know there are ways of turning points to polylines, but does anybody know of a method to snap the points to the street grid? In other words, of deriving vehicle paths that hug the streets?

The reason I think that turning points to polylines probably isn't enough is because I only have location data for every plow every 60 seconds. This means there aren't coordinate points for when plows were turning at certain intersection, so if you just drew lines between points some of them would cut through blocks.

• This is an interesting problem. The deal is that between 60 seconds the plow can go through some streets. I would suggest connection the points and intersecting those with polylines, but that may give you an absurd result, showing way more plowing then what really occurred. – George Silva Jan 16 '12 at 3:14
• How fast do the snowplows travel? How long are the streets they plough? Just wondering how many street segments would get missed between points. – Simbamangu Jan 16 '12 at 4:29
• Do the ploughs have a 'route' per se? – Hairy Jan 16 '12 at 8:51

The usual approach consists of two steps:

1. Map matching

The process of "snapping" the vehicle location to the street geometries. The trivial approach is to snap the vehicle location to the nearest point on the nearest road geometry. (There are more sophisticated approaches, which I'm sure you can google easily.)

2. Routing

After map matching, you can route between two successive points. Here again, the easiest approach is to find the shortest path. This route can tell you which roads have been plowed and when.

For the case of low-sampling rate map-matching, I would check out this paper in which the authors use a database of previously observed trajectories to help identify 'likely paths'. Its based on the idea that people are more likely to traverse popular paths.

If you don't have data available to use, a simpler approach is given in this paper for the same problem (i.e. low sampling rate). Although I don't think its never stated explicitly, the authors use a hidden markov model and identify the most likely path. Their model is pretty simple: observations are normally distributed about a road segment, transitions between roads are based on a weighted distance between segments.

Lastly, this question and its answers may also be of interest to you.