4

It is a real world use case. For example, a route from place A to place B can be different series of lat, lng points - the different trips though they are exactly the same sequence from Street x and then Road y then High way z.

The differences are the locations are reported in different time (for example each trip reports the location 1 minute) and the Vehicles appear in the different lane of the same street.

So, do you have some ideas about how to compute the similarity of two different trips belong to the same route (kinds of mapping different trips to the same route ).

cdhit
  • 171
  • 3
  • Are you only interested in similarity of routes between the same points A and B? What should the similarity be to a route from A through B and on to C? What's the purpose of this similarity metric: a fast admissible heuristic e.g. for A* search, or a precise numerical value? How many digits precision do you have on the coordinates - differential GPS gives 5 dps / 1m resolution. What's the similarity of a route B-A to a route A-B: 0, -1, or something else? – smci Sep 08 '16 at 19:24

2 Answers2

1

I would go about this problem using the following approach:

  1. Create a poly-line for the baseline trip.
  2. Create a buffer zone (closed polygon) around this poly-line using a small radius, say 20 meters.
  3. Using the points in the second trip, calculate the fraction of points that lie outside the buffer zone.

A fraction of zero means that all points from the second trip lie inside the first trip's buffer zone, while a fraction of one means that all lie outside.

You can use this fraction as a measure of dissimilarity, where 1 means that both trips are completely dissimilar and 0 means completely similar (within the given buffer radius). For completeness, you might want to reverse the poly-line roles and calculate the "reverse" similarity. Your final similarity score could then be the product of both.

I usually implement my algorithms in C# using .NET and for these purposes I use Microsoft's System.Spatial NuGet package. Here you can find methods like STBuffer and STContains that will greatly help to implement this.

João Paulo Figueira
  • 31
  • 3
  • I think, it would be useful also to add distances between two start points, and the same for finish. To avoid cases, when one route is a subset of another, or a way back. – sobach Sep 08 '16 at 15:30
0

If I correctly understood your problem: you have a set of routes between the same two start and destination locations, and each route is described as a set of (lat, lon, time) tuples.

In order to compute the distance between two routes, one possibility would be to apply a variant of the edit distance between strings. This algorithm computes the distance between two strings as the amount of string operations (edit, remove, add letters) required to transform the first string into the second one.

You just have to come up with a set of "route operations", and the cost of each of these operations (add point routes, remove point routes, replace one point route by another one, and so on).

Pablo Suau
  • 1,767
  • 1
  • 13
  • 20
  • Sorry, I do not quite understand your thoughts. What I am thinking is if I was given a route task, like from location A, pick up a child and go along with street B to the intersection C and turn left and continue along the Street D until the destination. And then I got the real (latitude, longitude) points that how a person run this task, how good this person finish the routed task? use the similarity to describe how good he finish the task. – cdhit Jul 06 '16 at 22:13
  • Did you already read about string edit distance? – Pablo Suau Jul 07 '16 at 08:55
  • I think string edit distance may not apply for this one, because two routes may be similar but the points we got are totally different because they are discrete points on the route. – cdhit Jul 08 '16 at 00:27
  • 1
    Could you please give us a more specific example of two routes from your real data which you would like to compare in terms of distance? – Pablo Suau Jul 08 '16 at 09:05