Determine what predetermined routes a point is closest to

Question

I have a set of predetermined routes (red) that drivers will take to the same location but with different starting points, n number of miles appart.

The algorithm I'm trying to implement is one where passengers (blue dots) who wish to come along could search using their pick up address and be matched with a driver that will drive closest (no more than y miles out of the driver's way) to them so that they can be picked up.

I had originally thought of approaching this by drawing a polygon using the passenger's location as the centroid, and checking if the polygon intersects with any of the routes. Another way I thought of approaching this is by slicing the routes and checking if the dots land on any slice. These two approaches however might put a notable amount of overhead, specially when scaling to over 500 different routes.

Answer 1

Don't know how many other people will ever need to do this, but I ended up using Google Maps to get a polyline of the route, decoding it into geopoints, saving them into elasticsearch, and then I can find the closest route with a simple geospatial search in elasticsearch.

Answer 2

You can use Map Matching. When a match is retrieved, it returns a path on the road and path network closest to the input traces.

This SO post - Determining path user is on based on GPS location and the given logic in Get closest point to a line might help you.