求解旅行商问题专用工具elkai

发表于 更新于
elkai专门用于解决TSP问题，被认为是目前解决TSP问题最有效的算法。

elkai是python的第三方库，专门用于解决TSP问题，目前已知能够在规模达到315个节点的问题中求解出最优方案。elkai本身的实现基于大名鼎鼎的LKH算法，该算法被认为是目前解决TSP问题最有效的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import numpy as np
import elkai
import math
import matplotlib.pyplot as plt
import scipy as sp
import scipy.spatial as ssp

"""
data.txt数据载入
-----------------
重庆,106.54,29.59
拉萨,91.11,29.97
乌鲁木齐,87.68,43.77
银川,106.27,38.47
呼和浩特,111.65,40.82
南宁,108.33,22.84
哈尔滨,126.63,45.75
长春,125.35,43.88
沈阳,123.38,41.8
石家庄,114.48,38.03
太原,112.53,37.87
西宁,101.74,36.56
济南,117,36.65
郑州,113.6,34.76
南京,118.78,32.04
合肥,117.27,31.86
杭州,120.19,30.26
福州,119.3,26.08
南昌,115.89,28.68
长沙,113,28.21
武汉,114.31,30.52
广州,113.23,23.16
台北,121.5,25.05
海口,110.35,20.02
兰州,103.73,36.03
西安,108.95,34.27
成都,104.06,30.67
贵阳,106.71,26.57
昆明,102.73,25.04
香港,114.1,22.2
澳门,113.33,22.13
"""
city_name = []
city_condition = []
with open('data.txt','r',encoding='UTF-8') as f:
    lines = f.readlines()
    for line in lines:
        line = line.split('\n')[0]
        line = line.split(',')
        city_name.append(line[0])
        city_condition.append([float(line[1]), float(line[2])])
city_condition = np.array(city_condition)

# 利用scipy计算距离矩阵
def genDistanceMat(x,y):
    X=np.array([x,y])
    distMat=ssp.distance.pdist(X.T)
    sqdist=ssp.distance.squareform(distMat)
    return sqdist
x,y = city_condition[:,0],city_condition[:,1]

# 计算距离矩阵
distance = genDistanceMat(x, y)

# 传入解方案，计算解方案的总距离
def cal_fitness(solutionnew):
    valuenew = np.sum(distance[solutionnew[:-1],solutionnew[1:len(solutionnew)]])
    return valuenew

solutionbest = elkai.solve_int_matrix(distance)
solutionbest.append(0)
print("最优解方案:",solutionbest)
print("最优解总长度:",cal_fitness(solutionbest))