4 ms·

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

• n4r9 9y ago
  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.
  • loverofthings 9y ago
    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.
    • n4r9 9y ago
      > 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.