Python 實作2-OPT優化算法（及通俗解釋）

算法通俗解釋

優化對象：一個路徑序列例如：1 2 3 4 5 6 7

2-OPT作用：随機是其中的兩個點換位置（注意保留原有連結），例如：2和5換位置，要保證3還是和2挨着，序列會變成1 5 4 3 2 6 7

優化：序列變動之後，與原序列，對比路徑和，如果路徑和變短則更新路徑

循環：重複上述步驟，設定循環次數，次數達到就跳出循環。

完整代碼

import numpy as np
import matplotlib.pyplot as plt
from mysql import *

MAXCOUNT = 10

def calDist(xid, yid, durationlist):
    for dura in durationlist:
        if dura['origin'] == xid and dura['destination'] == yid:
            return dura['duration']


def calPathDist(LocidList, durationlist):
    sum = 0
    for i in range(1, len(LocidList)):
        sum += calDist(LocidList[i], LocidList[i - 1], durationlist)
    return sum


# path1長度比path2短則傳回true
def pathCompare(path1, path2, LocidList, durationlist):
    LocidList1 = []; LocidList2 = []
    for i in path1:
        LocidList1.append(LocidList[i])
    for i in path2:
        LocidList2.append(LocidList[i])
    if calPathDist(LocidList1, durationlist) <= calPathDist(LocidList2, durationlist):
        return True
    return False


def generateRandomPath(bestPath):
    a = np.random.randint(len(bestPath))
    while True:
        b = np.random.randint(len(bestPath))
        if np.abs(a - b) > 1:
            break
    if a > b:
        return b, a, bestPath[b:a + 1]
    else:
        return a, b, bestPath[a:b + 1]


def reversePath(path):
    rePath = path.copy()
    rePath = reversed(rePath)
    return list(rePath)


def updateBestPath(bestPath, LocidList, durationlist):
    count = 0
    while count < MAXCOUNT:
        start, end, path = generateRandomPath(bestPath)
        rePath = reversePath(path)
        # print('path:', path,'repath:', rePath, 'end:', end)
        if 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 ProduceInput(routes):
    routes_pathindex = np.arange(0, len(routes))
    test = mysql()
    orderlist = test.findALLorder()
    duration = test.findALLduration()
    location = test.findAllloc()
    orderlist_route = []
    for order in orderlist:
        if str(order['OrderId']) in routes:
            orderlist_route.append(order)
    LocId = []
    for order in orderlist_route:
        LocId.append(test.findloc(order['Lat'], order['Lng']))

    return routes_pathindex, LocId, duration


if __name__ == '__main__':
    routes = ['40001', '40003', '40002', '40004', '40005', '40006', '40007', '40008']
    #注明：routes_pathindex是路徑的下标，LocId儲存的是所有點的位置，duration儲存的是各個位置之間的距離機關
    (routes_pathindex, LocId, duration) = ProduceInput(routes)
    print(updateBestPath(routes_pathindex, LocId, duration))