# Creating a route based on GPS proximity

1. ## Creating a route based on GPS proximity

I have a list of locations with GPS coordinates. From the GPS coordinates I found the distance between each point with respect to one another. Now I have been trying to sort the locations based on the next closest point. In the end I would like the formula to start at a location (i.e. 16-10-426-12-EXT Receiver) find the next closest point (16-11-488-12 Receiver) then find the next closest point from there but exclude any location that was previously listed. Excluding previously listed locations from the Index or lookup is what I can not figure out.  Register To Reply

2. ## Re: Creating a route based on GPS proximity

Filter the table and sort any column smallest to largest.  Register To Reply

3. Originally Posted by protonLeah Filter the table and sort any column smallest to largest.
That will only sort the distance from one point with respect to the rest. I need it to pick the closest point in relation to each individual location. For example if you have point A between B, C, and D; B 1m to the left of A, C 1m to the right of A, and D 3.1m to the right of A, sorting them will put the order A, B, C, D when the most efficient route should be something more like A, B, D, C  Register To Reply

4. ## Re: Creating a route based on GPS proximity

So, is it really some kind of "shortest path" algorithm that you are trying to do here? http://www.excel-easy.com/examples/s...h-problem.html  Register To Reply

5. Originally Posted by MrShorty So, is it really some kind of "shortest path" algorithm that you are trying to do here? http://www.excel-easy.com/examples/s...h-problem.html
Its a similar idea. Except I will have a lot of data and would need it listed based on the shortest path of the next closest point, excluding any duplicates already in the list  Register To Reply

6. ## Re: Creating a route based on GPS proximity

So a "shortest path -- greedy algorithm style" type algorithm? Just trying to make sure I understand exactly what you are trying to do.

In the other shortest path algorithms, the "don't repeat a node" seems to be handled by the constraint that "flow into a node"-"flow out of node"=0. I would probably expect that the "don't duplicate a node" part of the algorithm probably includes some formula to count flow in/flow out of each node.

In searching for other sample spreadsheets, I came across this shortest path algorithm tutorial with a couple of sample sheets: https://networkmodels.weebly.com/excel-solver.html One of their examples looks more like the 2D distance matrix that you have, so it might be more helpful.

I think if I were doing this, I would probably start with one of these shortest path problem spreadsheets/examples, and make sure I understand exactly how it works. Once I understand how those examples work, I would structure your data in a similar way -- with nodes and arcs and such. Once I have the spreadsheet set up (with or without the Solver model), then I can work on the "greedy algorithm" part of the problem.

(FWIW, I started trying to develop the greedy algorithm and thought that it looked easier with the arcs in list format like the Excel Easy example rather than in the 2D matrix format, but I did not explore it in depth. Whichever approach is going to require some thought towards data structure.)  Register To Reply

There are currently 1 users browsing this thread. (0 members and 1 guests) 