4-opt and Double Bridge

Replacing 3-optic moves in the local optimization with 4-opt moves increases the time complexity the algorithm from O(N³) to O(N⁴), or, in the case of using lists of candidates (neighbors), from O(N * m²) to O (N * m³), where m is number of neighbors in the list.

However, the problem does not lie only in much greater time of execution. Applying 4-opt moves gives tours only slightly shorter than those from 3-optimization. Moreover, while for 3-opt there are 8 types (cases) of move, for 4-opt this number increases to 48, so considering all of them becomes much more complicated. As in 3-opt, one of them gives the tour identical with the tour before the move. Analogically to 3-opt, many of them are equal to a single 2-opt or a single 3-opt move; there are only 25 pure 4-opt moves. But something new appears in 4-opt moves: most known 4-opt move, called double bridge move.

The simplicity and symmetry of the double bridge scheme make it particularly easy to recognize and remember:

Double bridge, as the simplest non-sequential move (idea of so called sequenctial moves is described later), plays important role even in algorithms that do not use full 4-optimization. By definition given tour after full 3-optimization cannot be further improved by 3-opt, but it does not mean that there are no similar but shorter tours. Instead of trying to search or build such tours from scratch, we often use 3-optimized tour and perturb it to obtain a new good initial tour, that we can then optimize, perhaps getting better result. Double bridge is used as simple and effective perturbation.

Double bridge and other non-sequential 4-opt moves are discussed in detail later.