Shortest Path between Locations (without repeating)

[ciaran3]

I'm missing something obvious here and I just can't figure out how to quite go about it.

I've essentially got a list of 20 locations - then looking up their zip codes and referencing them to lat/long.

I want to take the 1st location (marking it as 1) and find the next closest location from it of the 19 remaining (and mark that location as 2). Then find the next closest location to location #2 and mark that as #3, etc. More or less trying to find the shortest distance path that taking me to all locations on that list without repeating. Short example below.

Good on finding the distance and comparing it, my issue is more with how to knock a location off from the list once it's been selected.

Any assistance would be appreciated it.

Please Login or Register  to view this content.

More or less the X loop doesn't do anything - I correctly find the location closest to Alpha but don't go beyond that because it just gets stuck there.

[ciaran3]

The version below largely works - but it's re-selecting some locations (eg location is getting chosen as #4 and later being chosen again as #40).

Please Login or Register  to view this content.

[6StringJazzer]

First, the algorithm you describe will not necessarily give the shortest path across all locations.

If you have a fixed starting point, and want to visit 19 more points, there are 19! possible paths, or 1.2 x 10¹⁷. (See Travelling Salesman Problem for a famous description of what you're trying to do.)

That being said I will dig into your code and see if I can answer your question as asked.

[ciaran3]

Ah, perhaps a bad descriptor then. I'd like to find the next closest location based upon my base location (so Alpha = 1, find closest to Alpha = 2/Beta, find closest to 2/Beta = 3/Charlie, etc) for my 20 locations.

I know it pretty much is guaranteed to be non-optimal path but it's more focused on minimizing day to day travel (1 location = 1 day).

Feel free to scrap and adjust as necessary - but hopefully my adjusted description is a little clearer.

The important caveat is not repeating locations.

[6StringJazzer]

There are some things about your code that are a bit confusing, and might be clearer if you included your Excel file. For example, by are you multliplying R * 4? Why do you have a For loop that goes from 1 To 1? What is TestLoc? How are you marking points that have already been used?

[ciaran3]

Ah - I've got some information in there I cleaned up in the code. I'm running this for multiple individuals (when it works) so the loop is for each individual (the location ID assigned to them is in columns 1, 5, 9, etc).

So Column A is the identifying info I'm lookup up to obtain lat/lon, Column B/C are identifying info that's not being used, and Column D contains the visit order.

So BaseLoc is my default start point, then it loops through all 20 locations (calculating distance from the BaseLoc) and records the closest location. It then resets BaseLoc to that location and repeats (in theory skipping locations that were already assigned).

[TheN]

if you know it is always 20 locations, couldn't you just declare 20 separate variables a default value of 0 or something and assign them their respective positions? then do until no more zeros are left?

alternatively, if you want a more elegant solution, something like hiding/editing the used ones and only looking at visible/unedited locations could be another route to your desired results.

Don't quite understand all of your code, so not going to give example code, sorry.

[6StringJazzer]

There are some things about your code that are a bit confusing, and might be clearer if you included your Excel file.