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([7])

    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