Remedies for slow 3-optimization

As we can see from statistics the basic version of 3-optimization is much slower than 2-optimization. For N=100 running times are by one to two orders of magnitude greater. This is in line with expectations, because 2-optimization is of O(N²), while 3-optimization is of O(N³).

A tour which cannot be improved by any 2-opt move is called 2-optimal. Similarly, a tour which cannot be improved by any 3-opt move is called 3-optimal. Each 3-optimal tour is 2-optimal (see: 3-opt move and general idea of iterative 3-opt) but not vice versa. We are looking for ways to improve tours beyond 2-optimality, but faster than in basic 3-opt iterative algorithm.

We will take a look at two approaches:

1. use some faster improving heuristic, a simplified version of the 3-opt, limited to specific cases (Or-opt, 2.5-opt),
2. use some speed-ups to 3-opt without limiting the set of examined cases (don’t look bits, fixed radius search, neighbor lists).