Iterative Macro - How to calculate fastest drive time between dozens of points?

[bnelly1987]

Hello,

My question is this. Starting in Sacramento, California (California's Capital), what is the quickest route in order to hit every state capital across the USA.  My goal is to take a road trip and drive across the entire USA, hitting every state capital. I'm convinced the best way to do this would be through an iterative macro. Maybe I'm wrong, but it seems to be the right way to do this. I have attached my file that has each capital and its Spatial point/Centroid for each. Also, I have access to the TomTom traffic data. If you do not, please just use straight line distance and I'm sure I can adjust the workflow to use the TomTom data.

I'm at a loss on this. Even just help getting me started would be appreciated. Thank you in advance!

[Thableaus · Accepted solution]

Hi @bnelly1987 

I developed an iterative macro for you. See if this is a fine solution:

- The loop input separates the first result (which is going to be Sacramento) from the rest of the dataset and append it. Some changes on the fields for labeling purposes are done (labels as Start_City and End_City)

- Formula Tool to create distance in miles from Start to End.

- Sort Tool identifies the shortest distance.

- Sample Tool again to isolate the result and store in the final output.

The other side:

- Join the rest of the dataset to the End_city that got the shortest distance in the iteration

- Put this city on the top so it will be the next evaluated in the following iteration. (Using Union Tool)

- Count Records to keep track of how many cities are left

- Append this count to the dataset

- Use a filter to control the iterations. If the dataset has only one record, it's time to stop. So we'll keep going until Count is greater than 1. That will feed the Loop Output, which is going to be the next iteration Input.

The workflow:

- Put Sacramento as the first city of the route.

- Summarize distance so you can see how many miles you traveled

- You can even create a Travel_Line to see it on a map your whole route.

Whole package appended. I hope it suits you.

Cheers,

[bnelly1987]

Wow! Thank you so much. This is amazing.

[bnelly1987]

Thableaus,

I am still running into one major issue with this. While the iterative macro finds the next closest capital, it doesn't necessarily find the fastest route. Here is a screenshot of the final output

Starting in California, it moves on to Nevada. From Nevada it moves to Idaho and then it continues to move east. It doesnt go to Oregon or Washington until the very end because Idaho is slightly closer to Nevada than either Oregon or Washington. Looking at this map, total drive time and distance would be much longer then the better route. The smarter thing to do would be to go to oregon and washington after Nevada rather then Idaho, and then move to Idaho after. Is there a way to get this iterative macro to run various scenarios and then give back the shortest possible total distance? Thank you so much for your help!

[Thableaus]

Hi @bnelly1987 

I'm gonna work on this later. You might be right.

Cheers,

[Thableaus]

@bnelly1987 

I looked up during the weekend some way to solve your problem.

I found out there's an algorithm called Dijkstra's algorithm that is useful in these situations.

Still not sure how to bring that to Python, specifically to your case. 

Regarding to Alteryx's tools, I'm not so sure if there's one to do that.

I wonder if @MarqueeCrew @danilang or @CharlieS  have been through something similar and could bring some ideas to this matter.

Cheers, 

[MarqueeCrew]

not me.  travelling salesman isn't my bag.

[danilang]

Hi @bnelly1987 

I was going to reply to this last Friday, but I got sidetracked.  

This class of problem is known as NPComplete.  This class contains The Traveling Salesman problem(your's), the Knapsack problem(which may be @MarqueeCrew's bag.) and others.  No one's been able to prove that NP-Complete problems can be solved using any algorithms that take less time than the brute force approach.   

At the moment the only way to guarantee that you've got the shortest path through all 50 state capitals, is to actually generate all the possible paths and take the shortest one.  Since you're looking at 30414093201713378043612608166064768844377641568960512000000000000 permutations, it's going to take a long time.  

Like @Thableaus mentioned there are approximations and heuristics that will give you "shorter" paths, but none of them is guaranteed to give you the shortest path.  The linked Wiki page is a good starting point. 

If you just want to enjoy the trip and not actually do the calculation, this link says it's the shortest

https://www.adventuresportsnetwork.com/travel/the-most-efficient-road-trip-to-every-lower-48-u-s-sta...

Of course, since it can't be proven, you just have to take their word for it.

Edit:  you might want to combine that map with this one  https://flowingdata.com/2015/10/26/top-brewery-road-trip-routed-algorithmically/ but it will probably take you a lot longer!  Cheers

Dan