### 使用 Python 编写遗传算法解决带同时取送需求的车辆路径问题 (VRP) #### 1. 定义问题 带同时取送需求的车辆路径问题（Pickup and Delivery Vehicle Routing Problem, PDVRP）是一种复杂的组合优化问题，在该问题中，每辆车不仅需要访问多个地点进行货物配送，还需要在同一趟行程中完成某些特定位置的取货和送货任务。 #### 2. 表达问题 为了使PDVRP适应于遗传算法框架内求解，需将其转换成易于处理的形式。具体来说，就是创建一个合理的染色体结构来代表可能的路线方案[^1]。通常采用整数列表形式表示各节点被访问次序；其中正负号区分送货与取货行为。 #### 3. 初始种群生成 初始化阶段涉及随机生成一组可行解作为初始种群成员。这些解应满足基本约束条件，比如容量限制和服务时间窗等。 ```python import random from typing import List, Tuple def generate_initial_population(num_vehicles: int, num_customers: int) -> List[List[int]]: """Generates an initial population of routes.""" customers = list(range(1, num_customers + 1)) population = [] for _ in range(num_vehicles): route = [-random.choice(customers)] # Start with a pickup point while True: remaining_customers = set(customers).difference(set(route)) if not remaining_customers or len(route) >= num_customers / num_vehicles * 2: break next_customer = random.sample(list(remaining_customers), k=1)[0] delivery_or_pickup = (-next_customer if random.random() < 0.5 else next_customer) route.append(delivery_or_pickup) population.append(route) return population ``` #### 4. 计算适应度函数 适应度评估是衡量每个候选解质量的关键环节。对于PDVRP而言，总行驶距离是最常用的评价指标之一。此外还需考虑其他因素如载重量平衡性和客户满意度等。 ```python def calculate_fitness(routes: List[List[int]], distance_matrix: List[List[float]]) -> float: """Calculates the fitness value based on total travel cost.""" total_distance = sum( sum(distance_matrix[abs(a)-1][abs(b)-1] for a, b in zip([0]+route[:-1], route)) for route in routes ) return -total_distance # Minimize distance by maximizing negative values. ``` #### 5. 设计交叉变异操作 针对PDVRP特点设计专门的遗传算子有助于提高搜索效率并防止陷入局部最优解。文中提到两种有效的重组策略：一是基于双亲选择部分匹配的城市序列构造后代；二是通过2-opt方法调整路径顺序以消除交叉现象。 ```python def crossover(parents: Tuple[List[int], List[int]]) -> List[int]: parent_a, parent_b = parents start_city_index = abs(random.choice(parent_a)) offspring_route = [start_city_index] current_node = start_city_index visited_nodes = {current_node} while len(offspring_route) < min(len(parent_a), len(parent_b)): options_from_parent_a = [ node for i, node in enumerate(parent_a) if i != 0 and abs(node) not in visited_nodes and ((node > 0) == (parent_a[i-1]*node>0))] options_from_parent_b = [ node for i, node in enumerate(parent_b) if i != 0 and abs(node) not in visited_nodes and ((node > 0) == (parent_b[i-1]*node>0))] chosen_option = ( max(options_from_parent_a, key=lambda n: abs(n)) if options_from_parent_a else max(options_from_parent_b, key=lambda n: abs(n)) ) offspring_route.append(chosen_option) visited_nodes.add(abs(chosen_option)) return offspring_route def mutate(individual: List[int]) -> None: """Applies mutation to individual using two-point swap method""" idx_pair = sorted(random.sample(range(len(individual)), 2)) individual[idx_pair[0]], individual[idx_pair[1]] = \ individual[idx_pair[1]], individual[idx_pair[0]] ``` #### 6. 实施进化过程 最后一步是在迭代过程中不断更新种群直至达到预设终止条件为止。期间要合理控制精英保留比例以及引入适当的新鲜血液保持多样性。 ```python def evolve(population: List[List[int]], fitness_fn, selection_fn, crossover_fn, mutation_rate=.05, elite_size=2, generations=100) -> List[List[int]]: best_solution = None history_best_fitnesses = [] for generation in range(generations): ranked_solutions = [(solution, fitness_fn(solution)) for solution in population] ranked_solutions.sort(key=lambda pair: pair[1], reverse=True) top_elites = [pair[0] for pair in ranked_solutions[:elite_size]] selected_parents = selection_fn(ranked_solutions) children = [] for i in range((len(population) - elite_size)//2): child_one_genes = crossover(selected_parents[i*2]) child_two_genes = crossover(selected_parents[(i*2)+1]) if random.random() < mutation_rate: mutate(child_one_genes) mutate(child_two_genes) children.extend([child_one_genes, child_two_genes]) new_generation = top_elites + children population[:] = new_generation current_best_fit = max(fitness_fn(soln) for soln in population) history_best_fitnesses.append(current_best_fit) if not best_solution or current_best_fit > fitness_fn(best_solution): best_solution = max(new_generation, key=fitness_fn) return best_solution, history_best_fitnesses[-1] ```