New TSP Algorithm

[srheede]

Hi,

I wrote a new algorithm for the traveling salesman problem.

I've benchmarked it against the top algorithms from ORTools. The resulting route tends to always be within 10 percent of the distance of the best routes produced by the ORTools algorithms. What is remarkable about my algorithm is that the run time is orders of magnitude faster. See the examples attached.

Let me know if this would be of interest to ORTools.

[Mizux]

Did you only compare the first strategy heuristic or does the guided local search was enabled too ?

Does your algorithm structure would support multiple vehicles, multiple dimensions, pickup and delivery, dropping location, and all others features routing support ? Having tons of features has a cost....
Is 12732 and 46122 the objective cost ?
Otherwise did you compare against Concorde which is a pure TSP IIRC ?

[lperron]

So, you are not comparing apple to apple. You are running your heuristics against heuristic + local search.
On gr202, Christofides takes <4ms (cost similar to yours), on fl417, <6ms (cost slightly worse).