Python：用模拟退火算法求解多车辆路径规划问题并可视化

= data.iloc[:, 2].tolist() # 获取所有行的第三列数据 #*******************************初始化参数************************************* # 计算节点数 num_nodes = len(x) # 计算车辆数 num_vehicles = 3 # 车辆容量 vehicle_capacity = 50 # 节点编号0代表起点，如果有120个点，则节点编号为1-120 nodes = [i for i in range(num_nodes)] # 计算车辆的起始节点和结束节点都是节点0 depot = 0 #*******************************计算距离************************************* def distance(x1, y1, x2, y2): return math.sqrt((x1 - x2)**2 + (y1 - y2)**2) # 计算节点之间的距禽 distances = {} for from_node in nodes: distances[from_node] = {} for to_node in nodes: if from_node == to_node: distances[from_node][to_node] = 0 else: distances[from_node][to_node] = distance(x[from_node], y[from_node], x[to_node], y[to_node]) print(distances) #*******************************模拟退火算法************************************* def get_route_cost(route): cost = 0 for i in range(len(route) - 1): cost += distances[route[i]][route[i+1]] return cost def simulated_annealing(num_vehicles, vehicle_capacity, demands, distances, num_iterations = 1000, initial_temperature = 1000, cooling_rate = 0.999): # 初始化当前最优解 best_solution = [] best_cost = float('inf') # 生成初始解 current_solution = [] unserved_nodes = [i for i in range(1, num_nodes)] for i in range(num_vehicles): route = [] capacity = vehicle_capacity while capacity > 0 and len(unserved_nodes) > 0: node = random.choice(unserved_nodes) if capacity >= demands[node]: route.append(node) capacity -= demands[node] unserved_nodes.remove(node) route = [0] + route + [0] current_solution.append(route) # 计算当前解的成本 current_cost = sum([get_route_cost(route) for route in current_solution]) # 初始化温度 temperature = initial_temperature # 模拟退火迭代 for i in range(num_iterations): # 生成邻域解 neighbor_solution = current_solution.copy() vehicle = random.randint(0, num_vehicles - 1) while len(neighbor_solution[vehicle]) <= 2: vehicle = random.randint(0, num_vehicles - 1) node1 = random.choice(neighbor_solution[vehicle][1:-1]) neighbor_solution[vehicle].remove(node1) vehicle = random.randint(0, num_vehicles - 1) node2 = random.choice([node for node in unserved_nodes if demands[node] <= vehicle_capacity - sum(demands[i] for i in neighbor_solution[vehicle][1:-1])]) unserved_nodes.remove(node2) neighbor_solution[vehicle].insert(random.randint(1, len(neighbor_solution[vehicle]) - 1), node2) # 计算邻域解的成本 neighbor_cost = sum([get_route_cost(route) for route in neighbor_solution]) # 判断是否接受邻域解 if neighbor_cost < current_cost or random.random() < math.exp((current_cost - neighbor_cost) / temperature): current_solution = neighbor_solution current_cost = neighbor_cost # 更新最优解 if current_cost < best_cost: best_solution = current_solution best_cost = current_cost # 降低温度 temperature *= cooling_rate return best_solution, best_cost # 运行模拟退火算法 best_solution, best_cost = simulated_annealing(num_vehicles, vehicle_capacity, demands, distances) # 输出结果 print("Best solution:", best_solution) print("Best cost:", best_cost) #*******************************绘制路径************************************* def plot_route(x, y, route): for i in range(1, len(route)): plt.plot([x[route[i-1]], x[route[i]]], [y[route[i-1]], y[route[i]]], 'bo-') plt.plot([x[route[-1]], x[0]], [y[route[-1]], y[0]], 'bo-') plt.figure() for i, route in enumerate(best_solution): plot_route(x, y, route) plt.plot(x[0], y[0], 'ro') plt.show() ######[AI写代码神器 | 2729点数解答 | 2024-11-25 15:32:50]