Ride matching in Google Maps with Rails 3 for a carpooling system

We want to search through carpools to find an optimal carpool whose route passes through the user's location. The data in the carpool is just the start and end points. Assuming the end point is a common end point for the user and the car pool creator, what would be the best way to determine an appropriate carpool for the user? We are using Rails 3. Both Google Maps API v2 an开发者_运维知识库d v3 are possible solutions.

What you really want to know is the detour, both in time and distance. There's no simple way to determine this mathematically from just cooridnates. Luckily, it's trivial to do with a routeplanner. Just calculate both the time with and without waypoint.

If you have a very large set of carpoolers, it helps to start with the ones that are physically closest . Once you get a carpool with a detour of N kilometers, you know that you can exclude all other begin/end pairs where the begin-user-end distance in a straight line is at least N kilometers more than the best route from begin to end. This is the logic behind A*; start with what looks best geometrically so you quickly establish an upper bound and need not spend a lot of work on long detours.