In optimization, 3-opt is a simple local search algorithm for solving the
travelling salesperson problem and related
network optimization problems. Compared to the simpler
2-opt
In optimization, 2-opt is a simple local search algorithm for solving the traveling salesman problem.
The 2-opt algorithm was first proposed by Croes in 1958, although the basic move had already been suggested by Flood.M. M. Flood, The traveling-sa ...
algorithm, it is slower but can generate higher-quality solutions.
3-opt analysis involves deleting 3 connections (or edges) in a
network
Network, networking and networked may refer to:
Science and technology
* Network theory, the study of graphs as a representation of relations between discrete objects
* Network science, an academic field that studies complex networks
Mathematics ...
(or tour), 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(tour, i, j, k):
"""If reversing tour :jwould make the tour shorter, then do it."""
# Given tour ..A-B...C-D...E-F... A, B, C, D, E, F = tour -1 tour tour -1 tour tour -1 tour % len(tour) d0 = distance(A, B) + distance(C, D) + distance(E, F)
d1 = distance(A, C) + distance(B, D) + distance(E, F)
d2 = distance(A, B) + distance(C, E) + distance(D, F)
d3 = distance(A, D) + distance(E, B) + distance(C, F)
d4 = distance(F, B) + distance(C, D) + distance(E, A)
if d0 > d1:
tour :j= reversed(tour :j
return -d0 + d1
elif d0 > d2:
tour :k= reversed(tour :k
return -d0 + d2
elif d0 > d4:
tour :k= reversed(tour :k
return -d0 + d4
elif d0 > d3:
tmp = tour :k+ tour :j tour :k= 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
(relative cost).
This is the complete 3-opt swap making use of the above mechanism:
def three_opt(tour):
"""Iterative improvement based on 3 exchange."""
while True:
delta = 0
for (a, b, c) in all_segments(len(tour)):
delta += reverse_segment_if_better(tour, a, b, c)
if delta >= 0:
break
return tour
def all_segments(n: int):
"""Generate all segments combinations"""
return ((i, j, k)
for i in range(n)
for j in range(i + 2, n)
for k in range(j + 2, n + (i > 0)))
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.
See also
*
2-opt
In optimization, 2-opt is a simple local search algorithm for solving the traveling salesman problem.
The 2-opt algorithm was first proposed by Croes in 1958, although the basic move had already been suggested by Flood.M. M. Flood, The traveling-sa ...
*
Local search (optimization)
In computer science, local search is a heuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate s ...
*
Lin–Kernighan heuristic
In combinatorial optimization, Lin–Kernighan is one of the best heuristic algorithm, heuristics for solving the symmetric travelling salesman problem. It belongs to the class of Local search (optimization), local search algorithms, which take a t ...
References
*
* Available a
PDF* Available a
PDF* Local Search Heuristics. (n.d.) Retrieved June 16, 2008, from http://www.tmsk.uitm.edu.my/~naimah/csc751/slides/LS.pdf{{Dead link, date=September 2018 , bot=InternetArchiveBot , fix-attempted=yes
Heuristic algorithms
Travelling salesman problem