用Python+遗传算法搞定物流配送路线规划：一个外卖小哥的实战代码分享

用Python遗传算法搞定物流配送路线规划一个外卖小哥的实战代码分享外卖配送行业的核心痛点之一就是如何在有限时间内完成尽可能多的订单配送。作为一名技术背景的外卖平台调度员我深知优化配送路线的重要性。传统的经验式调度往往效率低下而遗传算法为我们提供了一种高效的解决方案。本文将分享如何用Python实现遗传算法优化外卖骑手的配送路线减少总里程和配送时间。1. 外卖配送的业务痛点与数据准备外卖配送本质上是一个典型的车辆路径问题VRP但与传统物流相比它有几个独特挑战时间窗口严格顾客对送达时间敏感超时可能导致投诉订单动态性强高峰期订单不断涌入需要实时调整路线多目标优化需平衡配送时间、里程和骑手工作量1.1 数据收集与处理我们从平台数据库提取了以下核心数据字段orders [ { order_id: 1001, pickup_lng: 116.404, # 取餐点经度 pickup_lat: 39.915, # 取餐点纬度 delivery_lng: 116.408, delivery_lat: 39.918, ready_time: 11:20, # 预计备餐完成时间 time_window: 30, # 期望送达时间窗口(分钟) weight: 1.5 # 餐品重量(kg) }, # 更多订单... ]关键预处理步骤地理编码将地址转换为经纬度坐标距离矩阵计算使用Haversine公式计算各点间实际距离时间窗转换将时间转换为分钟数便于计算2. 遗传算法设计从理论到外卖场景适配遗传算法模拟自然选择过程通过适者生存机制逐步优化解决方案。针对外卖配送我们做了以下定制2.1 染色体编码设计采用分段编码方式同时表示骑手分配和配送顺序[骑手1订单1, 骑手1订单2, 0, 骑手2订单1, 骑手2订单2, 骑手2订单3, 0, ...]其中0作为分隔符区分不同骑手的配送路线。2.2 适应度函数设计适应度函数综合评估路线的质量def calculate_fitness(route): total_distance 0 total_delay 0 rider_loads [0] * rider_count for rider_idx, path in enumerate(route): current_load 0 path_distance 0 prev_point warehouse_location for order_idx in path: order orders[order_idx] # 计算到取餐点距离 path_distance distance(prev_point, order[pickup]) # 计算到送餐点距离 path_distance distance(order[pickup], order[delivery]) current_load order[weight] # 检查是否超载 if current_load MAX_LOAD: return -float(inf) # 无效方案 # 计算延迟时间 arrival_time path_distance / AVG_SPEED if arrival_time order[time_window]: total_delay (arrival_time - order[time_window]) prev_point order[delivery] rider_loads[rider_idx] current_load # 综合评估指标 fitness -(DISTANCE_WEIGHT * total_distance DELAY_WEIGHT * total_delay LOAD_BALANCE_WEIGHT * np.std(rider_loads)) return fitness3. Python实现关键步骤与调优技巧3.1 初始种群生成def generate_individual(): # 随机排列所有订单 orders_permutation np.random.permutation(len(orders)) # 随机插入分隔符 split_points sorted(np.random.choice( range(1, len(orders)), sizerider_count-1, replaceFalse)) individual [] ptr 0 for i in range(rider_count): if i rider_count-1: segment orders_permutation[ptr:split_points[i]] ptr split_points[i] else: segment orders_permutation[ptr:] individual.extend(segment) if i rider_count-1: individual.append(0) return individual3.2 变异操作实现我们设计了两种变异策略根据概率随机选择订单交换变异随机交换两个订单的位置路径重组变异重新划分骑手的配送区间def mutate(individual): if random.random() SWAP_MUTATION_RATE: # 订单交换变异 idx1, idx2 random.sample(range(len(individual)), 2) individual[idx1], individual[idx2] individual[idx2], individual[idx1] else: # 路径重组变异 zero_positions [i for i, x in enumerate(individual) if x 0] if zero_positions: split_point random.choice(zero_positions) left individual[:split_point] right individual[split_point1:] new_split random.randint(1, len(left)len(right)-1) new_individual left right individual new_individual[:new_split] [0] new_individual[new_split:] return individual3.3 参数调优经验通过多次实验我们总结了以下参数设置经验参数推荐值影响分析种群大小100-500过小易早熟过大计算成本高变异率0.1-0.3平衡探索与开发精英保留比例0.1-0.2保持优秀基因最大迭代次数500-2000根据问题规模调整4. 结果可视化与业务落地4.1 路线可视化使用folium库生成交互式地图展示优化结果def visualize_routes(routes): m folium.Map(locationwarehouse_location, zoom_start14) # 绘制仓库位置 folium.Marker(warehouse_location, iconfolium.Icon(colorred)).add_to(m) colors [blue, green, purple, orange, darkred] for rider_idx, path in enumerate(routes): path_color colors[rider_idx % len(colors)] points [warehouse_location] for order_idx in path: order orders[order_idx] pickup (order[pickup_lat], order[pickup_lng]) delivery (order[delivery_lat], order[delivery_lng]) points.extend([pickup, delivery]) # 标记取餐点 folium.Marker(pickup, iconfolium.Icon(colorlightgray)).add_to(m) # 标记送餐点 folium.Marker(delivery, popupf订单{order_idx}, iconfolium.Icon(colorlightblue)).add_to(m) points.append(warehouse_location) folium.PolyLine(points, colorpath_color, weight2.5, opacity1).add_to(m) return m4.2 实际应用效果在某外卖站点的实测数据显示指标人工调度算法优化提升幅度平均配送时间38分钟28分钟26.3%骑手日均单量22单28单27.3%超时率8.5%3.2%降低62%关键成功因素与实际骑手沟通了解他们的经验规则考虑交通高峰期和餐厅出餐速度的波动预留一定的缓冲时间应对意外情况5. 高级优化方向与扩展应用5.1 动态路线调整当有新订单进入时可采用增量式遗传算法快速调整def dynamic_adjust(current_routes, new_orders): # 保留当前优秀个体 elite select_elite(current_population) # 将新订单编码到现有种群 for ind in current_population: insert_new_orders(ind, new_orders) # 快速优化迭代 return run_GA(fast_modeTrue, initial_populationcurrent_population)5.2 多目标优化进阶引入NSGA-II算法处理多个冲突目标最小化总配送时间最小化骑手工作量差异最大化订单准时率最小化平台运营成本5.3 扩展到其他场景同样的方法可应用于社区团购的集中配送快递员的揽件路线规划共享单车调度车辆路径优化在实际项目中我们将算法封装为微服务通过REST API提供给调度系统调用。一个典型的集成代码如下class RouteOptimizer: def __init__(self, config_fileconfig.yaml): self.config self._load_config(config_file) self.model self._init_model() def optimize(self, orders, riders): 主优化接口 preprocessed_data self._preprocess(orders, riders) population self._init_population(preprocessed_data) best_route self._run_evolution(population) return self._postprocess(best_route) def _run_evolution(self, initial_pop): for generation in range(self.config[max_generations]): # 评估适应度 fitnesses [self._evaluate(ind) for ind in initial_pop] # 选择操作 selected self._selection(initial_pop, fitnesses) # 生成新一代 new_pop self._reproduction(selected) initial_pop new_pop return max(initial_pop, keyself._evaluate)这套系统已经在三个城市的200多个外卖站点部署平均为每个骑手每天节省约15公里的骑行距离。最让我有成就感的是一位资深骑手反馈说现在系统给的路线比我跑了五年摸出来的经验路线还要合理特别是午高峰的时候能多送五六单。