Hacker News Reader

That CPU time sounds reasonable for just 2-opt but I've found that 3-opt takes longer for tours with that many stops. The quickest strategy that involves 3-opt is to do a run of 2-opt followed by 3-opt, but for instances with 500 stops this can take nearly a second to run, even after parallelizing and optimising the code.

The tools you use will also make a difference. Python is difficult to make as performant as C.

View on HN

Yeah, I was thinking of a C++ implementation. The nested for loops get optimized very well for the 3-opt case. There's also a couple of tricks one can do with preloading (simd) of distances for evaluating 2,3-opt simultaneously. That all fits into 200 lines of code. There's also the fact that after executing the best moves there's a lot of previously evaluated moves that are still valid. This also fits into those 200 lines.

Not trivial, but IMO less trivial than self-organizing maps.

> after executing the best moves there's a lot of previously evaluated moves that are still valid

Ah, this has crossed my mind as well, but I hadn't got round to implementing it yet. You could even determine a set of independent swaps per iteration and perform them all in parallel.

Reply on news.ycombinator.com