别再硬啃理论了！用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 matplotlib- DEAP：强大的进化算法框架
- 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, fitness=creator.FitnessMin) toolbox = base.Toolbox() toolbox.register("indices", random.sample, range(1, num_customers+1), 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, penalty=1000): 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, indpb=0.05)锦标赛选择：
toolbox.register("select", tools.selTournament, tournsize=3)4. 算法执行与参数调优
4.1 主进化循环
def main(): pop = toolbox.population(n=300) 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', markersize=10) # 绘制客户点 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, '--', color=color, linewidth=2) plt.show()5.3 进化过程监控
# 记录每代最佳适应度 stats = tools.Statistics(lambda ind: ind.fitness.values) stats.register("min", np.min) logbook = tools.Logbook() logbook.record(gen=0, **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(i+1, len(route)-1): # 计算交换前后的距离差 old_dist = (distance(route[i-1], route[i], instance) + distance(route[j], route[j+1], instance)) new_dist = (distance(route[i-1], route[j], instance) + distance(route[i], route[j+1], instance)) if new_dist < old_dist: route[i:j+1] = 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_rate=0.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问题的核心方法。在实际项目中，建议从简单版本开始，逐步添加复杂约束和优化策略。遗传算法的魅力在于其灵活性——通过调整编码方案、适应度函数和遗传算子，你可以解决各种变种的路径优化问题。