别再手动排路线了！用Python+遗传算法搞定物流配送VRP（附完整代码）

用Python遗传算法实现智能物流配送路径规划物流配送效率直接影响企业运营成本而传统人工排线方式往往耗时费力且难以达到最优。本文将带你用Python构建一个基于遗传算法的智能配送系统从数据准备到算法调优完整实现自动化路径规划。1. 环境准备与数据建模在开始编码前我们需要搭建合适的开发环境。推荐使用Python 3.8版本主要依赖以下库pip install numpy matplotlib pandas deap物流配送问题(VRP)的核心数据结构需要包含以下要素配送中心坐标客户点坐标列表各客户点需求量车辆载重限制车辆数量限制我们可以用如下数据结构表示class VRPInstance: def __init__(self): self.depot (0, 0) # 配送中心坐标 self.customers [] # 客户坐标列表 self.demands [] # 客户需求量 self.vehicle_capacity 100 # 单车载重 self.num_vehicles 5 # 可用车辆数2. 遗传算法核心设计遗传算法模拟自然选择过程通过迭代优化寻找最优解。针对VRP问题我们需要特别设计以下组件2.1 染色体编码采用客户点序列编码方式例如路线1: [0,1,2,3,0] 路线2: [0,4,5,0] 路线3: [0,6,7,8,0]编码为一条染色体[1,2,3,4,5,6,7,8]2.2 适应度函数设计考虑三个关键因素总行驶距离车辆使用数量载重约束违反程度def fitness(individual, instance): total_distance 0 used_vehicles 1 current_load 0 # 从配送中心出发 prev_point instance.depot for customer_idx in individual: # 检查是否需要返回配送中心 if current_load instance.demands[customer_idx] instance.vehicle_capacity: # 返回配送中心并开始新路线 total_distance distance(prev_point, instance.depot) prev_point instance.depot used_vehicles 1 current_load 0 # 前往下一个客户点 customer instance.customers[customer_idx] total_distance distance(prev_point, customer) current_load instance.demands[customer_idx] prev_point customer # 最后返回配送中心 total_distance distance(prev_point, instance.depot) # 惩罚项车辆使用数超过限制 penalty max(0, used_vehicles - instance.num_vehicles) * 1000 return total_distance penalty,2.3 遗传算子设计选择算子采用锦标赛选择toolbox.register(select, tools.selTournament, tournsize3)交叉算子有序交叉(OX)toolbox.register(mate, tools.cxOrdered)变异算子交换变异toolbox.register(mutate, tools.mutShuffleIndexes, indpb0.05)3. 完整算法实现使用DEAP框架构建完整遗传算法流程from deap import base, creator, tools import random def genetic_algorithm_vrp(instance, pop_size100, n_gen500, cx_prob0.8, mut_prob0.2): # 定义问题类型 creator.create(FitnessMin, base.Fitness, weights(-1.0,)) creator.create(Individual, list, fitnesscreator.FitnessMin) toolbox base.Toolbox() # 注册遗传操作 toolbox.register(indices, random.sample, range(len(instance.customers)), len(instance.customers)) toolbox.register(individual, tools.initIterate, creator.Individual, toolbox.indices) toolbox.register(population, tools.initRepeat, list, toolbox.individual) toolbox.register(evaluate, fitness, instanceinstance) toolbox.register(mate, tools.cxOrdered) toolbox.register(mutate, tools.mutShuffleIndexes, indpb0.05) toolbox.register(select, tools.selTournament, tournsize3) # 初始化种群 pop toolbox.population(npop_size) # 评估初始种群 fitnesses list(map(toolbox.evaluate, pop)) for ind, fit in zip(pop, fitnesses): ind.fitness.values fit # 进化循环 for gen in range(n_gen): # 选择下一代 offspring toolbox.select(pop, len(pop)) offspring list(map(toolbox.clone, offspring)) # 交叉 for child1, child2 in zip(offspring[::2], offspring[1::2]): if random.random() cx_prob: toolbox.mate(child1, child2) del child1.fitness.values del child2.fitness.values # 变异 for mutant in offspring: if random.random() mut_prob: toolbox.mutate(mutant) del mutant.fitness.values # 评估新个体 invalid_ind [ind for ind in offspring if not ind.fitness.valid] fitnesses map(toolbox.evaluate, invalid_ind) for ind, fit in zip(invalid_ind, fitnesses): ind.fitness.values fit # 更新种群 pop[:] offspring # 返回最优解 return tools.selBest(pop, k1)[0]4. 结果可视化与调优技巧4.1 路径可视化使用matplotlib绘制最优路径def plot_solution(instance, individual): plt.figure(figsize(10, 8)) # 绘制配送中心 plt.scatter(instance.depot[0], instance.depot[1], cred, s200, markers, labelDepot) # 绘制客户点 x [c[0] for c in instance.customers] y [c[1] for c in instance.customers] plt.scatter(x, y, cblue, s100, labelCustomers) # 绘制路径 current_route [instance.depot] current_load 0 for customer_idx in individual: customer instance.customers[customer_idx] if current_load instance.demands[customer_idx] instance.vehicle_capacity: # 完成当前路线 current_route.append(instance.depot) x [p[0] for p in current_route] y [p[1] for p in current_route] plt.plot(x, y, --, alpha0.5) # 开始新路线 current_route [instance.depot, customer] current_load instance.demands[customer_idx] else: current_route.append(customer) current_load instance.demands[customer_idx] # 绘制最后一条路线 current_route.append(instance.depot) x [p[0] for p in current_route] y [p[1] for p in current_route] plt.plot(x, y, --, alpha0.5) plt.legend() plt.title(Vehicle Routing Solution) plt.show()4.2 参数调优指南参数推荐范围影响说明种群大小50-200越大搜索空间越广但计算成本增加迭代次数500-5000问题复杂度越高需要越多迭代交叉概率0.7-0.9控制新个体产生的频率变异概率0.01-0.1保持种群多样性关键锦标赛大小3-7选择压力调节实际项目中建议采用网格搜索寻找最优参数组合param_grid { pop_size: [50, 100, 200], cx_prob: [0.7, 0.8, 0.9], mut_prob: [0.01, 0.05, 0.1] } best_params None best_fitness float(inf) for params in ParameterGrid(param_grid): solution genetic_algorithm_vrp(instance, **params) current_fitness fitness(solution, instance)[0] if current_fitness best_fitness: best_fitness current_fitness best_params params5. 实际应用中的优化技巧在真实物流场景中我们还需要考虑以下实际问题动态需求处理当有新订单到达时如何高效更新现有路线def dynamic_update(current_solution, new_orders): # 将新订单插入到现有解中 for order in new_orders: best_pos find_best_insertion(current_solution, order) current_solution.insert(best_pos, order.customer_idx) # 局部优化 return local_search(current_solution)时间窗约束客户可能有特定的服务时间要求def time_window_penalty(route, instance): penalty 0 current_time 0 for i in range(len(route)-1): from_node route[i] to_node route[i1] # 计算行驶时间 travel_time distance(from_node, to_node) / SPEED current_time travel_time # 检查时间窗 if to_node in instance.time_windows: start, end instance.time_windows[to_node] if current_time start: # 提前到达等待 current_time start elif current_time end: # 延迟到达惩罚 penalty (current_time - end) * PENALTY_RATE return penalty多目标优化平衡距离、时间、成本等多个指标def multi_objective_fitness(individual): total_distance calculate_distance(individual) total_time calculate_time(individual) vehicle_cost calculate_vehicle_cost(individual) return total_distance, total_time, vehicle_cost在实际项目中遗传算法通常与其他优化技术结合使用初始种群优化使用节约算法等启发式方法生成优质初始解混合局部搜索在遗传算法中嵌入变邻域搜索等局部优化并行计算利用多核CPU或GPU加速进化过程