尧图网站建设 
简介MDVRP多配送中心车辆路径规划的MATLAB遗传算法求解实现主要面向物流、供应链与交通运输领域的算法研究者、竞赛参赛者及高年级本科生/研究生。该问题在VRP基础上引入多个配送中心与多车辆协同目标是在满足客户需求的前提下最小化总行驶距离或成本资源包提供了从问题建模、初始种群生成到遗传操作选择、交叉、变异的完整代码框架。压缩包共22个文件其中13个.mat数据文件包含多组不同规模、不同车辆数/容量系数的标准测试实例9个.m脚本和函数负责主流程、适应度计算、交叉变异算子以及结果可视化整体仅20KB紧凑易读、便于二次开发。目前已吸引379人浏览学习。通过学习这份资源读者既能快速跑通MDVRP算例并观察路径规划结果也能深入理解遗传算法在组合优化问题中的编码设计与算子实现为后续扩展时间窗、容量限制等约束或对比模拟退火、粒子群等算法打下基础。1. 多车场路径规划MDVRP 让 VRP 解法直接失效调度中心屏幕上同时亮着三个仓库的坐标每辆车从不同的车场出发订单散落在整个城市。如果你手上只有一套 VRP车辆路径问题的算法把多车场数据硬塞进去大概率得到一个“所有车都从一个点出发”的假设然后调度员看到方案里一半的车要先空驶几十公里去另一个车场——这种解法在真实物流场景里根本不敢用。MDVRPMulti-Depot Vehicle Routing Problem多车场车辆路径问题正是为此存在的模型多辆车、多中心、路径规划三者同时约束目标是让所有车从各自所属车场出发、服务完客户后返回原车场总成本最小。这篇文章面向做物流调度系统、算法选型或自研路径规划引擎的工程师讲清楚 MDVRP 的建模方法、可复现的求解代码、参数调优方向以及从静态模型走向动态避障场景时的改造思路。2. MDVRP 的数学模型与约束从 CVRP 扩展到多车场2.1 为什么不能直接把单车场模型套用到多车场单车场 CVRPCapacitated VRP带容量约束的车辆路径问题里所有车辆共享同一个出发点数学上只需要一个 depot 节点。换成 MDVRP问题立刻多了一个维度车与车场的归属关系。同一辆车从车场 A 出发就不能在中途去车场 B 补给这意味着每条路径的起点和终点都绑定在特定车场上。如果你把多个车场的数据直接拼成一个超级节点求解器会把车辆安排到错误的出发车场导致空驶成本被严重低估。另一个常见误区是“把多车场问题当作多 TSP 来解”。TSP 只关心一条回路怎么最短而 MDVRP 同时做三件事车辆分配给哪个车场、每条路径的服务顺序、以及车辆容量约束。如果只按距离聚类把客户分给最近车场每个簇内部再做 TSP 路径忽略了跨簇客户可以共享同一条路径的可能性最终总成本不一定最优。下面给出 MDVRP 的经典整数规划模型方便你确认自己落地时的约束边界。2.2 MDVRP 的集合、参数与决策变量定义MDVRP 的输入数据至少要包含三类信息车场集合、车辆集合、客户集合。设车场集合为 $D$客户集合为 $C$车辆集合为 $K$。每个车场 $d$ 拥有若干车辆每辆车 $k$ 的容量为 $Q_k$每个客户 $i$ 的需求量为 $q_i$节点 $i$ 与 $j$ 之间的距离或时间、成本为 $c_{ij}$。决策变量用二元变量 $x_{ijk}$ 表示车辆 $k$ 是否从节点 $i$ 直接行驶到节点 $j$用 $y_{ik}$ 表示车辆 $k$ 是否服务客户 $i$。目标函数是最小化所有车辆的总行驶距离$$ \min \sum_{k \in K} \sum_{i \in V} \sum_{j \in V} c_{ij} \cdot x_{ijk} $$约束条件分为四组。第一组是车场一致性约束每辆车 $k$ 的路径起点和终点必须属于同一个车场这要求每辆车 $k$ 至多关联一个车场 $d$且如果 $k$ 被使用路径上所有节点的车场归属必须一致。第二组是容量约束每辆车服务的客户总需求不超过其容量即 $\sum_{i \in C} q_i \cdot y_{ik} \le Q_k$。第三组是流守恒约束每个客户要么恰好被一辆车访问一次即 $\sum_{k} y_{ik} 1$且每个客户节点的入流等于出流。第四组是子回路消除约束防止出现不经过车场的巡回路线这一组约束在实现中最容易遗漏。2.2.1 MDVRP 与其他 VRP 变体的区别变体车场数量车辆返回原车场核心难点VRP1必须返回容量约束与路径优化MDVRP多个必须返回各自车场车辆与车场归属联合决策OVRP开放式1不要求返回路径是非闭合回路MDOVRP多个不要求返回车场选择与开放路径同时优化表格里的对比要点在于MDVRP 的复杂度主要来自车辆与车场的归属关系和距离不对称性耦合。如果你只需要车辆从就近车场出发那么这是一个较容易的聚类问题但真实场景中车辆有固定停放点不允许随意更换车场这就是完整 MDVRP 的约束来源。3. 用 OR-Tools 求解 MDVRP最小可跑通的 Python 代码3.1 为何选择 OR-Tools 而不是手写遗传算法MDVRP 属于 NP-hard 问题精确算法只能求解 50 个客户以内的实例。在生产系统中常见做法是用元启发式算法或商用求解器。Google OR-Tools 的 Routing Library 内置了 LNS大邻域搜索和 metaheuristic 机制支持自定义 start/end 索引天然适配多车场模型。相比手写遗传算法OR-Tools 的调参空间更小、收敛速度更稳而且对容量约束、时间窗约束都有现成 API不需要自己维护可行性检查逻辑。以下是基于 OR-Tools 的最小可运行代码数据用 2 个车场、4 辆车、16 个客户测试from ortools.constraint_solver import pywrapcp, routing_enums_pb2 import math # 节点 0,1 是车场节点 2~17 是客户 depot_ids [0, 1] customer_ids list(range(2, 18)) num_vehicles 4 # 车辆对应的起始车场0,1 号车从车场0出发2,3号车从车场1出发 vehicle_depots [0, 0, 1, 1] vehicle_capacities [100, 100, 80, 80] # 客户需求与 customer_ids 一一对应 demands [10, 20, 15, 18, 30, 8, 12, 25, 16, 14, 9, 22, 11, 19, 7, 13] # 构造节点坐标简化为二维平面实际可替换为经纬度 locations [(0, 0), (50, 50)] for i in range(len(customer_ids)): locations.append((30 i * 3, 20 (i % 5) * 7)) def distance_func(from_node, to_node): x1, y1 locations[from_node] x2, y2 locations[to_node] return int(math.sqrt((x1 - x2) ** 2 (y1 - y2) ** 2)) # 创建数据模型 data {} data[num_vehicles] num_vehicles data[depot_ids] depot_ids data[vehicle_depots] vehicle_depots data[demands] [0, 0] demands # 车场节点需求为0 data[vehicle_capacities] vehicle_capacities data[locations] locations # 初始化 RoutingIndexManager每个车场使用独立的 start/end index manager pywrapcp.RoutingIndexManager( len(locations), data[num_vehicles], vehicle_depots, vehicle_depots) routing pywrapcp.RoutingModel(manager) # 注册距离回调 def distance_callback(from_index, to_index): from_node manager.IndexToNode(from_index) to_node manager.IndexToNode(to_index) return distance_func(from_node, to_node) transit_callback_index routing.RegisterTransitCallback(distance_callback) routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # 注册需求回调并添加容量约束 def demand_callback(from_index): from_node manager.IndexToNode(from_index) return data[demands][from_node] demand_callback_index routing.RegisterUnaryTransitCallback(demand_callback) routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, # 无松弛量 data[vehicle_capacities], True, # 从车辆起始节点开始累计 Capacity) # 设置搜索策略先用路径最邻近启发式再模拟退火 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.SIMULATED_ANNEALING) search_parameters.time_limit.seconds 10 solution routing.SolveWithParameters(search_parameters)代码逻辑分四步说明车辆车场归属通过vehicle_depots列表传入RoutingIndexManager每个车辆分配独立的 start 节点和 end 节点索引这一步是 MDVRP 与单车场 VRP 实现的最大区别。容量约束使用AddDimensionWithVehicleCapacity创建累加维度参数0表示车辆在服务过程中的装载量不允许超过容量如果出现超载解会被直接判为不可行。first_solution_strategy指定初始解的构造方式PATH_CHEAPEST_ARC会优先选择每辆车的最便宜弧段适合多车场场景local_search_metaheuristic决定初始解之后的改进算法SIMULATED_ANNEALING对 MDVRP 这类多局部最优问题比较稳。time_limit.seconds 10是根据需要调整的核心参数一般 50 个客户以内 10 秒足够200 个客户建议 60 秒起步具体看你对解质量的要求。3.2 从 Solution 提取路径并输出多车场路由表求解完成后需要将Solution对象转换成可直接落地执行的路径列表方便后端系统接单派车。下面代码实现了路径提取和结果打印if solution: print(总行驶距离:, solution.ObjectiveValue()) for vehicle_id in range(data[num_vehicles]): index routing.Start(vehicle_id) route [] route_distance 0 while not routing.IsEnd(index): route.append(manager.IndexToNode(index)) previous_index index index solution.Value(routing.NextVar(index)) route_distance distance_func( manager.IndexToNode(previous_index), manager.IndexToNode(index)) route.append(manager.IndexToNode(index)) depot manager.IndexToNode(routing.Start(vehicle_id)) print(f车辆 {vehicle_id} (车场 {depot}): {route}) print(f 行驶距离: {route_distance}) else: print(未找到可行解请检查容量约束或时间限制)输出结果中每个车辆编号旁边会标注其出发车场方便调度系统按实际车场位置派单。解析路径时要注意manager.IndexToNode的转换routing.Start(id)返回的是内部索引不转换直接打印会得到错误的节点编号。4. MDVRP 求解器参数调优与解的合法性验证4.1 影响解质量的 5 个核心参数OR-Tools 的默认参数在大多数 VRP 实例上表现中等但 MDVRP 因为多了车场分配维度参数敏感度更高。下面列出我在实际项目中优先调整的五个参数以及对应的调整方向。参数默认值推荐调整策略影响方向first_solution_strategyPATH_CHEAPEST_ARC客户分布均匀用SAVINGS车场分散用CHRISTOFIDES影响初始解质量local_search_metaheuristicGUIDED_LOCAL_SEARCH大规模用TABU_SEARCH小规模用SIMULATED_ANNEALING决定局部搜索跳出能力time_limit.seconds无客户数×5 秒左右起步直接限制解质量上限log_searchFalse调试时开 True输出搜索过程solution_limitLong.MAX设定找到 N 个解即停控制最坏运行时间SAVINGS策略适合客户密集分布的场景因为它的核心思想是合并路径节省里程而 MDVRP 中节约里程的效果比单车场更明显。如果你的车场本身也分散在城区多个角落建议用CHRISTOFIDES它通过最小生成树和完美匹配构造可行解车场归属的处理更平滑。4.1.1 处理车辆容量不对称的常见误配置有一种典型误配置车辆容量不同但vehicle_capacities列表长度与num_vehicles不一致。OR-Tools 不会报数组越界但会导致部分车辆被默认分配容量 0解空间直接被砍掉一大半。调试方法是在求解前打印routing.vehicle_capacities确认每辆车的容量是否与业务配置一致。另一个容易被忽略的问题是需求数组的节点编号对齐。数据中如果客户节点编号从 0 开始但车场节点占用了 0、1后续客户节点编号会错位demand_callback返回的可能是错误客户的需求容量约束形同虚设。解决方法是把车场节点编号和客户节点编号分开维护在回调函数中通过manager.IndexToNode做统一映射。4.2 如何验证解是合法且接近最优的求解器输出的结果不一定是可行性最优解尤其是超过 100 个客户时需要验证每组路径的合法性。验证分三步先从解的路径中提取每个客户的访问次数保证每个客户恰好被访问一次其次检查每辆车的累积需求量是否小于等于容量最后统计每辆车的终点车场是否与起点车场一致。代码层面可以用下面的检查函数做快速验证def validate_mdvrp_solution(routing, solution, data): # 检查1: 每个客户是否被恰好访问一次 visit_count {} for vehicle_id in range(data[num_vehicles]): index routing.Start(vehicle_id) while not routing.IsEnd(index): node manager.IndexToNode(index) if node in customer_ids: visit_count[node] visit_count.get(node, 0) 1 index solution.Value(routing.NextVar(index)) for c in customer_ids: if visit_count.get(c, 0) ! 1: return False, f客户 {c} 访问次数为 {visit_count.get(c, 0)} # 检查2: 容量约束 for vehicle_id in range(data[num_vehicles]): index routing.Start(vehicle_id) load 0 while not routing.IsEnd(index): node manager.IndexToNode(index) load data[demands][node] if load data[vehicle_capacities][vehicle_id]: return False, f车辆 {vehicle_id} 超载: {load} index solution.Value(routing.NextVar(index)) # 检查3: 车场一致性OR-Tools 默认强制但防御性检查仍推荐 for vehicle_id in range(data[num_vehicles]): start_node manager.IndexToNode(routing.Start(vehicle_id)) end_node manager.IndexToNode(routing.End(vehicle_id)) if end_node ! start_node: # 注意start 和 end 相同的车场编号才合法 pass # 实际比对需要根据业务编号映射 return True, 合法这类验证逻辑在 CI 测试中建议保留防止后续改了数据格式后解的可信度悄悄下降。对于解的接近最优程度可以用下界评估把 MDVRP 松弛成不考虑车场归属的分配问题计算一个不考虑路径连续性的理论最小成本然后用求解器结果除以这个下界得到 gap。gap 在 20% 以内通常可以接受超过 30% 就需要调大时间限制或换 metaheuristic。5. 从静态解到动态避障MDVRP 的滚动时域更新技巧5.1 为什么静态最优解在真实路况中会失配MDVRP 模型本身假设距离矩阵是固定不变的但在城市配送场景中道路拥堵、临时封路、客户改单都会让“最优路径”变成“不可行路径”。如果你直接对每个新状态重新求解整个 MDVRP计算时长扛不住高频调用如果完全不重算路径偏离度会越来越大。工程上常见的做法是引入滚动时域Rolling Horizon重规划只在车辆到达某个关键节点或收到异常事件时触发局部重算。一个实用的触发条件表如下触发事件重算范围更新频率新订单插入受影响车辆路径高频按分钟道路封闭受影响区域内所有未完成路径中频每小时车辆故障该车剩余客户重新分配低频按需滚动时域的核心不是重新求解完整的 MDVRP而是锁定已完成的路径段只对未来时间窗内的节点做局部优化。这要求你的模型支持冻结某些弧段OR-Tools 中可以通过设置routing.NextVar的固定值来模拟已执行路径。5.2 动态避障场景的小规模重规划代码骨架def reoptimize_frozen_routes(routing, solution, frozen_vehicle_ids): # 对已冻结车辆强制其下一跳保持原计划 for vid in frozen_vehicle_ids: index routing.Start(vid) while not routing.IsEnd(index): next_node solution.Value(routing.NextVar(index)) # 固定弧段: 强制 NextVar 取原解的值 routing.NextVar(index).SetValues([next_node]) index next_node # 对未冻结车辆重新求解时间限制可以缩短 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.TABU_SEARCH) search_parameters.time_limit.seconds 5 new_solution routing.SolveWithParameters(search_parameters) return new_solution这里的核心技巧是SetValues方法它把车辆下一跳固定为原解求解器在构建邻域时会跳过这些弧段只搜索未冻结子集。这样每条车辆路径的计算规模从全局降为局部单次重算耗时可以在毫秒级到秒级。注意固定弧段不要过多否则剩余解空间太小容易得到局部次优解。一般建议冻结已完成 80% 路径的车辆其他车辆保持自由搜索。动态场景中路径规划算法从静态 MDVRP 延展到动态避障小车路径规划需要考虑的不只是距离矩阵变化还有车辆时间窗的连锁反应。如果你在 ROS 2 环境中做机器人多车调度同样的滚动时域思路可以直接复用只是把距离函数替换为实时路径规划模块输出的代价估计。最终记住一条原则静态求解保证方案质量动态重算保证方案可用两者交替执行才是生产级的做法。本文还有配套的精品资源点击获取 多车场路径规划MDVRP：从建模到OR-Tools求解与动态重规划
简介MDVRP多配送中心车辆路径规划的MATLAB遗传算法求解实现主要面向物流、供应链与交通运输领域的算法研究者、竞赛参赛者及高年级本科生/研究生。该问题在VRP基础上引入多个配送中心与多车辆协同目标是在满足客户需求的前提下最小化总行驶距离或成本资源包提供了从问题建模、初始种群生成到遗传操作选择、交叉、变异的完整代码框架。压缩包共22个文件其中13个.mat数据文件包含多组不同规模、不同车辆数/容量系数的标准测试实例9个.m脚本和函数负责主流程、适应度计算、交叉变异算子以及结果可视化整体仅20KB紧凑易读、便于二次开发。目前已吸引379人浏览学习。通过学习这份资源读者既能快速跑通MDVRP算例并观察路径规划结果也能深入理解遗传算法在组合优化问题中的编码设计与算子实现为后续扩展时间窗、容量限制等约束或对比模拟退火、粒子群等算法打下基础。1. 多车场路径规划MDVRP 让 VRP 解法直接失效调度中心屏幕上同时亮着三个仓库的坐标每辆车从不同的车场出发订单散落在整个城市。如果你手上只有一套 VRP车辆路径问题的算法把多车场数据硬塞进去大概率得到一个“所有车都从一个点出发”的假设然后调度员看到方案里一半的车要先空驶几十公里去另一个车场——这种解法在真实物流场景里根本不敢用。MDVRPMulti-Depot Vehicle Routing Problem多车场车辆路径问题正是为此存在的模型多辆车、多中心、路径规划三者同时约束目标是让所有车从各自所属车场出发、服务完客户后返回原车场总成本最小。这篇文章面向做物流调度系统、算法选型或自研路径规划引擎的工程师讲清楚 MDVRP 的建模方法、可复现的求解代码、参数调优方向以及从静态模型走向动态避障场景时的改造思路。2. MDVRP 的数学模型与约束从 CVRP 扩展到多车场2.1 为什么不能直接把单车场模型套用到多车场单车场 CVRPCapacitated VRP带容量约束的车辆路径问题里所有车辆共享同一个出发点数学上只需要一个 depot 节点。换成 MDVRP问题立刻多了一个维度车与车场的归属关系。同一辆车从车场 A 出发就不能在中途去车场 B 补给这意味着每条路径的起点和终点都绑定在特定车场上。如果你把多个车场的数据直接拼成一个超级节点求解器会把车辆安排到错误的出发车场导致空驶成本被严重低估。另一个常见误区是“把多车场问题当作多 TSP 来解”。TSP 只关心一条回路怎么最短而 MDVRP 同时做三件事车辆分配给哪个车场、每条路径的服务顺序、以及车辆容量约束。如果只按距离聚类把客户分给最近车场每个簇内部再做 TSP 路径忽略了跨簇客户可以共享同一条路径的可能性最终总成本不一定最优。下面给出 MDVRP 的经典整数规划模型方便你确认自己落地时的约束边界。2.2 MDVRP 的集合、参数与决策变量定义MDVRP 的输入数据至少要包含三类信息车场集合、车辆集合、客户集合。设车场集合为 $D$客户集合为 $C$车辆集合为 $K$。每个车场 $d$ 拥有若干车辆每辆车 $k$ 的容量为 $Q_k$每个客户 $i$ 的需求量为 $q_i$节点 $i$ 与 $j$ 之间的距离或时间、成本为 $c_{ij}$。决策变量用二元变量 $x_{ijk}$ 表示车辆 $k$ 是否从节点 $i$ 直接行驶到节点 $j$用 $y_{ik}$ 表示车辆 $k$ 是否服务客户 $i$。目标函数是最小化所有车辆的总行驶距离$$ \min \sum_{k \in K} \sum_{i \in V} \sum_{j \in V} c_{ij} \cdot x_{ijk} $$约束条件分为四组。第一组是车场一致性约束每辆车 $k$ 的路径起点和终点必须属于同一个车场这要求每辆车 $k$ 至多关联一个车场 $d$且如果 $k$ 被使用路径上所有节点的车场归属必须一致。第二组是容量约束每辆车服务的客户总需求不超过其容量即 $\sum_{i \in C} q_i \cdot y_{ik} \le Q_k$。第三组是流守恒约束每个客户要么恰好被一辆车访问一次即 $\sum_{k} y_{ik} 1$且每个客户节点的入流等于出流。第四组是子回路消除约束防止出现不经过车场的巡回路线这一组约束在实现中最容易遗漏。2.2.1 MDVRP 与其他 VRP 变体的区别变体车场数量车辆返回原车场核心难点VRP1必须返回容量约束与路径优化MDVRP多个必须返回各自车场车辆与车场归属联合决策OVRP开放式1不要求返回路径是非闭合回路MDOVRP多个不要求返回车场选择与开放路径同时优化表格里的对比要点在于MDVRP 的复杂度主要来自车辆与车场的归属关系和距离不对称性耦合。如果你只需要车辆从就近车场出发那么这是一个较容易的聚类问题但真实场景中车辆有固定停放点不允许随意更换车场这就是完整 MDVRP 的约束来源。3. 用 OR-Tools 求解 MDVRP最小可跑通的 Python 代码3.1 为何选择 OR-Tools 而不是手写遗传算法MDVRP 属于 NP-hard 问题精确算法只能求解 50 个客户以内的实例。在生产系统中常见做法是用元启发式算法或商用求解器。Google OR-Tools 的 Routing Library 内置了 LNS大邻域搜索和 metaheuristic 机制支持自定义 start/end 索引天然适配多车场模型。相比手写遗传算法OR-Tools 的调参空间更小、收敛速度更稳而且对容量约束、时间窗约束都有现成 API不需要自己维护可行性检查逻辑。以下是基于 OR-Tools 的最小可运行代码数据用 2 个车场、4 辆车、16 个客户测试from ortools.constraint_solver import pywrapcp, routing_enums_pb2 import math # 节点 0,1 是车场节点 2~17 是客户 depot_ids [0, 1] customer_ids list(range(2, 18)) num_vehicles 4 # 车辆对应的起始车场0,1 号车从车场0出发2,3号车从车场1出发 vehicle_depots [0, 0, 1, 1] vehicle_capacities [100, 100, 80, 80] # 客户需求与 customer_ids 一一对应 demands [10, 20, 15, 18, 30, 8, 12, 25, 16, 14, 9, 22, 11, 19, 7, 13] # 构造节点坐标简化为二维平面实际可替换为经纬度 locations [(0, 0), (50, 50)] for i in range(len(customer_ids)): locations.append((30 i * 3, 20 (i % 5) * 7)) def distance_func(from_node, to_node): x1, y1 locations[from_node] x2, y2 locations[to_node] return int(math.sqrt((x1 - x2) ** 2 (y1 - y2) ** 2)) # 创建数据模型 data {} data[num_vehicles] num_vehicles data[depot_ids] depot_ids data[vehicle_depots] vehicle_depots data[demands] [0, 0] demands # 车场节点需求为0 data[vehicle_capacities] vehicle_capacities data[locations] locations # 初始化 RoutingIndexManager每个车场使用独立的 start/end index manager pywrapcp.RoutingIndexManager( len(locations), data[num_vehicles], vehicle_depots, vehicle_depots) routing pywrapcp.RoutingModel(manager) # 注册距离回调 def distance_callback(from_index, to_index): from_node manager.IndexToNode(from_index) to_node manager.IndexToNode(to_index) return distance_func(from_node, to_node) transit_callback_index routing.RegisterTransitCallback(distance_callback) routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # 注册需求回调并添加容量约束 def demand_callback(from_index): from_node manager.IndexToNode(from_index) return data[demands][from_node] demand_callback_index routing.RegisterUnaryTransitCallback(demand_callback) routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, # 无松弛量 data[vehicle_capacities], True, # 从车辆起始节点开始累计 Capacity) # 设置搜索策略先用路径最邻近启发式再模拟退火 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.SIMULATED_ANNEALING) search_parameters.time_limit.seconds 10 solution routing.SolveWithParameters(search_parameters)代码逻辑分四步说明车辆车场归属通过vehicle_depots列表传入RoutingIndexManager每个车辆分配独立的 start 节点和 end 节点索引这一步是 MDVRP 与单车场 VRP 实现的最大区别。容量约束使用AddDimensionWithVehicleCapacity创建累加维度参数0表示车辆在服务过程中的装载量不允许超过容量如果出现超载解会被直接判为不可行。first_solution_strategy指定初始解的构造方式PATH_CHEAPEST_ARC会优先选择每辆车的最便宜弧段适合多车场场景local_search_metaheuristic决定初始解之后的改进算法SIMULATED_ANNEALING对 MDVRP 这类多局部最优问题比较稳。time_limit.seconds 10是根据需要调整的核心参数一般 50 个客户以内 10 秒足够200 个客户建议 60 秒起步具体看你对解质量的要求。3.2 从 Solution 提取路径并输出多车场路由表求解完成后需要将Solution对象转换成可直接落地执行的路径列表方便后端系统接单派车。下面代码实现了路径提取和结果打印if solution: print(总行驶距离:, solution.ObjectiveValue()) for vehicle_id in range(data[num_vehicles]): index routing.Start(vehicle_id) route [] route_distance 0 while not routing.IsEnd(index): route.append(manager.IndexToNode(index)) previous_index index index solution.Value(routing.NextVar(index)) route_distance distance_func( manager.IndexToNode(previous_index), manager.IndexToNode(index)) route.append(manager.IndexToNode(index)) depot manager.IndexToNode(routing.Start(vehicle_id)) print(f车辆 {vehicle_id} (车场 {depot}): {route}) print(f 行驶距离: {route_distance}) else: print(未找到可行解请检查容量约束或时间限制)输出结果中每个车辆编号旁边会标注其出发车场方便调度系统按实际车场位置派单。解析路径时要注意manager.IndexToNode的转换routing.Start(id)返回的是内部索引不转换直接打印会得到错误的节点编号。4. MDVRP 求解器参数调优与解的合法性验证4.1 影响解质量的 5 个核心参数OR-Tools 的默认参数在大多数 VRP 实例上表现中等但 MDVRP 因为多了车场分配维度参数敏感度更高。下面列出我在实际项目中优先调整的五个参数以及对应的调整方向。参数默认值推荐调整策略影响方向first_solution_strategyPATH_CHEAPEST_ARC客户分布均匀用SAVINGS车场分散用CHRISTOFIDES影响初始解质量local_search_metaheuristicGUIDED_LOCAL_SEARCH大规模用TABU_SEARCH小规模用SIMULATED_ANNEALING决定局部搜索跳出能力time_limit.seconds无客户数×5 秒左右起步直接限制解质量上限log_searchFalse调试时开 True输出搜索过程solution_limitLong.MAX设定找到 N 个解即停控制最坏运行时间SAVINGS策略适合客户密集分布的场景因为它的核心思想是合并路径节省里程而 MDVRP 中节约里程的效果比单车场更明显。如果你的车场本身也分散在城区多个角落建议用CHRISTOFIDES它通过最小生成树和完美匹配构造可行解车场归属的处理更平滑。4.1.1 处理车辆容量不对称的常见误配置有一种典型误配置车辆容量不同但vehicle_capacities列表长度与num_vehicles不一致。OR-Tools 不会报数组越界但会导致部分车辆被默认分配容量 0解空间直接被砍掉一大半。调试方法是在求解前打印routing.vehicle_capacities确认每辆车的容量是否与业务配置一致。另一个容易被忽略的问题是需求数组的节点编号对齐。数据中如果客户节点编号从 0 开始但车场节点占用了 0、1后续客户节点编号会错位demand_callback返回的可能是错误客户的需求容量约束形同虚设。解决方法是把车场节点编号和客户节点编号分开维护在回调函数中通过manager.IndexToNode做统一映射。4.2 如何验证解是合法且接近最优的求解器输出的结果不一定是可行性最优解尤其是超过 100 个客户时需要验证每组路径的合法性。验证分三步先从解的路径中提取每个客户的访问次数保证每个客户恰好被访问一次其次检查每辆车的累积需求量是否小于等于容量最后统计每辆车的终点车场是否与起点车场一致。代码层面可以用下面的检查函数做快速验证def validate_mdvrp_solution(routing, solution, data): # 检查1: 每个客户是否被恰好访问一次 visit_count {} for vehicle_id in range(data[num_vehicles]): index routing.Start(vehicle_id) while not routing.IsEnd(index): node manager.IndexToNode(index) if node in customer_ids: visit_count[node] visit_count.get(node, 0) 1 index solution.Value(routing.NextVar(index)) for c in customer_ids: if visit_count.get(c, 0) ! 1: return False, f客户 {c} 访问次数为 {visit_count.get(c, 0)} # 检查2: 容量约束 for vehicle_id in range(data[num_vehicles]): index routing.Start(vehicle_id) load 0 while not routing.IsEnd(index): node manager.IndexToNode(index) load data[demands][node] if load data[vehicle_capacities][vehicle_id]: return False, f车辆 {vehicle_id} 超载: {load} index solution.Value(routing.NextVar(index)) # 检查3: 车场一致性OR-Tools 默认强制但防御性检查仍推荐 for vehicle_id in range(data[num_vehicles]): start_node manager.IndexToNode(routing.Start(vehicle_id)) end_node manager.IndexToNode(routing.End(vehicle_id)) if end_node ! start_node: # 注意start 和 end 相同的车场编号才合法 pass # 实际比对需要根据业务编号映射 return True, 合法这类验证逻辑在 CI 测试中建议保留防止后续改了数据格式后解的可信度悄悄下降。对于解的接近最优程度可以用下界评估把 MDVRP 松弛成不考虑车场归属的分配问题计算一个不考虑路径连续性的理论最小成本然后用求解器结果除以这个下界得到 gap。gap 在 20% 以内通常可以接受超过 30% 就需要调大时间限制或换 metaheuristic。5. 从静态解到动态避障MDVRP 的滚动时域更新技巧5.1 为什么静态最优解在真实路况中会失配MDVRP 模型本身假设距离矩阵是固定不变的但在城市配送场景中道路拥堵、临时封路、客户改单都会让“最优路径”变成“不可行路径”。如果你直接对每个新状态重新求解整个 MDVRP计算时长扛不住高频调用如果完全不重算路径偏离度会越来越大。工程上常见的做法是引入滚动时域Rolling Horizon重规划只在车辆到达某个关键节点或收到异常事件时触发局部重算。一个实用的触发条件表如下触发事件重算范围更新频率新订单插入受影响车辆路径高频按分钟道路封闭受影响区域内所有未完成路径中频每小时车辆故障该车剩余客户重新分配低频按需滚动时域的核心不是重新求解完整的 MDVRP而是锁定已完成的路径段只对未来时间窗内的节点做局部优化。这要求你的模型支持冻结某些弧段OR-Tools 中可以通过设置routing.NextVar的固定值来模拟已执行路径。5.2 动态避障场景的小规模重规划代码骨架def reoptimize_frozen_routes(routing, solution, frozen_vehicle_ids): # 对已冻结车辆强制其下一跳保持原计划 for vid in frozen_vehicle_ids: index routing.Start(vid) while not routing.IsEnd(index): next_node solution.Value(routing.NextVar(index)) # 固定弧段: 强制 NextVar 取原解的值 routing.NextVar(index).SetValues([next_node]) index next_node # 对未冻结车辆重新求解时间限制可以缩短 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.TABU_SEARCH) search_parameters.time_limit.seconds 5 new_solution routing.SolveWithParameters(search_parameters) return new_solution这里的核心技巧是SetValues方法它把车辆下一跳固定为原解求解器在构建邻域时会跳过这些弧段只搜索未冻结子集。这样每条车辆路径的计算规模从全局降为局部单次重算耗时可以在毫秒级到秒级。注意固定弧段不要过多否则剩余解空间太小容易得到局部次优解。一般建议冻结已完成 80% 路径的车辆其他车辆保持自由搜索。动态场景中路径规划算法从静态 MDVRP 延展到动态避障小车路径规划需要考虑的不只是距离矩阵变化还有车辆时间窗的连锁反应。如果你在 ROS 2 环境中做机器人多车调度同样的滚动时域思路可以直接复用只是把距离函数替换为实时路径规划模块输出的代价估计。最终记住一条原则静态求解保证方案质量动态重算保证方案可用两者交替执行才是生产级的做法。本文还有配套的精品资源点击获取