Route optimization

[etudiant]

Originally Posted by JimEli

Prone to flying off the handle? Because you just went all Fox-One on me. Try switching to 100% Ox before total GLOC. Nobody’s claiming plagiarism. I just pointed out that you called an imported, specialized library to do all the heavy lifting and create the TSP solution. Sort of like claiming you can multiply, but then using a calculator. You're the one that boasted. You also should have noted, that the imported algorithm, “does not guarantee to find the optimal solution.” I’ll ignore the remainder of your pointless drivel, however reference your comment about my post, you could have followed my link to the source of the comment. I did that so anyone but a disgruntled pelican could clearly see it wasn’t mine. And regarding enlightening, “us all where such a start to end solution has been presented before for everyone to see?” A few progenitors are,

https://jupyter.brynmawr.edu/service...15/TSPv3.ipynb

and,

Travelling Salesman Problem · Ross Scrivener

and the Concorde TSP Solver, widely regarded as the fastest true TSP solver in existence (BTW, its also an iPhone app),

https://en.wikipedia.org/wiki/Concorde_TSP_Solver

Sorry, you don't sound competent.
Roosevelt (Teddy) pointed out :

It is not the critic who counts... the credit belongs to the man who is actually in the arena

Swh has provided a useful bit of work. What have you contributed?

[JimEli]

Attached is my alternative program. Like the posted code above, it doesn’t necessarily provide the optimum (or shortest) tour through all points. As I stated above, as the number of points grow, the possible number of tours increases as a factor (n!). Therefore, the code can't search every possible path, but uses an approximating algorithm that in most cases finds a tour that is short, but not guaranteed to be the shortest. But it’s very fast. The program is a Windows executable which uses the Chrisofides algorithm with 2-opt optimization. Feed it a csv file consisting of pairs of lat/long points, and it outputs a kml file.

Here are a few examples of output displayed in Google Earth:

48 US state capitols

Sweden Cities (on my laptop, an 1.6GHz i5, it runs in approx. 2 seconds)

It took me longer to accomplish this because I don’t live in my parent’s basement. Due to size, the C++ source code is available via pm.