从外卖配送看算法实战：Python+NetworkX解决简化版VRP问题

外卖配送路径优化实战：用Python+NetworkX解决简化版VRP问题

中午12点，城市里的外卖订单如潮水般涌来。配送员小张的手机上瞬间出现了8个不同方向的订单，他盯着地图上分散的标记点皱起了眉头——怎样才能用最短的时间送完所有外卖？这背后隐藏的正是运筹学中的经典难题：车辆路径规划问题(VRP)。本文将带你用Python和NetworkX库，从零构建一个简化版的外卖配送优化系统。

1. 理解外卖配送中的VRP问题

外卖配送本质上是一个带容量约束的车辆路径问题(CVRP)。想象你管理着一个外卖站，每天需要安排骑手配送数十个订单。每个订单有特定的送货地点和预计配送时间，而每位骑手的电动车电池容量和餐箱空间都有限制。我们的目标是设计一套算法，在满足以下约束条件下，找到总路程最短的配送方案：

• 单车辆容量限制：每位骑手一次最多携带5份外卖
• 时间窗口要求：所有订单需在60分钟内送达
• 路径连通性：配送路线必须形成闭合环路（从站点出发最后返回站点）

传统的人工排班方式往往依赖经验，难以应对订单量的突然波动。而基于图论的算法解决方案，能够快速生成较优路径，将平均配送效率提升30%以上。下面这张表展示了人工调度与算法调度的关键差异：

提示：在实际商业系统中，还会考虑实时交通数据、骑手当前位置等多维因素，本文重点讲解核心的路径规划算法框架。

2. 构建配送网络图模型

首先需要将实际问题抽象为图论模型。我们用NetworkX创建加权图结构，其中：

• 节点(Node)：代表配送站点和客户地址
• 边(Edge)：连接节点的路径，权重为实际距离或行驶时间
• 图属性：存储骑手容量、订单需求等约束条件

import networkx as nx import matplotlib.pyplot as plt # 初始化有向图（考虑单行道等实际情况） G = nx.DiGraph() # 添加节点：0为配送站，1-8为客户点 locations = { 0: "配送站", 1: "科技大厦A座", 2: "中央公寓3栋", 3: "金融中心B塔", 4: "大学城食堂", 5: "医院急诊部", 6: "体育场西门", 7: "购物中心北门", 8: "公园东侧门" } # 各节点需求（负值表示配送站库存） demands = {0: -15, 1: 2, 2: 1, 3: 3, 4: 4, 5: 1, 6: 2, 7: 1, 8: 1} # 添加带需求的节点 for node in locations: G.add_node(node, demand=demands[node], label=locations[node]) # 添加边及其权重（行驶分钟数） edges = [ (0,1,8), (0,2,12), (0,3,9), (1,2,5), (1,4,14), (2,3,7), (2,5,15), (3,6,11), (4,5,6), (4,7,10), (5,6,9), (5,8,13), (6,0,7), (7,8,4), (8,0,6) ] G.add_weighted_edges_from(edges) # 可视化网络 pos = nx.spring_layout(G) nx.draw(G, pos, with_labels=True, labels=locations, node_size=500) edge_labels = nx.get_edge_attributes(G, "weight") nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels) plt.show()

这段代码构建了一个包含9个节点的配送网络，其中：

• 节点0是配送中心（需求为-15，表示初始有15份外卖待配送）
• 节点1-8是客户点（正需求表示需要配送的外卖数量）
• 边权重代表两点间的行驶时间（分钟）

3. 实现贪心插入算法

对于中小规模的外卖配送问题（<20个点），贪心算法能在毫秒级给出可行解。我们设计一个基于最近邻策略的启发式算法：

1. 初始化路线：从配送站出发的空路线
2. 订单分配：将未分配订单按距离当前路线的最短插入成本排序
3. 可行性检查：确保插入后不超过车辆容量限制
4. 迭代优化：直到所有订单被分配

def greedy_vrp(G, depot=0, capacity=5, max_iter=100): unvisited = [n for n in G.nodes if n != depot and G.nodes[n]['demand'] > 0] routes = [[depot, depot]] current_loads = [0] while unvisited and max_iter > 0: max_iter -= 1 best_cost = float('inf') best_route = None best_node = None best_pos = None for node in unvisited: for i, route in enumerate(routes): if current_loads[i] + G.nodes[node]['demand'] > capacity: continue for j in range(1, len(route)): cost = (G[route[j-1]][node]['weight'] + G[node][route[j]]['weight'] - G[route[j-1]][route[j]]['weight']) if cost < best_cost: best_cost = cost best_node = node best_route = i best_pos = j if best_node is None: # 需要新增一辆车 routes.append([depot, depot]) current_loads.append(0) continue routes[best_route].insert(best_pos, best_node) current_loads[best_route] += G.nodes[best_node]['demand'] unvisited.remove(best_node) return routes # 执行算法 routes = greedy_vrp(G) print("生成的配送路线：", routes) # 计算总耗时 total_time = sum(sum(G[route[i]][route[i+1]]['weight'] for i in range(len(route)-1)) for route in routes) print("预计总行驶时间：", total_time, "分钟")

典型输出可能如下：

生成的配送路线： [[0, 1, 2, 3, 6, 0], [0, 4, 5, 8, 0], [0, 7, 0]] 预计总行驶时间： 72 分钟

注意：实际应用中需要添加异常处理，比如当某个客户点无法被任何路线服务时（距离过远或需求过大），应触发特殊处理流程。

4. 进阶优化：2-opt局部搜索

基础贪心算法生成的路线常有交叉等低效路径。我们引入2-opt优化技术进行后处理：

def two_opt_swap(route, i, j): return route[:i] + route[i:j+1][::-1] + route[j+1:] def route_cost(G, route): return sum(G[route[k]][route[k+1]]['weight'] for k in range(len(route)-1)) def optimize_route(G, route, max_iter=50): improved = True best_route = route best_cost = route_cost(G, route) while improved and max_iter > 0: max_iter -= 1 improved = False for i in range(1, len(route)-2): for j in range(i+1, len(route)-1): new_route = two_opt_swap(route, i, j) new_cost = route_cost(G, new_route) if new_cost < best_cost: best_route = new_route best_cost = new_cost improved = True route = best_route return best_route # 优化所有路线 optimized_routes = [optimize_route(G, r) for r in routes] print("优化后的路线：", optimized_routes) # 比较优化效果 original_total = sum(route_cost(G, r) for r in routes) optimized_total = sum(route_cost(G, r) for r in optimized_routes) print(f"优化节省时间：{original_total - optimized_total}分钟 ({((original_total - optimized_total)/original_total)*100:.1f}%)")

经过2-opt优化后，相同实例通常能获得5-15%的额外效率提升。下表对比了三种策略的效果：

5. 系统集成与实战建议

将上述算法投入实际应用还需要考虑以下工程化因素：

1. 实时数据接入：

   # 模拟实时订单更新 def update_network(G, new_orders): for node, demand in new_orders.items(): G.nodes[node]['demand'] += demand if demand > 0 and node not in G: # 添加新节点和边 G.add_node(node, demand=demand) # 需要补充邻近边数据 G.add_edge(0, node, weight=estimate_distance(node))

2. 动态调整策略：

   • 当新订单到达时，评估插入现有路线的最小成本位置
   • 设置重新优化阈值（如新增订单量>20%时触发全局重新规划）

3. 可视化监控界面：

   # 使用Plotly实现交互式路线图 import plotly.graph_objects as go def plot_routes(G, routes): edge_x, edge_y = [], [] for route in routes: for i in range(len(route)-1): x0, y0 = pos[route[i]] x1, y1 = pos[route[i+1]] edge_x.extend([x0, x1, None]) edge_y.extend([y0, y1, None]) fig = go.Figure() fig.add_trace(go.Scatter(x=edge_x, y=edge_y, line=dict(width=0.5, color='gray'), hoverinfo='none', mode='lines')) node_x, node_y, node_text = [], [], [] for node in G.nodes(): x, y = pos[node] node_x.append(x) node_y.append(y) node_text.append(G.nodes[node]['label']) fig.add_trace(go.Scatter(x=node_x, y=node_y, text=node_text, mode='markers+text', marker=dict(size=12, color='lightblue'))) fig.show()

在实际部署中发现几个关键经验：

• 将算法封装为微服务，通过REST API提供路径规划服务
• 为骑手APP提供实时导航和任务提醒功能
• 设置算法保护机制，当计算超时(>500ms)时自动回退到分区调度模式
• 定期用历史数据训练距离预测模型，提高权重估计准确性