Find best matching routes from GPS data

I'm making an application where users can save GPS data from phone to server when they travel their everyday routes. For example they are heading from home to work. GPS data is stored in a database.

Now, user wants to know maybe there's more people who travels this route too. I want to compare different users routes and give to user for example 3-5 best matches from other users routes.

Important is compare the whole trip, because users can join their routes and go work together from starting at some point not just from beginning and end. Also I think important is the destinatio开发者_开发问答n point from the users view, who is searching other users routes. Other user route must be near by the searchers route end.

There are two factors - time and location. One user drives with a car and another walks and takes a bus for example. The one who walks starts his trip earlier, another later, because he travels this route faster. In one point at certain time their routes are matching.

How can be routes compared? Is there algorithm(s) for that? Do I need to compare every point in a route?

Essentially you are talking about a combination of routing algorithms and traveling-sales-man

The most common routing algorithm was invented by Dijkstra some 50 years ago, and calculate the best way of getting from point a to point b in a directed network -- in routing applications that means that each road is represented as a edge in the network, and where each edge is associated with a "cost" i.e. the time it take to travel down the road, or the average speed, or in your case it would be the number of people traveling on that route.

The Traveling Sales Man is a slightly different but also related, trying to optimize for the number of nodes visited -- in your case it is probably solving the opposite as it is trying to maximize the number of cities (edge-intersection nodes) while minimizing the cost of traveling to all the nodes -- worth understanding if you want to solve this problem

See GIS - it's a (HUGE) field of study - very interesting but very intense

I think what you would have to do is to convert the GPS co-ordinates that you get from the phone, into routes. Have a look at this Open Route Service which is part of the Open Street Map project.

Once you have each person's latitude and longitude converted to a common set of routes, then it will be easier comparing their paths to see if they have something in common. You could also do things like search for alternate routes. Perhaps one person by traveling a couple of extra mile/km can travel together with another group of 4-5 people going in basically the same direction. Things like that.