Python实战：用遗传算法搞定外卖骑手路径规划（附完整代码）

Python实战：用遗传算法优化外卖骑手路径规划（附完整代码）

外卖配送效率直接影响用户体验和平台运营成本。传统人工调度方式难以应对高峰期的订单激增，而智能路径规划算法能自动生成最优配送方案。本文将手把手教你用Python实现遗传算法，解决外卖骑手路径规划问题。

1. 问题建模与场景分析

外卖配送本质上属于带时间窗的车辆路径问题（VRPTW）。我们需要考虑以下核心要素：

• 配送点：每个订单对应一个配送位置，包含经纬度坐标和期望送达时间
• 骑手属性：电动车续航里程、载货箱容量、工作时长限制
• 优化目标：最小化总配送时长、减少骑手数量、平衡各骑手工作量

典型业务约束包括：

1. 每个订单只能由一位骑手配送
2. 骑手载重不超过保温箱容量（如5kg）
3. 订单需在承诺时间内送达（如30分钟）
4. 骑手连续工作不超过8小时

class Order: def __init__(self, id, lat, lng, weight, prepare_time, promise_duration): self.id = id self.location = (lat, lng) # 经纬度坐标 self.weight = weight # 订单重量(kg) self.promise_time = prepare_time + promise_duration # 最晚送达时间戳 class Rider: def __init__(self, id, max_load, max_hours): self.id = id self.max_load = max_load # 最大载重(kg) self.max_hours = max_hours # 最长工作时间(小时)

2. 遗传算法设计要点

2.1 染色体编码方案

采用分段编码方式，用0分隔不同骑手的配送路线。例如编码[3,1,2,0,5,4]表示：

• 骑手A路线：订单3 → 订单1 → 订单2
• 骑手B路线：订单5 → 订单4

def generate_individual(orders, rider_count): """随机生成初始个体""" genes = orders.copy() random.shuffle(genes) # 插入分隔符 for _ in range(rider_count - 1): pos = random.randint(1, len(genes)-1) genes.insert(pos, 0) return genes

2.2 适应度函数设计

综合评估三个关键指标：

1. 总配送时长（从接单到最后一单送达）
2. 总行驶距离（所有骑手路径之和）
3. 骑手使用数量

def calculate_fitness(individual, orders_dict, riders): total_time = 0 total_distance = 0 used_riders = 0 current_rider = riders[0] current_load = 0 path = [] for gene in individual: if gene == 0: # 切换到下个骑手 if path: used_riders += 1 path = [] current_rider = riders[used_riders] current_load = 0 else: order = orders_dict[gene] if current_load + order.weight > current_rider.max_load: return -float('inf') # 超载则适应度为负无穷 path.append(order) current_load += order.weight # 计算路径时间和距离 # ... 实际实现需要调用地图API计算路线 # 加权得分（数值越大越好） return -(0.5*total_time + 0.3*total_distance + 0.2*used_riders)

3. 核心算法实现

3.1 种群初始化

创建包含多个个体的初始种群，确保多样性：

def initialize_population(pop_size, orders, rider_count): return [generate_individual(orders, rider_count) for _ in range(pop_size)]

3.2 选择操作

采用锦标赛选择策略，保留优质基因：

def selection(population, fitnesses, elite_size): # 保留精英个体 elite_indices = np.argsort(fitnesses)[-elite_size:] elites = [population[i] for i in elite_indices] # 锦标赛选择 selected = [] for _ in range(len(population) - elite_size): candidates = random.sample(range(len(population)), 3) winner = max(candidates, key=lambda x: fitnesses[x]) selected.append(population[winner]) return elites + selected

3.3 变异操作

设计三种变异方式增强搜索能力：

1. 交换变异：随机交换两个订单位置
2. 逆转变异：反转路线片段顺序
3. 迁移变异：将订单转移到其他骑手路线

def mutate(individual, mutation_rate): if random.random() > mutation_rate: return individual mutation_type = random.choice(['swap', 'reverse', 'move']) if mutation_type == 'swap': i, j = random.sample(range(len(individual)), 2) individual[i], individual[j] = individual[j], individual[i] elif mutation_type == 'reverse': start, end = sorted(random.sample(range(len(individual)), 2)) individual[start:end+1] = individual[start:end+1][::-1] elif mutation_type == 'move': non_zero = [i for i, g in enumerate(individual) if g != 0] if len(non_zero) < 2: return individual src = random.choice(non_zero) dest = random.choice([i for i in range(len(individual)) if i != src]) individual.insert(dest, individual.pop(src)) return individual

4. 完整算法流程

将各组件整合为完整遗传算法：

def genetic_algorithm(orders, riders, pop_size=100, elite_size=20, mutation_rate=0.1, generations=500): order_ids = [o.id for o in orders] orders_dict = {o.id: o for o in orders} # 初始化 population = initialize_population(pop_size, order_ids, len(riders)) best_fitness = -float('inf') best_individual = None for gen in range(generations): # 评估适应度 fitnesses = [calculate_fitness(ind, orders_dict, riders) for ind in population] # 更新最优解 current_best = max(fitnesses) if current_best > best_fitness: best_fitness = current_best best_index = fitnesses.index(current_best) best_individual = population[best_index] # 选择 new_population = selection(population, fitnesses, elite_size) # 变异 population = [mutate(ind, mutation_rate) for ind in new_population] return decode_solution(best_individual, orders_dict, riders)

5. 实际应用优化技巧

5.1 距离矩阵预计算

使用Google Maps API或OSRM提前计算所有订单点间的行驶距离和时间：

from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def create_distance_matrix(locations): """调用地图API生成距离矩阵""" # 实际实现需要调用地图服务 return distance_matrix

5.2 并行化评估

利用多进程加速适应度计算：

from multiprocessing import Pool def evaluate_population(population): with Pool() as p: return p.map(calculate_fitness, population)

5.3 动态参数调整

根据进化过程自动调整变异率：

def adaptive_mutation_rate(gen, max_gen): base_rate = 0.1 return base_rate * (1 - gen/max_gen)

6. 效果评估与可视化

使用Matplotlib展示优化结果：

import matplotlib.pyplot as plt def plot_solution(solution, orders): fig, ax = plt.subplots(figsize=(10, 8)) # 绘制骑手路线 colors = plt.cm.tab10.colors for i, route in enumerate(solution.routes): x = [o.location[0] for o in route] y = [o.location[1] for o in route] ax.plot(x, y, 'o-', color=colors[i], label=f'Rider {i+1}') ax.legend() plt.show()

典型优化效果对比：

7. 工程实践建议

1. 实时性处理：每小时重新运行算法，吸收新订单并考虑骑手当前位置
2. 异常处理：为骑手预留20%容量缓冲应对订单取消或新增
3. 硬件部署：使用Redis缓存距离矩阵，减少API调用开销
4. A/B测试：对比算法调度与人工调度效果，持续优化权重参数

# 实际部署示例 while True: current_orders = get_new_orders() active_riders = get_available_riders() if time_to_replan() or significant_change(): solution = genetic_algorithm(current_orders, active_riders) dispatch_orders(solution) time.sleep(60) # 每分钟检查一次

通过遗传算法实现的外卖路径规划系统，某外卖平台在试点城市实现了配送时效提升22%，骑手日均配送单量增加15%。这种技术方案特别适合订单密集的一二线城市，能有效降低运营成本的同时提升用户体验。