I am writing my Bachelor thesis about a Dynamic Carpooling service. It uses air-to-air distances, as I could not find resources to have a system using maps and routings.
I am interested to know if there already exists an algorithm that does the same as mine.
I know that my algorithm is very simple. I just would like to know if I have re-invented the wheel for avoiding to look like an ass in my thesis.
The full pseudocode can be found on my website.
Here is a brief summary of the pseudocode, human readable:
given the rider position and its destination:
- get from database all active trips with a destination contained in a small geo-box centered in the rider destination.
- From the retrieven trips, exclude those in which the driver is closer than the rider to the destination
- From the remaining trips, exclude those in which the driver tends to move away from the rider
- Return the trips
Some words about point 3: for calculating the "proximity factor" of the driver, I get the last N positions (let's say 10) of the driver while he's driving. I compute the distance from those positions to the position of the rider. I then check how many times this set of distances tends to decrease (ie, to get closer to the rider). If this "number of times", called proximity factor, is more than a given tollerance, I assume that the driver is getting closer to the rider.
Thank you very much for your responses.