简介面向多骑手同起点外卖配送场景的MATLAB优化方案主要解决多个订单从同一出发点分配骑手并规划高效路径的问题适合物流调度、路径规划或智能优化算法初学者参考。压缩包大小37KB内含多个MATLAB源函数与距离数据文件涵盖初始路径生成、最远插入、重新插入、变异及适应度计算等核心模块并配有距离矩阵数据便于直接运行和调试。方案整体采用遗传算法或类似全局优化思路通过初始化种群、适应度评估、路径调整和迭代进化最终输出较优配送路线并可视化展示。目前已有420人学习浏览代码虽精简但逻辑完整读者可据此理解配送调度问题的建模方法、启发式算子设计以及MATLAB算法实现细节也可在此基础上扩展为多约束、多目标的实际配送优化系统。1. 多骑手外卖配送同一起点出发这不是分单是路径规划一个餐厅同时涌进 10 个订单、5 个骑手在店里等着取餐最直觉的做法是每人 2 单、按顺序派。但稍一推演就会发现骑手 A 拿到的单分别在城南和城西骑手 B 的两单却在同一条路上路线交叉导致整体超时。这个场景在运筹学里对应带容量约束的车辆路径问题CVRP的特例——所有车辆从同一个车场出发服务完客户后允许不回场。放在即时配送语境里就是同起点的多骑手任务批量分派。做外卖平台调度、门店自配送、聚合配送系统的工程师迟早要面对这个问题如果只在谁少谁先分的层面写规则20 单以内还能凑合一旦进入午高峰、新订单持续插入、骑手回店重新领单的状态就必须换成真正的路径规划思路了。2. 把同起点配送建模成 VRP先有距离矩阵再谈骑手容量2.1 为什么均分订单在路线层面必然吃亏按订单数量均分的做法本质上是每次只给骑手追加当前最近的下一单属于贪心分配。它的致命问题在于服务顺序一旦确定后期没有一个环节能消除掉已经产生的交叉绕路。多做 1 公里的绕行直接影响的不只是配送费还有超时率。VRP 求解器跟贪心的本质差别是它在一次规划中同时决策两件事每个骑手承接哪些订单以及每个骑手按什么顺序完成这些订单。同一起点出发让问题在结构上被简化了一点所有路线共享同一个起点节点不需要处理骑手当前在哪个位置的起点异质问题。你只需用一个统一的起点索引去构造路径。但反过来它又叠加了另一个麻烦骑手从同一家店出发意味着他们会在同一时间涌向同一批方向如何避免路线重叠、如何让骑手之间负载均衡这些都不在普通求最短路径的算法范围内。所以第一步不是写分配规则而是把问题形式化成一个起点、多个骑手、每个骑手容量固定、目标是最小化总耗时的 CVRP 模型。2.2 距离矩阵优先用路网耗时而不是直线距离外卖配送的时间成本由路网、红绿灯、商家出餐时间决定两点之间的直线距离只能用于量级估算不能作为优化目标。生产环境里建议通过批量地理解析接口获取真实的路网耗时。常用的手段是用高德、百度或腾讯地图的矩阵接口一次请求能拿回 10×10 或 25×25 的起终点耗时矩阵。单位统一换算成秒后直接喂给求解器作为成本矩阵。# 以矩阵接口返回为例distance_matrix 的行是起点索引列是终点索引 # 索引 0 固定是餐厅1..n 是订单配送点数值单位是秒 # 真实接口返回后一般要做一次对称化和兜底处理 distance_matrix [ [0, 900, 1200], # 0 到 0 是 00 到 1 是 900 秒0 到 2 是 1200 秒 [800, 0, 600], # 1 到 0 是 800 秒回程1 到 2 是 600 秒 [1000, 700, 0] # 2 到 0 是 1000 秒 ]这段矩阵的含义要看清两个细节对角线必须是 0非对称是常态因为单行道、过街天桥、小区门禁方向都会让 A→B 和 B→A 的耗时不同。在 OR-Tools 里距离矩阵不需要提前对称化求解器天然支持非对称成本。但要小心矩阵接口在部分跨城或偏远地址会返回异常值所以程序里需要做一层兜底把超大值或空值替换成该行的最大值或者直接用直线距离乘以一个经验系数 1.5 填充避免求解器因为一个坏数据把整条路线带歪。2.3 容量约束把骑手最多拿几单写进模型每个骑手一次能带的订单量是有限的这是 CVRP 里的容量约束。电瓶车后座箱体的空间、取餐后保温袋的容量、以及骑手对多单路线的熟悉程度都会影响这个值。容量设置过小骑手需求数量变多平台运力成本上升容量设置过大单个骑手可能拿到 810 单最后一单已经凉透。实践里我一般按商圈热度和平均配送距离来定3 公里以内的单建议容量上限 635 公里的单建议 4超过 5 公里建议 23。ORM-Tools 的容量约束通过回调函数实现不是直接传一个数字。这一点经常让第一次接触的人困惑你设定的 capacity 只是上限求解器在路径构建的每一步都会调用回调去累加当前节点的需求量。可以在回调里把每个订单的重量都设为 1这样容量就等于骑手的最大接单数。如果以后要扩展到重量体积冷热分离的多维度容量比如饮料杯数和大体积外卖不能混装就需要把需求量改成一个向量并实现多维累加判断。2.4 起终点与骑手归店同起点场景的一个分支决策同一起点出发还有一种常见变体骑手送完所有单之后是直接结束回家还是必须回到餐厅等待下一次派单。这个决策影响求解器是否要加回程成本。外卖场景里骑手通常不回店而是留在配送末端等系统派新单所以模型里一般把不强制回库当成默认行为。OR-Tools 通过设置 pickup/delivery 或直接不添加 return-to-depot 的约束来模拟这一点。对不想深入研究 CVRP 细节的人最简单的方式是先跑必须回程的模型看结果里回程耗时占比是否超过 15%如果超过再去掉回程约束通常总耗时会有明显下降。3. 用 OR-Tools 跑通 5 骑手 30 单的最小算例3.1 最小代码30 个订单 5 个骑手的一次求解OR-Tools 的 routing 模块是 Google 维护的开源求解器内部封装了 CP-SAT 和局部搜索算法对中小规模 CVRP 的求解速度远快于自己写遗传算法。下面是一个可以直接运行的最小算例30 个订单、5 个骑手、容量上限 6出发点固定为索引 0。from ortools.constraint_solver import pywrapcp, routing_enums_pb2 # 1. 构造数据0 是餐厅1..30 是订单点 # 实际生产中用距离矩阵接口的返回值替换这里 distance_matrix [[0] * 31 for _ in range(31)] for i in range(1, 31): distance_matrix[0][i] 600 i * 10 # 模拟餐厅到各点耗时 distance_matrix[i][0] 500 i * 8 # 模拟回程耗时 for i in range(1, 31): for j in range(1, 31): distance_matrix[i][j] abs(i - j) * 50 300 demands [0] [1] * 30 # 每个订单需求量记为 1 num_vehicles 5 vehicle_capacity 6 # 每名骑手最多带 6 单 depot_index 0 # 2. 创建索引管理器与模型 manager pywrapcp.RoutingIndexManager( len(distance_matrix), num_vehicles, depot_index) routing pywrapcp.RoutingModel(manager) # 3. 注册距离回调 def distance_callback(from_index, to_index): from_node manager.IndexToNode(from_index) to_node manager.IndexToNode(to_index) return distance_matrix[from_node][to_node] distance_cb_index routing.RegisterTransitCallback(distance_callback) routing.SetArcCostEvaluatorOfAllVehicles(distance_cb_index) # 4. 注册容量回调 def demand_callback(from_index): from_node manager.IndexToNode(from_index) return demands[from_node] demand_cb_index routing.RegisterUnaryTransitCallback(demand_callback) routing.AddDimensionWithVehicleCapacity( demand_cb_index, 0, [vehicle_capacity] * num_vehicles, True, capacity) # 5. 配置启发式与局部搜索并加上求解时间上限 search_parameters pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) search_parameters.local_search_metaheuristic ( routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH) search_parameters.time_limit.FromSeconds(10) # 6. 求解并输出 solution routing.SolveWithParameters(search_parameters) if solution: for vehicle_id in range(num_vehicles): index routing.Start(vehicle_id) route_nodes [] route_seconds 0 while not routing.IsEnd(index): route_nodes.append(manager.IndexToNode(index)) next_index solution.Value(routing.NextVar(index)) route_seconds distance_matrix[ manager.IndexToNode(index)][manager.IndexToNode(next_index)] index next_index route_nodes.append(0) print(f骑手{vehicle_id}: {route_nodes}总耗时 {route_seconds} 秒)代码里有几个关键点需要解释。第 4 步的AddDimensionWithVehicleCapacity是所有约束里最容易被写错的位置第二个参数 0 是每个节点允许的等待时间松弛量True 表示按起点方向进行容量累加。如果把容量设成 6 但 demand_callback 返回的是总数量求解器会在一条路径上累计到第 7 单时强制拆分到下一辆车。第 5 步的PATH_CHEAPEST_ARC是在做初始解时优先选择单段代价最小的边这个策略在同起点场景下收敛很快GUIDED_LOCAL_SEARCH则负责在初始解基础上跳出局部最优。时间上限 10 秒在 30 单 5 车这种规模下通常能收敛到接近最优不需要再往上加。3.2 影响路线质量的四个参数策略、扰动、时间和目标第一个是first_solution_strategy。除了PATH_CHEAPEST_ARC还有SAVINGS节省法和SWEEP扫描法。同一起点、订单在餐厅周边呈扇形分布时SWEEP的初始解通常更接近人力分配直觉按照订单点的极角排序后切块。但SWEEP对前置的距离矩阵没有预评估容易在高密度区域出现局部堆积。我在生产环境里的做法是同一份数据分别跑一轮PATH_CHEAPEST_ARC和SWEEP取总耗时的较小值牺牲少量计算时间换取质量。第二个是local_search_metaheuristic。GUIDED_LOCAL_SEARCH适合有大量局部极小值的配送网络但它的收敛速度比SIMULATED_ANNEALING慢。订单量在 50 以下时推荐直接上GUIDED_LOCAL_SEARCH10 秒内结果稳定订单量到了 100 以上SIMULATED_ANNEALING配合更长的求解时间反而效果更好。第三个是time_limit。这不是越大越好。线上调度一般要求 13 秒内返回计划离线预排单可以放宽到 30 秒。一个经验值是每增加 10 个订单点、或每增加 2 辆骑手车时间上限至少增加 2 秒否则局部搜索跑不完一轮完整的邻域交换。第四个是目标函数的定义。OR-Tools 默认最小化总行驶时间但你可以在SetArcCostEvaluatorOfAllVehicles之外再叠加一个软时间窗惩罚。对即时配送来说单纯最小化总里程会牺牲部分订单的时效。常见做法是把每超过时限 1 分钟的惩罚系数乘以 60 秒加进距离回调让求解器在绕路 400 米和超时 2 分钟之间自己做权衡。3.3 求解结果怎么落到调度台求解器输出的是每个骑手节点索引的访问顺序但这个顺序不直接等同于派单顺序。在代码示例里我把节点 0 作为回程终点加入了数组这使得输出的最后一项总是 0。实际写生产代码时要过滤掉头尾的 0并把这个顺序映射成取餐 配送两个阶段。同一家店出发意味着所有订单的取餐点相同所以骑手路线在系统里展示出来的其实是纯配送顺序。还有一类隐藏信息值得从解里提取每个骑手路线中的最大行驶距离和最小行驶距离之差。如果这个差值大于 500 米调度台上的骑手会有明显的有的在跑有的在等的状态这是运力分布不均的信号。后续可以在 OR-Tools 模型里增加一个辅助维度对每个车辆的总耗时做范围约束强制把差值控制在设置值内。4. 时间窗、动态新单插入与求解器变慢的三个坑4.1 时间窗硬约束写进模型软约束写进成本外卖场景的时间窗不是一个固定区间而是承诺送达时间点加上一个容忍浮动。比较好的建模方式是分为硬时间窗和软时间窗。硬时间窗表示该订单必须在餐厅出餐后 40 分钟内送到这个约束直接加入 OR-Tools 的时间维度。软时间窗则不做强约束而是通过惩罚系数体现在成本里。硬约束写多了会让可行解空间急剧缩小在高峰期容易出现无解软时间窗把超时变成一种可以接受的代价由目标函数去平衡总配送时长和超时单量。OR-Tools 的时间窗维度需要为每个订单点设置一个区间[min_time, max_time]并把行驶耗时和等待松弛一起放入维度time_cb_index routing.RegisterTransitCallback( lambda f, t: distance_matrix[manager.IndexToNode(f)][manager.IndexToNode(t)] ) routing.AddDimension( time_cb_index, 1200, 3600, True, time) time_dim routing.GetDimensionOrDie(time) for node in range(1, 31): min_time 600 node * 5 max_time 1800 node * 8 time_dim.CumulVar(node).SetRange(min_time, max_time)AddDimension的第二个参数 1200 是最大松弛时间表示骑手可以在节点上多等 20 分钟第三个参数 3600 是单个骑手路线的全局时间上限。这两个值如果设得过于宽松求解器会找出先等后送的路线来逃避时间窗冲突如果设过紧高峰期会无解。我一般把松弛时间限制在 300 秒以下不让骑手等待成为默认策略。4.2 新订单插入动态场景下的局部重排静态排单只适合下单后五秒内、还没有骑手出发的场景。实际运行中骑手已经在路上新订单进来后要做的是插入而非全量重排。插入逻辑不一定要交给求解器一个小规模邻域搜索加贪心通常就够了。常见的做法是先把距离新订单最近的三个骑手路线取出来把新订单依次插到他们的每个可能位置计算插入后绕行距离增量选增量最小的方案。这个过程可以在 50 毫秒内完成对线上体验影响很小。如果插入后任何一个骑手的剩余可接单数变成负数或者某条路线的时间窗被破坏就放弃该插入位置转投下一个候选骑手。def best_insertion(new_order, routes, distance_matrix): best_gap float(inf) best_route None best_pos None for rid, route in routes.items(): # 依次尝试所有插入位置计算增量成本 for pos in range(1, len(route)): before route[pos - 1] after route[pos] delta ( distance_matrix[before][new_order] distance_matrix[new_order][after] - distance_matrix[before][after] ) if delta best_gap: best_gap delta best_route rid best_pos pos return best_route, best_pos, best_gap这段代码的核心是增量计算。插入成本不是新订单到前后两个点的耗时相加而是加一个替换操作原来从 before 直接去 after现在改为 before 去 new_order、new_order 去 after把这两段的和与原来一段的差作为代价。这样得到的 delta 是真实绕路量。需要考虑路网非对称时 before→new_order、new_order→after 使用的是矩阵里不同方向的数值delta 可能是负值——如果出现负值说明新订单恰好落在原路线折返点上插入后反而缩短了距离这种情况一定要允许插入。4.3 三个会让求解器明显变慢的配置第一个坑是距离矩阵没有预处理。直接填接口返回的原始秒数数值范围在 3003000 之间这对 OR-Tools 的邻域搜索没有影响但如果矩阵里有大量 99999 这样的填充值求解器会把它们当成真实大代价去搜索拖慢收敛。建议在喂给模型之前把所有不可达节点替换成一个小于最大合法值的惩罚值。第二个坑是车辆数远多于实际需要。同一起点出 10 单配 5 个骑手模型允许 5 条路线同时存在但其实 3 条就能装下全部订单。多余车辆会让求解器多出大量空跑路线的组合搜索。可以通过把车辆数设置成订单总量除以容量上限的向上取整再强制空车路线不允许出现求解速度会立刻改善。第三个坑是容量维度设置过大。骑手能拿 20 单时单条路线包含的节点数变长局部搜索的邻域规模指数级增加。订单量超过 80、单条容量超过 8 时OR-Tools 的求解时间会从秒级涨到分钟级。此时需要认真考虑下面的两阶段算法。5. 订单量超过 80先用 K-Means 聚出方向再对每个方向跑 TSP5.1 为什么直接全量求解会失控当同一起点的订单数超过 80OR-Tools 的 RoutingModel 即使在 30 秒内也能返回一个解但这个解的质量往往不如人工经验。原因在于全量 CVRP 的搜索空间正比于节点数的平方乘以片段数局部搜索每次交换邻域的复杂度会显著上升。对即时配送来说高峰期延迟 3 秒以上订单的取值和出餐状态已经变了解算得再精确也没有意义。此时我更倾向于两阶段法第一阶段用聚类算法把所有订单按空间位置切分成若干簇簇的数量大致等于骑手数量第二阶段在每一簇内部独立求解一个旅行商问题TSP只优化访问顺序不再处理骑手间的交叉问题。这种思想的本质是把谁去哪和先送谁两个问题拆开分别用不同的算法去解决牺牲少量全局最优性换取分钟内出解的能力。5.2 K-Means 加最小坐标映射的落地代码from sklearn.cluster import KMeans import geopy.distance # coords: List[(lat, lng)]第一个元素是餐厅坐标 # 订单点按经纬度聚类簇数等于骑手数 coords [(39.90, 116.40), (39.91, 116.41), ...] locations coords[1:] kmeans KMeans(n_clusters5, random_state0).fit(locations) labels kmeans.labels_ # 聚完簇后按簇收集订单再分别跑 OR-Tools 的 TSP clusters {i: [] for i in range(5)} for idx, label in enumerate(labels): clusters[label].append(idx 1)聚类完成不代表路线可用。K-Means 用的是欧氏距离而配送耗时受路网影响两个在坐标上很近的点可能因为快速路的阻隔实际要绕很大一圈。所以真正的生产流程是聚类生成簇后取出每个簇的订单点重新构造该簇的距离矩阵再喂给 TSP 求解器。跨簇的解需要再合并一次如果两个相邻簇的总耗时都不超过 40 分钟而且簇边界订单之间距离小于 500 米就尝试把两个簇合并成一个用 TSP 重解一次通常会找到比单独解更短的路线。5.3 验证方案质量绕路率和最长单线时长两阶段法跑完后不要只看总里程。对齐业务上关心的两个指标绕路率和最长单线时长。绕路率的定义是所有骑手的实际总行驶时间减去它们各自路线首尾直线距离估算时间之和再除以估算时间总和。绕路率超过 30% 说明聚类或路线顺序不合理优先检查簇与簇之间是否存在 1 公里以上的重叠区域。最长单线时长的定义是单个骑手从餐厅出发到完成最后一单的时间这个值超过 50 分钟就说明该路线承载了太多订单需要回退到上一轮结果并调大簇数。验证手段也不能只靠模拟。生产环境里建议留存一份一周的历史订单数据把每个订单的实际完成时间、骑手轨迹、取餐等待时间记录下来回放历史数据做批量化仿真。仿真时把已完成订单的起点和时间码输入到离线求解器得到的新方案和实际执行方案对比就能算出理论优化空间。这个回放系统是迭代调度参数最重要的基础设施比任何一次性的在线验证都有说服力。最后还有一个更贴近骑手体验的细节同一起点出发时每个骑手路线的前几个订单点尽量不要让两名骑手的路线交叉。聚类已经天然规避了大部分交叉但 TSP 求解时不同簇的边界点仍然可能产生路线重叠。出现这种情况时不需要重新聚类把边界上的订单交换到另一队列里即可——让谁离哪个簇的质心更近决定归属是最简单且有效的修正策略。本文还有配套的精品资源点击获取
基于OR-Tools的同起点外卖配送路径规划实战
简介面向多骑手同起点外卖配送场景的MATLAB优化方案主要解决多个订单从同一出发点分配骑手并规划高效路径的问题适合物流调度、路径规划或智能优化算法初学者参考。压缩包大小37KB内含多个MATLAB源函数与距离数据文件涵盖初始路径生成、最远插入、重新插入、变异及适应度计算等核心模块并配有距离矩阵数据便于直接运行和调试。方案整体采用遗传算法或类似全局优化思路通过初始化种群、适应度评估、路径调整和迭代进化最终输出较优配送路线并可视化展示。目前已有420人学习浏览代码虽精简但逻辑完整读者可据此理解配送调度问题的建模方法、启发式算子设计以及MATLAB算法实现细节也可在此基础上扩展为多约束、多目标的实际配送优化系统。1. 多骑手外卖配送同一起点出发这不是分单是路径规划一个餐厅同时涌进 10 个订单、5 个骑手在店里等着取餐最直觉的做法是每人 2 单、按顺序派。但稍一推演就会发现骑手 A 拿到的单分别在城南和城西骑手 B 的两单却在同一条路上路线交叉导致整体超时。这个场景在运筹学里对应带容量约束的车辆路径问题CVRP的特例——所有车辆从同一个车场出发服务完客户后允许不回场。放在即时配送语境里就是同起点的多骑手任务批量分派。做外卖平台调度、门店自配送、聚合配送系统的工程师迟早要面对这个问题如果只在谁少谁先分的层面写规则20 单以内还能凑合一旦进入午高峰、新订单持续插入、骑手回店重新领单的状态就必须换成真正的路径规划思路了。2. 把同起点配送建模成 VRP先有距离矩阵再谈骑手容量2.1 为什么均分订单在路线层面必然吃亏按订单数量均分的做法本质上是每次只给骑手追加当前最近的下一单属于贪心分配。它的致命问题在于服务顺序一旦确定后期没有一个环节能消除掉已经产生的交叉绕路。多做 1 公里的绕行直接影响的不只是配送费还有超时率。VRP 求解器跟贪心的本质差别是它在一次规划中同时决策两件事每个骑手承接哪些订单以及每个骑手按什么顺序完成这些订单。同一起点出发让问题在结构上被简化了一点所有路线共享同一个起点节点不需要处理骑手当前在哪个位置的起点异质问题。你只需用一个统一的起点索引去构造路径。但反过来它又叠加了另一个麻烦骑手从同一家店出发意味着他们会在同一时间涌向同一批方向如何避免路线重叠、如何让骑手之间负载均衡这些都不在普通求最短路径的算法范围内。所以第一步不是写分配规则而是把问题形式化成一个起点、多个骑手、每个骑手容量固定、目标是最小化总耗时的 CVRP 模型。2.2 距离矩阵优先用路网耗时而不是直线距离外卖配送的时间成本由路网、红绿灯、商家出餐时间决定两点之间的直线距离只能用于量级估算不能作为优化目标。生产环境里建议通过批量地理解析接口获取真实的路网耗时。常用的手段是用高德、百度或腾讯地图的矩阵接口一次请求能拿回 10×10 或 25×25 的起终点耗时矩阵。单位统一换算成秒后直接喂给求解器作为成本矩阵。# 以矩阵接口返回为例distance_matrix 的行是起点索引列是终点索引 # 索引 0 固定是餐厅1..n 是订单配送点数值单位是秒 # 真实接口返回后一般要做一次对称化和兜底处理 distance_matrix [ [0, 900, 1200], # 0 到 0 是 00 到 1 是 900 秒0 到 2 是 1200 秒 [800, 0, 600], # 1 到 0 是 800 秒回程1 到 2 是 600 秒 [1000, 700, 0] # 2 到 0 是 1000 秒 ]这段矩阵的含义要看清两个细节对角线必须是 0非对称是常态因为单行道、过街天桥、小区门禁方向都会让 A→B 和 B→A 的耗时不同。在 OR-Tools 里距离矩阵不需要提前对称化求解器天然支持非对称成本。但要小心矩阵接口在部分跨城或偏远地址会返回异常值所以程序里需要做一层兜底把超大值或空值替换成该行的最大值或者直接用直线距离乘以一个经验系数 1.5 填充避免求解器因为一个坏数据把整条路线带歪。2.3 容量约束把骑手最多拿几单写进模型每个骑手一次能带的订单量是有限的这是 CVRP 里的容量约束。电瓶车后座箱体的空间、取餐后保温袋的容量、以及骑手对多单路线的熟悉程度都会影响这个值。容量设置过小骑手需求数量变多平台运力成本上升容量设置过大单个骑手可能拿到 810 单最后一单已经凉透。实践里我一般按商圈热度和平均配送距离来定3 公里以内的单建议容量上限 635 公里的单建议 4超过 5 公里建议 23。ORM-Tools 的容量约束通过回调函数实现不是直接传一个数字。这一点经常让第一次接触的人困惑你设定的 capacity 只是上限求解器在路径构建的每一步都会调用回调去累加当前节点的需求量。可以在回调里把每个订单的重量都设为 1这样容量就等于骑手的最大接单数。如果以后要扩展到重量体积冷热分离的多维度容量比如饮料杯数和大体积外卖不能混装就需要把需求量改成一个向量并实现多维累加判断。2.4 起终点与骑手归店同起点场景的一个分支决策同一起点出发还有一种常见变体骑手送完所有单之后是直接结束回家还是必须回到餐厅等待下一次派单。这个决策影响求解器是否要加回程成本。外卖场景里骑手通常不回店而是留在配送末端等系统派新单所以模型里一般把不强制回库当成默认行为。OR-Tools 通过设置 pickup/delivery 或直接不添加 return-to-depot 的约束来模拟这一点。对不想深入研究 CVRP 细节的人最简单的方式是先跑必须回程的模型看结果里回程耗时占比是否超过 15%如果超过再去掉回程约束通常总耗时会有明显下降。3. 用 OR-Tools 跑通 5 骑手 30 单的最小算例3.1 最小代码30 个订单 5 个骑手的一次求解OR-Tools 的 routing 模块是 Google 维护的开源求解器内部封装了 CP-SAT 和局部搜索算法对中小规模 CVRP 的求解速度远快于自己写遗传算法。下面是一个可以直接运行的最小算例30 个订单、5 个骑手、容量上限 6出发点固定为索引 0。from ortools.constraint_solver import pywrapcp, routing_enums_pb2 # 1. 构造数据0 是餐厅1..30 是订单点 # 实际生产中用距离矩阵接口的返回值替换这里 distance_matrix [[0] * 31 for _ in range(31)] for i in range(1, 31): distance_matrix[0][i] 600 i * 10 # 模拟餐厅到各点耗时 distance_matrix[i][0] 500 i * 8 # 模拟回程耗时 for i in range(1, 31): for j in range(1, 31): distance_matrix[i][j] abs(i - j) * 50 300 demands [0] [1] * 30 # 每个订单需求量记为 1 num_vehicles 5 vehicle_capacity 6 # 每名骑手最多带 6 单 depot_index 0 # 2. 创建索引管理器与模型 manager pywrapcp.RoutingIndexManager( len(distance_matrix), num_vehicles, depot_index) routing pywrapcp.RoutingModel(manager) # 3. 注册距离回调 def distance_callback(from_index, to_index): from_node manager.IndexToNode(from_index) to_node manager.IndexToNode(to_index) return distance_matrix[from_node][to_node] distance_cb_index routing.RegisterTransitCallback(distance_callback) routing.SetArcCostEvaluatorOfAllVehicles(distance_cb_index) # 4. 注册容量回调 def demand_callback(from_index): from_node manager.IndexToNode(from_index) return demands[from_node] demand_cb_index routing.RegisterUnaryTransitCallback(demand_callback) routing.AddDimensionWithVehicleCapacity( demand_cb_index, 0, [vehicle_capacity] * num_vehicles, True, capacity) # 5. 配置启发式与局部搜索并加上求解时间上限 search_parameters pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) search_parameters.local_search_metaheuristic ( routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH) search_parameters.time_limit.FromSeconds(10) # 6. 求解并输出 solution routing.SolveWithParameters(search_parameters) if solution: for vehicle_id in range(num_vehicles): index routing.Start(vehicle_id) route_nodes [] route_seconds 0 while not routing.IsEnd(index): route_nodes.append(manager.IndexToNode(index)) next_index solution.Value(routing.NextVar(index)) route_seconds distance_matrix[ manager.IndexToNode(index)][manager.IndexToNode(next_index)] index next_index route_nodes.append(0) print(f骑手{vehicle_id}: {route_nodes}总耗时 {route_seconds} 秒)代码里有几个关键点需要解释。第 4 步的AddDimensionWithVehicleCapacity是所有约束里最容易被写错的位置第二个参数 0 是每个节点允许的等待时间松弛量True 表示按起点方向进行容量累加。如果把容量设成 6 但 demand_callback 返回的是总数量求解器会在一条路径上累计到第 7 单时强制拆分到下一辆车。第 5 步的PATH_CHEAPEST_ARC是在做初始解时优先选择单段代价最小的边这个策略在同起点场景下收敛很快GUIDED_LOCAL_SEARCH则负责在初始解基础上跳出局部最优。时间上限 10 秒在 30 单 5 车这种规模下通常能收敛到接近最优不需要再往上加。3.2 影响路线质量的四个参数策略、扰动、时间和目标第一个是first_solution_strategy。除了PATH_CHEAPEST_ARC还有SAVINGS节省法和SWEEP扫描法。同一起点、订单在餐厅周边呈扇形分布时SWEEP的初始解通常更接近人力分配直觉按照订单点的极角排序后切块。但SWEEP对前置的距离矩阵没有预评估容易在高密度区域出现局部堆积。我在生产环境里的做法是同一份数据分别跑一轮PATH_CHEAPEST_ARC和SWEEP取总耗时的较小值牺牲少量计算时间换取质量。第二个是local_search_metaheuristic。GUIDED_LOCAL_SEARCH适合有大量局部极小值的配送网络但它的收敛速度比SIMULATED_ANNEALING慢。订单量在 50 以下时推荐直接上GUIDED_LOCAL_SEARCH10 秒内结果稳定订单量到了 100 以上SIMULATED_ANNEALING配合更长的求解时间反而效果更好。第三个是time_limit。这不是越大越好。线上调度一般要求 13 秒内返回计划离线预排单可以放宽到 30 秒。一个经验值是每增加 10 个订单点、或每增加 2 辆骑手车时间上限至少增加 2 秒否则局部搜索跑不完一轮完整的邻域交换。第四个是目标函数的定义。OR-Tools 默认最小化总行驶时间但你可以在SetArcCostEvaluatorOfAllVehicles之外再叠加一个软时间窗惩罚。对即时配送来说单纯最小化总里程会牺牲部分订单的时效。常见做法是把每超过时限 1 分钟的惩罚系数乘以 60 秒加进距离回调让求解器在绕路 400 米和超时 2 分钟之间自己做权衡。3.3 求解结果怎么落到调度台求解器输出的是每个骑手节点索引的访问顺序但这个顺序不直接等同于派单顺序。在代码示例里我把节点 0 作为回程终点加入了数组这使得输出的最后一项总是 0。实际写生产代码时要过滤掉头尾的 0并把这个顺序映射成取餐 配送两个阶段。同一家店出发意味着所有订单的取餐点相同所以骑手路线在系统里展示出来的其实是纯配送顺序。还有一类隐藏信息值得从解里提取每个骑手路线中的最大行驶距离和最小行驶距离之差。如果这个差值大于 500 米调度台上的骑手会有明显的有的在跑有的在等的状态这是运力分布不均的信号。后续可以在 OR-Tools 模型里增加一个辅助维度对每个车辆的总耗时做范围约束强制把差值控制在设置值内。4. 时间窗、动态新单插入与求解器变慢的三个坑4.1 时间窗硬约束写进模型软约束写进成本外卖场景的时间窗不是一个固定区间而是承诺送达时间点加上一个容忍浮动。比较好的建模方式是分为硬时间窗和软时间窗。硬时间窗表示该订单必须在餐厅出餐后 40 分钟内送到这个约束直接加入 OR-Tools 的时间维度。软时间窗则不做强约束而是通过惩罚系数体现在成本里。硬约束写多了会让可行解空间急剧缩小在高峰期容易出现无解软时间窗把超时变成一种可以接受的代价由目标函数去平衡总配送时长和超时单量。OR-Tools 的时间窗维度需要为每个订单点设置一个区间[min_time, max_time]并把行驶耗时和等待松弛一起放入维度time_cb_index routing.RegisterTransitCallback( lambda f, t: distance_matrix[manager.IndexToNode(f)][manager.IndexToNode(t)] ) routing.AddDimension( time_cb_index, 1200, 3600, True, time) time_dim routing.GetDimensionOrDie(time) for node in range(1, 31): min_time 600 node * 5 max_time 1800 node * 8 time_dim.CumulVar(node).SetRange(min_time, max_time)AddDimension的第二个参数 1200 是最大松弛时间表示骑手可以在节点上多等 20 分钟第三个参数 3600 是单个骑手路线的全局时间上限。这两个值如果设得过于宽松求解器会找出先等后送的路线来逃避时间窗冲突如果设过紧高峰期会无解。我一般把松弛时间限制在 300 秒以下不让骑手等待成为默认策略。4.2 新订单插入动态场景下的局部重排静态排单只适合下单后五秒内、还没有骑手出发的场景。实际运行中骑手已经在路上新订单进来后要做的是插入而非全量重排。插入逻辑不一定要交给求解器一个小规模邻域搜索加贪心通常就够了。常见的做法是先把距离新订单最近的三个骑手路线取出来把新订单依次插到他们的每个可能位置计算插入后绕行距离增量选增量最小的方案。这个过程可以在 50 毫秒内完成对线上体验影响很小。如果插入后任何一个骑手的剩余可接单数变成负数或者某条路线的时间窗被破坏就放弃该插入位置转投下一个候选骑手。def best_insertion(new_order, routes, distance_matrix): best_gap float(inf) best_route None best_pos None for rid, route in routes.items(): # 依次尝试所有插入位置计算增量成本 for pos in range(1, len(route)): before route[pos - 1] after route[pos] delta ( distance_matrix[before][new_order] distance_matrix[new_order][after] - distance_matrix[before][after] ) if delta best_gap: best_gap delta best_route rid best_pos pos return best_route, best_pos, best_gap这段代码的核心是增量计算。插入成本不是新订单到前后两个点的耗时相加而是加一个替换操作原来从 before 直接去 after现在改为 before 去 new_order、new_order 去 after把这两段的和与原来一段的差作为代价。这样得到的 delta 是真实绕路量。需要考虑路网非对称时 before→new_order、new_order→after 使用的是矩阵里不同方向的数值delta 可能是负值——如果出现负值说明新订单恰好落在原路线折返点上插入后反而缩短了距离这种情况一定要允许插入。4.3 三个会让求解器明显变慢的配置第一个坑是距离矩阵没有预处理。直接填接口返回的原始秒数数值范围在 3003000 之间这对 OR-Tools 的邻域搜索没有影响但如果矩阵里有大量 99999 这样的填充值求解器会把它们当成真实大代价去搜索拖慢收敛。建议在喂给模型之前把所有不可达节点替换成一个小于最大合法值的惩罚值。第二个坑是车辆数远多于实际需要。同一起点出 10 单配 5 个骑手模型允许 5 条路线同时存在但其实 3 条就能装下全部订单。多余车辆会让求解器多出大量空跑路线的组合搜索。可以通过把车辆数设置成订单总量除以容量上限的向上取整再强制空车路线不允许出现求解速度会立刻改善。第三个坑是容量维度设置过大。骑手能拿 20 单时单条路线包含的节点数变长局部搜索的邻域规模指数级增加。订单量超过 80、单条容量超过 8 时OR-Tools 的求解时间会从秒级涨到分钟级。此时需要认真考虑下面的两阶段算法。5. 订单量超过 80先用 K-Means 聚出方向再对每个方向跑 TSP5.1 为什么直接全量求解会失控当同一起点的订单数超过 80OR-Tools 的 RoutingModel 即使在 30 秒内也能返回一个解但这个解的质量往往不如人工经验。原因在于全量 CVRP 的搜索空间正比于节点数的平方乘以片段数局部搜索每次交换邻域的复杂度会显著上升。对即时配送来说高峰期延迟 3 秒以上订单的取值和出餐状态已经变了解算得再精确也没有意义。此时我更倾向于两阶段法第一阶段用聚类算法把所有订单按空间位置切分成若干簇簇的数量大致等于骑手数量第二阶段在每一簇内部独立求解一个旅行商问题TSP只优化访问顺序不再处理骑手间的交叉问题。这种思想的本质是把谁去哪和先送谁两个问题拆开分别用不同的算法去解决牺牲少量全局最优性换取分钟内出解的能力。5.2 K-Means 加最小坐标映射的落地代码from sklearn.cluster import KMeans import geopy.distance # coords: List[(lat, lng)]第一个元素是餐厅坐标 # 订单点按经纬度聚类簇数等于骑手数 coords [(39.90, 116.40), (39.91, 116.41), ...] locations coords[1:] kmeans KMeans(n_clusters5, random_state0).fit(locations) labels kmeans.labels_ # 聚完簇后按簇收集订单再分别跑 OR-Tools 的 TSP clusters {i: [] for i in range(5)} for idx, label in enumerate(labels): clusters[label].append(idx 1)聚类完成不代表路线可用。K-Means 用的是欧氏距离而配送耗时受路网影响两个在坐标上很近的点可能因为快速路的阻隔实际要绕很大一圈。所以真正的生产流程是聚类生成簇后取出每个簇的订单点重新构造该簇的距离矩阵再喂给 TSP 求解器。跨簇的解需要再合并一次如果两个相邻簇的总耗时都不超过 40 分钟而且簇边界订单之间距离小于 500 米就尝试把两个簇合并成一个用 TSP 重解一次通常会找到比单独解更短的路线。5.3 验证方案质量绕路率和最长单线时长两阶段法跑完后不要只看总里程。对齐业务上关心的两个指标绕路率和最长单线时长。绕路率的定义是所有骑手的实际总行驶时间减去它们各自路线首尾直线距离估算时间之和再除以估算时间总和。绕路率超过 30% 说明聚类或路线顺序不合理优先检查簇与簇之间是否存在 1 公里以上的重叠区域。最长单线时长的定义是单个骑手从餐厅出发到完成最后一单的时间这个值超过 50 分钟就说明该路线承载了太多订单需要回退到上一轮结果并调大簇数。验证手段也不能只靠模拟。生产环境里建议留存一份一周的历史订单数据把每个订单的实际完成时间、骑手轨迹、取餐等待时间记录下来回放历史数据做批量化仿真。仿真时把已完成订单的起点和时间码输入到离线求解器得到的新方案和实际执行方案对比就能算出理论优化空间。这个回放系统是迭代调度参数最重要的基础设施比任何一次性的在线验证都有说服力。最后还有一个更贴近骑手体验的细节同一起点出发时每个骑手路线的前几个订单点尽量不要让两名骑手的路线交叉。聚类已经天然规避了大部分交叉但 TSP 求解时不同簇的边界点仍然可能产生路线重叠。出现这种情况时不需要重新聚类把边界上的订单交换到另一队列里即可——让谁离哪个簇的质心更近决定归属是最简单且有效的修正策略。本文还有配套的精品资源点击获取
 深度解析：从滑动窗口原理到高效张量操作实践)
