3-opt


In optimization, 3-opt is a simple local search algorithm for solving the travelling salesman problem and related network optimization problems.
3-opt analysis involves deleting 3 connections in a network, to create 3 sub-tours. Then the 7 different ways of reconnecting the network are analysed to find the optimum one. This process is then repeated for a different set of 3 connections, until all possible combinations have been tried in a network. A single execution of 3-opt has a time complexity of. Iterated 3-opt has a higher time complexity.
This is the mechanism by which the 3-opt swap manipulates a given route:
def reverse_segment_if_better:
"""If reversing tour would make the tour shorter, then do it."""
# Given tour
A, B, C, D, E, F = tour, tour, tour, tour, tour, tour
d0 = distance + distance + distance
d1 = distance + distance + distance
d2 = distance + distance + distance
d3 = distance + distance + distance
d4 = distance + distance + distance
if d0 > d1:
tour = reversed
return -d0 + d1
elif d0 > d2:
tour = reversed
return -d0 + d2
elif d0 > d4:
tour = reversed
return -d0 + d4
elif d0 > d3:
tmp = tour + tour
tour = tmp
return -d0 + d3
return 0
The principle is pretty simple. You compute, the original distance and you compute the cost of each modification. If you find a better cost, apply the modification and return .
This is the complete 3-opt swap making use of the above mechanism:
def three_opt:
"""Iterative improvement based on 3 exchange."""
while True:
delta = 0
for in all_segments:
delta += reverse_segment_if_better
if delta >= 0:
break
return tour
def all_segments:
"""Generate all segments combinations"""
return
for i in range
for j in range
for k in range)
For the given tour, you generate all segments combinations and for each combinations, you try to improve the tour by reversing segments. While you find a better result, you restart the process, otherwise finish.