I've written some code to deal with this before (in my case, I wrote a distributed timer for cycle races, predicting current rider locations and gaps from sparse user reports). For me, finding nearest point on the segments of the polyline worked, but choosing only vertices would have made the time estimates terrible. Were the points somehow more fixed than that, eg towns/motels on the route?