别再硬啃理论了！用Python+遗传算法实战求解VRP（附完整代码与数据集）

用Python遗传算法实战求解车辆路径问题从理论到代码的完整指南物流配送、外卖调度、快递路线规划——这些看似日常的场景背后都隐藏着一个经典的运筹学难题车辆路径问题Vehicle Routing Problem, VRP。传统教材往往堆砌大量数学公式让初学者望而生畏。本文将带你用Python和遗传算法从零开始构建一个可运行的VRP求解器避开理论陷阱直接获得可复用的代码框架。1. 准备工作理解问题与工具链VRP的核心是在满足一系列约束条件下如车辆载重、客户时间窗等找到一组最优的配送路线使得总行驶距离或成本最小。我们以经典的A-n32-k5数据集为例该数据集包含1个仓库和31个客户点最优解需要5辆车总距离为784。1.1 必备工具安装首先确保你的Python环境已安装以下库pip install deap numpy matplotlibDEAP强大的进化算法框架NumPy高效的数值计算Matplotlib结果可视化1.2 数据结构设计VRP实例通常包含以下信息class VRPInstance: def __init__(self): self.depot None # 仓库坐标 self.customers [] # 客户列表每个客户包含坐标和需求量 self.vehicle_capacity 0 # 车辆载重上限2. 遗传算法框架搭建遗传算法模拟自然选择过程通过适者生存的机制逐步优化解决方案。我们将使用DEAP库快速构建算法框架。2.1 个体编码方案VRP的染色体需要表示多辆车的路径。我们采用基于客户编号的排列编码用分隔符表示不同车辆路线# 示例个体[1,5,3, 0, 2,6,4, 0, 7,8] # 其中0表示路线分隔符代表3辆车的路线2.2 DEAP初始化from deap import base, creator, tools # 定义适应度越小越好 creator.create(FitnessMin, base.Fitness, weights(-1.0,)) creator.create(Individual, list, fitnesscreator.FitnessMin) toolbox base.Toolbox() toolbox.register(indices, random.sample, range(1, num_customers1), num_customers) toolbox.register(individual, tools.initIterate, creator.Individual, toolbox.indices) toolbox.register(population, tools.initRepeat, list, toolbox.individual)3. 核心组件实现3.1 适应度函数设计适应度函数需要计算总行驶距离同时惩罚违反约束的解决方案def evaluate(individual, instance, penalty1000): total_distance 0 current_load 0 current_route [0] # 从仓库出发 for customer in individual: demand instance.customers[customer-1].demand if current_load demand instance.vehicle_capacity: # 返回仓库完成当前路线 current_route.append(0) total_distance calculate_route_distance(current_route, instance) # 开始新路线 current_route [0, customer] current_load demand else: current_route.append(customer) current_load demand # 添加最后一条路线 current_route.append(0) total_distance calculate_route_distance(current_route, instance) return total_distance,3.2 遗传算子定制**有序交叉(OX)**保持路径的相对顺序toolbox.register(mate, tools.cxOrdered)交换变异随机交换两个客户位置toolbox.register(mutate, tools.mutShuffleIndexes, indpb0.05)锦标赛选择toolbox.register(select, tools.selTournament, tournsize3)4. 算法执行与参数调优4.1 主进化循环def main(): pop toolbox.population(n300) CXPB, MUTPB, NGEN 0.7, 0.2, 100 # 评估初始种群 fitnesses list(map(toolbox.evaluate, pop)) for ind, fit in zip(pop, fitnesses): ind.fitness.values fit for g in range(NGEN): # 选择下一代 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() CXPB: toolbox.mate(child1, child2) del child1.fitness.values del child2.fitness.values # 变异 for mutant in offspring: if random.random() MUTPB: 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[:] offspring4.2 关键参数经验值参数推荐范围影响效果种群大小100-500越大搜索空间越广但计算成本增加交叉概率0.6-0.9控制新个体产生的速度变异概率0.01-0.1保持种群多样性进化代数50-200需要平衡收敛速度与计算时间5. 结果分析与可视化5.1 解的质量评估best_ind tools.selBest(pop, 1)[0] print(最优解总距离:, best_ind.fitness.values[0]) print(路线划分:, decode_routes(best_ind, instance))5.2 路线可视化def plot_routes(routes, instance): plt.figure(figsize(10,8)) # 绘制仓库 plt.plot(instance.depot.x, instance.depot.y, ks, markersize10) # 绘制客户点 for customer in instance.customers: plt.plot(customer.x, customer.y, bo) # 绘制路线 colors plt.cm.rainbow(np.linspace(0, 1, len(routes))) for route, color in zip(routes, colors): x [instance.depot.x] [instance.customers[i-1].x for i in route] [instance.depot.x] y [instance.depot.y] [instance.customers[i-1].y for i in route] [instance.depot.y] plt.plot(x, y, --, colorcolor, linewidth2) plt.show()5.3 进化过程监控# 记录每代最佳适应度 stats tools.Statistics(lambda ind: ind.fitness.values) stats.register(min, np.min) logbook tools.Logbook() logbook.record(gen0, **stats.compile(pop))6. 性能优化技巧6.1 局部搜索增强在遗传算法后加入2-opt局部优化def two_opt(route, instance): improved True while improved: improved False for i in range(1, len(route)-2): for j in range(i1, len(route)-1): # 计算交换前后的距离差 old_dist (distance(route[i-1], route[i], instance) distance(route[j], route[j1], instance)) new_dist (distance(route[i-1], route[j], instance) distance(route[i], route[j1], instance)) if new_dist old_dist: route[i:j1] route[j:i-1:-1] improved True return route6.2 并行化评估利用DEAP的并行评估功能加速计算from multiprocessing import Pool pool Pool() toolbox.register(map, pool.map)6.3 自适应参数调整根据种群多样性动态调整变异率def adaptive_mutation(pop, base_rate0.05): fits [ind.fitness.values[0] for ind in pop] diversity np.std(fits) / np.mean(fits) return base_rate * (1.5 - diversity)7. 工程实践建议数据预处理对客户点进行空间聚类可减少搜索空间约束处理逐步增加惩罚系数避免过早陷入局部最优混合算法结合禁忌搜索等局部优化方法提升解质量实时可视化在进化过程中动态展示当前最优解提示在实际物流系统中还需要考虑时间窗约束、多车型、动态需求等复杂因素。遗传算法作为元启发式方法可以灵活扩展适应这些需求。# 扩展适应度函数处理时间窗约束 def evaluate_with_time_windows(individual, instance): total_cost 0 current_time 0 for customer in individual: arrival_time current_time travel_time(current_pos, customer) if arrival_time customer.ready_time: # 等待成本 total_cost (customer.ready_time - arrival_time) * waiting_penalty elif arrival_time customer.due_time: # 延迟成本 total_cost (arrival_time - customer.due_time) * late_penalty current_time max(arrival_time, customer.ready_time) customer.service_time return total_cost,通过这个完整实现你应该已经掌握了用遗传算法解决VRP问题的核心方法。在实际项目中建议从简单版本开始逐步添加复杂约束和优化策略。遗传算法的魅力在于其灵活性——通过调整编码方案、适应度函数和遗传算子你可以解决各种变种的路径优化问题。