```python import numpy as np import random # 假设的车辆容量 CAPACITY = 200 # 节点索引、横坐标、纵坐标、需求量 nodes_data = [ [1, 406, 126, 0.97], [2, 386, 126, 0.60], [3, 366, 126, 0.21] ] random.seed(42) for i in range(6, 101): x = random.randint(0, 400) y = random.randint(0, 200) demand = random.uniform(0.1, 1.0) nodes_data.append([i, x, y, demand]) # 生成节点列表（包含仓库节点0和客户节点1 - 100） nodes = list(range(101)) # 提取节点索引、坐标和需求量 x_coords = {i: 0 for i in nodes} y_coords = {i: 0 for i in nodes} demands = {i: 0 for i in nodes} for data in nodes_data: index = data[0] x_coords[index] = data[1] y_coords[index] = data[2] demands[index] = data[3] # 计算距离矩阵 def calculate_distance_matrix(nodes): n = len(nodes) distance_matrix = np.zeros((n, n)) for i in range(n): for j in range(n): if i != j: dx = x_coords[nodes[i]] - x_coords[nodes[j]] dy = y_coords[nodes[i]] - y_coords[nodes[j]] distance_matrix[i, j] = np.sqrt(dx2 + dy2) return distance_matrix distance_matrix = calculate_distance_matrix(nodes) # 1. Clarke - Wright算法 def clarke_wright(): savings = [] for i in range(1, len(nodes)): for j in range(i + 1, len(nodes)): saving = distance_matrix[0, i] + distance_matrix[0, j] - distance_matrix[i, j] savings.append((-saving, i, j)) savings.sort() routes = [[i] for i in range(1, len(nodes))] for _, i, j in savings: for ri in routes: if i in ri: break for rj in routes: if j in rj: break if ri is rj: continue new_route_demand = sum(demands[node] for node in ri) + sum(demands[node] for node in rj) if new_route_demand <= CAPACITY: merged_route = ri + rj routes.remove(ri) routes.remove(rj) routes.append(merged_route) final_routes = [[0] + route + [0] for route in routes if route] return final_routes # 2. 遗传算法 def genetic_algorithm(): population_size = 50 num_generations = 100 mutation_rate = 0.1 def generate_valid_route(): unvisited = list(range(1, len(nodes))) random.shuffle(unvisited) routes = [] while unvisited: route = [0] current_demand = 0 while unvisited and current_demand + demands[unvisited[0]] <= CAPACITY: node = unvisited.pop(0) route.append(node) current_demand += demands[node] route.append(0) routes.append(route) return routes def fitness(route): total_distance = 0 for r in route: for i in range(len(r) - 1): total_distance += distance_matrix[r[i], r[i + 1]] return 1 / total_distance def crossover(parent1, parent2): child = [] for route1, route2 in zip(parent1, parent2): common_nodes = set(route1).intersection(set(route2)) new_route = [0] + list(common_nodes) + [0] remaining_nodes = set(route1 + route2) - set(new_route) current_demand = sum(demands[node] for node in new_route) while remaining_nodes: candidate = random.choice(list(remaining_nodes)) if current_demand + demands[candidate] <= CAPACITY: new_route.insert(-1, candidate) remaining_nodes.remove(candidate) current_demand += demands[candidate] else: break child.append(new_route) return child def mutate(route): if random.random() < mutation_rate: for r in route: if len(r) > 3: idx1, idx2 = random.sample(range(1, len(r) - 1), 2) r[idx1], r[idx2] = r[idx2], r[idx1] return route population = [generate_valid_route() for _ in range(population_size)] for _ in range(num_generations): new_population = [] for _ in range(population_size // 2): parents = random.sample(population, 2) child1 = crossover(parents[0], parents[1]) child2 = crossover(parents[1], parents[0]) child1 = mutate(child1) child2 = mutate(child2) new_population.extend([child1, child2]) population = sorted(new_population, key=lambda x: fitness(x), reverse=True)[:population_size] best_route = max(population, key=lambda x: fitness(x)) return best_route ``` 额外需要注意的逻辑点 1. 在Clarke - Wright算法中，合并路线时要确保新路线的需求量不超过车辆容量，避免出现不合理的路线规划。 2. 遗传算法中，生成初始种群时，每条路线的需求量也需要严格控制不超过容量，否则后续的交叉和变异操作可能会产生无效解。 3. 遗传算法中的适应度函数使用了距离的倒数，这样可以使得距离越短的路线适应度越高，但要注意距离为0的情况（虽然在实际中不太可能出现），防止出现除零错误。 [2025-06-11 02:45:18 | AI写代码神器 | 1530点数解答]