# Python implementation of K-OPT algorithm (and popular explanation)

## Algorithm interpretation

The first step is to understand the 2-OPT algorithm, not the reference link: https://blog.csdn.net/qq_30008595/article/details/95033476
The characteristic of K-OPT is to divide paths randomly into K segments and then call 2-OPT, because there are many paragraphs, but not every segment should use 2-OPT, so there are many combinations: 1 segments, 2 paragraphs... Segment K is used, so every one should be tried. If there is a better path, it will stay, or it will not stay.
Recommend a paper (possibly over the wall): https://pdfs.semanticscholar.org/ab7c/c83bb513a91b06f6c8bc3b9da7f60cbbaee5.pdf

## Complete code

```import random
import numpy as np
import matplotlib.pyplot as plt
import TWOPT
from itertools import combinations, permutations

MAXCOUNT = 1

def KDevide(routes_length, k):
PartNumber = []
for i in range(len(routes_length)):
if len(PartNumber) == 0:
PartNumber.append(random.randint(0, len(routes_length) - 1))
else:
if PartNumber[i-1]+2 < len(routes_length) - 1:
PartNumber.append(random.randint(PartNumber[i-1]+2, len(routes_length) - 1))
else:
break
return PartNumber

def Update_routes(routes, PartNumber):
Part_Routes = []
# routes.remove(7)
for Part_i in range(len(PartNumber)):
if Part_i == 0:
Part_Route = routes[0:PartNumber[Part_i]]
Part_Routes.append(Part_Route)
continue
elif  Part_i <= len(PartNumber) - 1:
print(Part_i, PartNumber[Part_i])
Part_Route = routes[PartNumber[Part_i-1]:PartNumber[Part_i]]
else:
break
if len(Part_Route) != 0:
Part_Routes.append(Part_Route)
print(PartNumber[-1])
if PartNumber[-1] != 7:
Part_Routes.append(routes[PartNumber[-1]:])
else:
Part_Routes.append()

return Part_Routes

def UpdatePartPath(bestPath, LocidList, durationlist):
count = 0
while count < MAXCOUNT:
start, end, path = TWOPT.generateRandomPath(bestPath)
rePath = TWOPT.reversePath(path)
print('path:', path,'repath:', rePath, 'end:', end)
if TWOPT.pathCompare(path, rePath, LocidList, durationlist):
count += 1
continue
else:
count = 0
print('path:', path, 'repath:', rePath, 'end:', end)
bestPath[start:end+1] = rePath
return bestPath

def Combination(Part_Routes):
Part = []
for i in range(len(Part_Routes)):
Part.append(i)
Modify_parts = []
for i in range(len(Part_Routes)):
Modify_parts.append(list(combinations(Part,i+1)))
return Modify_parts

#List the sorting results modify "parts: [[(1, 2)], [(1, 2), (2, 3)]] Modify_part: [(1, 2), (2, 3)]
def UpdateOnece(Modify_parts, Part_Routes):
temp = Part_Routes
UpdateRoutes = []
for Modify_part in Modify_parts:
for Modify_subpart in Modify_part:
Part_Routes = temp.copy()
for Modify_subsubpart in Modify_subpart:
Part_Routes[Modify_subsubpart] = TWOPT.reversePath(Part_Routes[Modify_subsubpart])
UpdateRoutes.append(Part_Routes)
return UpdateRoutes

def Merge(UpdateRoutes):
Merge_Routes = []
for UpdateRoute in UpdateRoutes:
Merge_Route = []
for SubUpdateRoute in UpdateRoute:
Merge_Route.extend(SubUpdateRoute)
Merge_Routes.append(Merge_Route)
return Merge_Routes

routes = ['40001', '40003', '40002', '40004', '40005', '40006', '40007', '40008']
(routes_pathindex, LocId, duration) = TWOPT.ProduceInput(routes)
k = KDevide(routes_pathindex, 4)
test = Update_routes(routes_pathindex, k)
result = UpdateOnece(Combination(test), test)
print(Merge(result))
```

Posted on Fri, 01 Nov 2019 23:58:05 -0700 by bunner bob