用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) }, # 更多订单... ]

关键预处理步骤：

1. 地理编码：将地址转换为经纬度坐标
2. 距离矩阵计算：使用Haversine公式计算各点间实际距离
3. 时间窗转换：将时间转换为分钟数便于计算

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 fitness

3. Python实现关键步骤与调优技巧

3.1 初始种群生成

def generate_individual(): # 随机排列所有订单 orders_permutation = np.random.permutation(len(orders)) # 随机插入分隔符 split_points = sorted(np.random.choice( range(1, len(orders)), size=rider_count-1, replace=False)) 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 individual

3.2 变异操作实现

我们设计了两种变异策略，根据概率随机选择：

1. 订单交换变异：随机交换两个订单的位置
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_point+1:] 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 individual

3.3 参数调优经验

通过多次实验，我们总结了以下参数设置经验：

4. 结果可视化与业务落地

4.1 路线可视化

使用folium库生成交互式地图展示优化结果：

def visualize_routes(routes): m = folium.Map(location=warehouse_location, zoom_start=14) # 绘制仓库位置 folium.Marker(warehouse_location, icon=folium.Icon(color='red')).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, icon=folium.Icon(color='lightgray')).add_to(m) # 标记送餐点 folium.Marker(delivery, popup=f"订单{order_idx}", icon=folium.Icon(color='lightblue')).add_to(m) points.append(warehouse_location) folium.PolyLine(points, color=path_color, weight=2.5, opacity=1).add_to(m) return m

4.2 实际应用效果

在某外卖站点的实测数据显示：

关键成功因素：

1. 与实际骑手沟通，了解他们的经验规则
2. 考虑交通高峰期和餐厅出餐速度的波动
3. 预留一定的缓冲时间应对意外情况

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_mode=True, initial_population=current_population)

5.2 多目标优化进阶

引入NSGA-II算法处理多个冲突目标：

1. 最小化总配送时间
2. 最小化骑手工作量差异
3. 最大化订单准时率
4. 最小化平台运营成本

5.3 扩展到其他场景

同样的方法可应用于：

• 社区团购的集中配送
• 快递员的揽件路线规划
• 共享单车调度车辆路径优化

在实际项目中，我们将算法封装为微服务，通过REST API提供给调度系统调用。一个典型的集成代码如下：

class RouteOptimizer: def __init__(self, config_file='config.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, key=self._evaluate)

这套系统已经在三个城市的200多个外卖站点部署，平均为每个骑手每天节省约15公里的骑行距离。最让我有成就感的是，一位资深骑手反馈说："现在系统给的路线比我跑了五年摸出来的经验路线还要合理，特别是午高峰的时候，能多送五六单。"