别再手动排路线了！用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 适应度函数

设计考虑三个关键因素：

1. 总行驶距离
2. 车辆使用数量
3. 载重约束违反程度

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, tournsize=3)

交叉算子：有序交叉(OX)

toolbox.register("mate", tools.cxOrdered)

变异算子：交换变异

toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05)

3. 完整算法实现

使用DEAP框架构建完整遗传算法流程：

from deap import base, creator, tools import random def genetic_algorithm_vrp(instance, pop_size=100, n_gen=500, cx_prob=0.8, mut_prob=0.2): # 定义问题类型 creator.create("FitnessMin", base.Fitness, weights=(-1.0,)) creator.create("Individual", list, fitness=creator.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, instance=instance) toolbox.register("mate", tools.cxOrdered) toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05) toolbox.register("select", tools.selTournament, tournsize=3) # 初始化种群 pop = toolbox.population(n=pop_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, k=1)[0]

4. 结果可视化与调优技巧

4.1 路径可视化

使用matplotlib绘制最优路径：

def plot_solution(instance, individual): plt.figure(figsize=(10, 8)) # 绘制配送中心 plt.scatter(instance.depot[0], instance.depot[1], c='red', s=200, marker='s', label='Depot') # 绘制客户点 x = [c[0] for c in instance.customers] y = [c[1] for c in instance.customers] plt.scatter(x, y, c='blue', s=100, label='Customers') # 绘制路径 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, '--', alpha=0.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, '--', alpha=0.5) plt.legend() plt.title('Vehicle Routing Solution') plt.show()

4.2 参数调优指南

实际项目中建议采用网格搜索寻找最优参数组合：

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 = params

5. 实际应用中的优化技巧

在真实物流场景中，我们还需要考虑以下实际问题：

• 动态需求处理：当有新订单到达时，如何高效更新现有路线

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[i+1] # 计算行驶时间 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

在实际项目中，遗传算法通常与其他优化技术结合使用：

1. 初始种群优化：使用节约算法等启发式方法生成优质初始解
2. 混合局部搜索：在遗传算法中嵌入变邻域搜索等局部优化
3. 并行计算：利用多核CPU或GPU加速进化过程