How to figure out the order of GPS coordinates with minimal distances?

l1nuxfr3@k · 2017-04-29 16:04:32

Hello Archers! I am working on something here and I would like to ask if somebody knows an algorithm that could help me solve one of my problems. I have a bunch of GPS coordinates and those represent some bus stations I have no idea of how all of them interact with each other. The only thing that I know, next to the coordinates is that a bus must pass through all of them. It's tricky because, the database that I have is huge but not in order and there is no way for me to physically rearrange this. I must figure out the ORDER of those stations! What I did so far is:

I've created a list of all of the stations that I need
I ran an algorithm that implements Haversine formula and runs a "for-each" loop through all of the stations to determinate the distance between the target station and ALL OTHER stations (basically, a loop which iterates through all of the stations and for each of them measures the distance to all of the other stations)
For the each of the stations, I've generated a list of distances which I've sorted in respect of the distance
Grabbed the first two candidates from the list of distances (those with lowest distance)

I know that this algorithm is a bit "vague" but I've tried to get the two closest neighbors of all of the stations in a route.
I believe there are many issues with this approach, especially at the last step that I've described. Since the Haversine formula doesn't say whether the neighbor station is "left" or "right" or somewhere else relative to the target station, I get absolute values of distances and I have no idea if the first two candidates are valid. I could try filtering this list with coordinates but it gets too complex.

Is there a better approach to this problem? And, again, what I am actually trying to ask here is: "is there a way to programmatically figure out the correct order of elements, just by knowing their GPS coordinates and the fact that you ask for such connections where the distance of the two adjacent stations is minimal?"

After I get the actual connections between the stations, I plan to implement a Breadth-first search (BFS) on them, but those connections are tricky.

ewaller · 2017-04-29 16:23:42

You might want to look at the bearing between stations in addition to the range. http://www.movable-type.co.uk/scripts/latlong.html
Obviously, you will not be doing Great Circle navigation over a local area, you should be able to just use the midpoint bearing.

I would plot the locations on a graph and find the best line through them http://serc.carleton.edu/mathyouneed/gr … stfit.html

Xyne · 2017-04-29 18:47:31

As a variation of your current algorithm, I would try to build the route one station at a time as follows.

remaining = <set of all stations>

a = b = remaining.pop() # pop the first station off the set, doesn't matter which one
x = y = <closest remaining station to a> # This is just to get started.

route = <queue with only station a>

while remaining:
  if distance(y,b) > distance(x,a):
    b = y
    route.append_to_end(y)
    remaining.remove(y)
    if (x == y):
      x = <closest remaining station to a>
    y = <closest remaining station to b>
  else:
    a = x
    route.append_to_start(x)
    remaining.remove(x)
    if (x == y):
      y = <closest remaining station to b>
    x = <closest remaining station to a>

That should reduce the number of pairwise distance calculations and minimize the great-arc distances between stations along the route. As with the previous algorithm, the bearing is ignored and the great-arc calculations are likely unnecessary as ewaller states above.

edit
Note that "distance(m,n)" in the loop above should not recalculate the distance each time. Whenever you determine the closest station, you should keep the distance in a variable (and use it to replace the "distance(m,n)" pseudo-code in the example).

edit 2
Also note that this completely disregards local geography and street maps. The effective distance would have to take into account not only bearing but also available street paths.

Last edited by Xyne (2017-04-29 20:25:46)

uberscientist · 2017-05-08 05:05:15

Maybe make a collection of the GPS coordinates in mongodb and run geospacial queries on them?

https://docs.mongodb.com/manual/referen … re-geojson
https://docs.mongodb.com/manual/referen … eospatial/

severach · 2017-05-08 05:08:23

Sounds to me like the Travelling Salesman Problem.

Arch Linux

#1 2017-04-29 16:04:32

How to figure out the order of GPS coordinates with minimal distances?

#2 2017-04-29 16:23:42

Re: How to figure out the order of GPS coordinates with minimal distances?

#3 2017-04-29 18:47:31

Re: How to figure out the order of GPS coordinates with minimal distances?

#4 2017-05-08 05:05:15

Re: How to figure out the order of GPS coordinates with minimal distances?

#5 2017-05-08 05:08:23

Re: How to figure out the order of GPS coordinates with minimal distances?

Board footer