禁忌搜索算法求解CVRP问题用python代码复现，代码有如下几个要求：1.车辆的容量为9；2.需求点有19个；3.每行代码须标注中文注释

# 导入必要的库
import numpy as np
import random

# 初始化数据
n = 19 # 需求点数量
capacity = 9 # 车辆容量
d = np.array([[0, 12, 23, 14, 20, 23, 19, 18, 13, 22, 28, 16, 18, 21, 12, 16, 27, 18, 19], # 距离矩阵
[12, 0, 15, 18, 23, 19, 20, 15, 23, 12, 14, 21, 23, 13, 22, 17, 18, 22, 21],
[23, 15, 0, 14, 18, 22, 23, 14, 18, 21, 17, 16, 13, 19, 18, 22, 15, 16, 23],
[14, 18, 14, 0, 24, 19, 17, 18, 22, 14, 17, 22, 14, 18, 19, 17, 24, 16, 18],
[20, 23, 18, 24, 0, 9, 12, 23, 20, 22, 14, 23, 20, 16, 17, 23, 22, 21, 20],
[23, 19, 22, 19, 9, 0, 13, 15, 14, 13, 20, 20, 16, 18, 22, 18, 23, 22, 20],
[19, 20, 23, 17, 12, 13, 0, 22, 13, 19, 13, 15, 22, 18, 23, 19, 14, 19, 17],
[18, 15, 14, 18, 23, 15, 22, 0, 18, 17, 21, 20, 15, 20, 13, 20, 16, 22, 17],
[13, 23, 18, 22, 20, 14, 13, 18, 0, 17, 22, 18, 19, 21, 19, 21, 19, 22, 19],
[22, 12, 21, 14, 22, 13, 19, 17, 17, 0, 23, 14, 21, 17, 15, 16, 18, 18, 17],
[28, 14, 17, 17, 14, 20, 13, 21, 22, 23, 0, 19, 18, 19, 22, 22, 18, 20, 22],
[16, 21, 16, 22, 23, 20, 15, 20, 18, 14, 19, 0, 13, 14, 14, 23, 14, 17, 21],
[18, 23, 13, 14, 20, 16, 22, 15, 19, 21, 18, 13, 0, 23, 19, 12, 16, 17, 19],
[21, 13, 19, 18, 16, 18, 18, 20, 21, 17, 19, 14, 23, 0, 22, 13, 20, 20, 20],
[12, 22, 18, 19, 17, 22, 23, 13, 19, 15, 22, 14, 19, 22, 0, 20, 18, 14, 21],
[16, 17, 22, 17, 23, 18, 19, 20, 21, 16, 22, 23, 12, 13, 20, 0, 15, 15, 23],
[27, 18, 15, 24, 22, 23, 14, 16, 19, 18, 18, 14, 16, 20, 18, 15, 0, 18, 21],
[18, 22, 16, 16, 21, 22, 19, 22, 22, 18, 20, 17, 17, 20, 14, 15, 18, 0, 22],
[19, 21, 23, 18, 20, 20, 17, 17, 19, 17, 22, 21, 19, 20, 21, 23, 21, 22, 0]])

# 初始化禁忌表
tabu_list = np.zeros((n, n))

# 初始化解
solution = [0] * n
best_solution = [0] * n
best_fitness = float('inf')

# 迭代次数
max_iter = 100

# 禁忌搜索算法
for i in range(max_iter):
# 初始化候选解
candidate = []
candidate_fitness = []

# 生成候选解
for j in range(n):
for k in range(j + 1, n):
if solution[j] == solution[k]:
continue
new_solution = solution.copy()
new_solution[j], new_solution[k] = new_solution[k], new_solution[j]
# 计算候选解的适应度
fitness = sum([d[new_solution[l - 1]][new_solution[l]] for l in range(1, n)]) + d[new_solution[-1]][new_solution[0]]
if fitness < best_fitness:
best_solution = new_solution
best_fitness = fitness
if fitness < candidate_fitness:
candidate = new_solution
candidate_fitness = fitness

# 更新禁忌表
for j in range(n):
for k in range(n):
if tabu_list[j][k] > 0:
tabu_list[j][k] -= 1
if candidate[j] == k:
tabu_list[j][k] = 10

# 更新解
solution = candidate.copy()

print('最优解:', best_solution)
print('最优解的适应度:', best_fitness)