Hacker News Reader

Comment by loverofthings | Hacker News Reader

7.5% longer than is optimal is way too much.

Doing simple 2-opt/3-opt heuristic (10-100ms CPU time of optimization, 200 lines of code) gets you to 1-3% of the optimum.

View on HN

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.

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