上个月给一家生鲜公司做配送系统升级3个前置仓、180个客户点、12台冷链车主题就是典型的多配送中心车辆路径优化Multi-Depot Vehicle Routing Problem, MDVRP。当时团队里有同事提议多仓还不简单把单仓模型跑三遍就行——给每个客户按距离指派到最近仓库再用原来的单仓库算法分头求解。结果实测总里程比预想高出15%以上几台车在仓库交界区域反复交叉调度员看路线回放直接说这不合理。那次项目让我彻底意识到多配送中心车辆路径优化里藏着太多单仓模型根本暴露不出来的问题。这篇分享不打算绕圈子。我会以实际项目经验为主线把MDVRP从问题定义、数学建模、算法选型到代码落地完整拆一遍。无论你是做同城物流、区域配送还是厂区多个车间之间的转运调度只要手上不止一个仓库或发车点下面的方法、代码和踩坑记录应该都能直接用上。1. 多配送中心车辆路径优化从问题本质说起1.1 多仓与单仓的差异到底在哪单配送中心VRP里所有车辆从同一个仓库出发服务完客户再回到同一个仓库问题里只有“哪些客户放一条路线”和“路线顺序怎么排”这两个维度。一旦进入多仓库场景问题就多了一层更大的维度客户到底归哪个仓库管车辆从哪个仓库出发、回到哪个仓库我用一个表格把复杂度变化说清楚维度单仓VRP多仓MDVRP客户与仓库绑定无需决策天然归一个仓库需要决策且不能简单按距离就近分仓车辆归属所有车辆属于同一仓库每辆车绑定一个出发仓库路线交叉控制只优化自身路线还要避免不同仓库车辆的大范围交叉容量不足时的调度同仓协调即可可能要从邻近仓库调车跨区作业求解规模n个客户的排列组合仓库分派与客户排列耦合在一起组合爆炸传统VRP在处理100个客户时本质是对100个节点做排列与切割而MDVRP在有2个仓库、100个客户时理论上有2的100次方级别的客户-仓库分派组合再叠加上每个分仓内部的路径规划。用大白话说单仓问题是在一张地图上画圈多仓问题是在多张地图之间同时画圈还要保证圈之间不打架。我实际遇到的情况是客户点分布天然有聚簇性如果纯粹按最近距离把客户分给某个仓库每个仓的客户列表确实能快速分开。问题出在车辆容量约束上——某个区域客户特别密集最近仓库的车辆容量不够用了从相邻仓库调车就会让车辆穿过对方区域出现“长臂路线”。局部看每段行驶都合理全局看就是绕路、空驶和拥堵叠加。这验证了一件事MDVRP的难点核心不是单个仓库内部的TSP有多难而是“分仓”和“路径”两个决策层之间存在强耦合。关于术语再说一句后面我提到的配送中心、前置仓、仓库在数学模型里都是同一个角色——车辆出发和返回的场站。不同的只是真实业务里的场地租金、库存位置和装卸能力。1.2 问题定义与成本结构正式描述一下我每次动手建模前会列出的要素仓库集合每个仓库有坐标、可用车辆数客户集合每个客户有坐标、需求量、服务时长车辆集合每辆车有容量上限、最大工作时长、固定出车成本成本矩阵任意两点之间的车程距离或行驶时间一般做时间与距离的加权。目标是找一组从各仓库出发并返回原仓库的路线集合让所有客户恰好被服务一次同时总成本最小。这里有个关键经验成本不能只写里程。我做的第一版目标函数只含总行驶距离求解器给出的路线非常“飘逸”——为了让总里程更小它会安排某辆车载货绕行大半个城市然后再空驶返回仓库。单看里程确实下来了但司机工作时间爆了油耗也没有真正省下来。后来我把三部分成本做成了加权目标固定出车成本 行驶人时成本 时间窗惩罚成本。这样一个解才“像人排出来的路线”。实际操作中我会给每个成本维度一个可调的权重系数然后拿历史人工路线做校准。比如同一批订单人工排线总里程是280公里模型跑出来280公里但配送总时长少了1.5小时这才有说服力。2. 建模与求解思路为什么不能简单加几个仓库2.1 把MDVRP写成数学规划标准的MDVRP可以建模为混合整数规划。设 x_ijk 为0-1变量表示车辆k是否从节点i行驶到节点j再设 y_ik 表示客户i是否由车辆k服务。目标函数可以写成min Σ_k Σ_(i,j) c_ij · x_ijk约束条件包含几个必选块每个客户恰好被访问一次对任意客户i所有车辆和所有进入弧的访问次数总和等于1车辆从仓库出发并返回仓库对每辆车出度弧和入度弧各恰好一条流守恒对任意中间客户节点进入弧数量等于离开弧数量容量约束同一辆车服务的客户需求总和不超过该车容量消除子环约束防止出现不经过仓库的非法小回路。这些约束看着简单真正往下推就会发现一个棘手的问题。为了消除子环要么加Miller-Tucker-Zemlin辅助变量要么加指数级数量的割平面约束。在商用求解器里跑小规模实例问题不大但到了100个客户、2个仓库这种中等规模直接解混合整数规划往往几小时内都拿不出一个可行解。我最初用开源求解器分别测试过一个30客户、2仓库的算例单纯分支定界跑了2个小时最优性gap还停在28%不动。后来换上大邻域搜索框架同一台机器上20秒就把gap压到5%以内。这个对比非常直观地说明了精确算法和启发式在MDVRP上的适用边界。2.2 为什么精确算法在多仓场景下迅速失效这里有个概念叫“维度爆炸”。MDVRP中仓库数量为m、客户数量为n时解空间会随着n的增长以指数级别扩散而m的引入又额外增加了一层“分组自由度”。精确算法诸如分支定界、分支切割、动态规划在最坏情况下都需要指数时间。当客户数超过50、仓库数大于等于2时大多数通用求解器就很难在可接受时间内证明最优解。这个背景下真正能在实际规模站住脚的方法有三条路线求解路线适用规模优点主要问题商用/开源MIP求解器客户数小于50仓库数1-2可证明最优性规模稍大就超时元启发式ALNS、GA、TS客户数上百甚至上千分钟级产出高质量可行解不保证最优需要调参经验强化学习端到端小规模泛化较好推理速度快训练成本大真实场景泛化难我在选型时遵循一个原则如果业务一天只有几趟车用求解器慢慢算完全可以如果一天几十趟甚至上百趟车就要放弃“最优”这个执念转向分钟级高质量可行解的启发式框架。有一个项目我甚至做过混合策略对规模小的区域用求解器精确求解对跨区域的大问题用大邻域搜索兜底整体效果比单一算法稳定得多。3. 算法选型与实践框架哪种方案最趁手3.1 先摸清自己的问题属于哪一档MDVRP不是一个固定难度的单一问题按约束强弱可以拆出很多变体基础MDVRP只有车辆容量约束MDVRPTW每个客户有服务时间窗车辆必须在窗口内到达MDVRPD同时取货和送货路径还要保证先取后送带新能源车型车辆还要额外考虑充电时间和续航里程。我强烈建议动手写任何求解器之前先把客户数、仓库数、约束种类、求解时效这四个维度列成一张表。否则很容易做出“理论上最优、实际没人用”的模型。之前有同事做了一个调度工具把油耗模型、司机休息时间、天气影响因子全塞进约束里结果模型规模爆炸每次求解30分钟以上调度员根本没法用。后来砍掉一半次要约束求解时间降到了40秒业务效果反而更好。这个案例我记到现在。3.2 ALNS工业界最耐打的框架自适应大邻域搜索也就是Adaptive Large Neighborhood Search是我这几年在MDVRP上最常推荐的框架。核心流程其实不复杂生成一个初始可行解常用最近邻加贪婪插入用一组destroy算子破坏当前解的一部分比如随机删除若干客户或者整条路线删除用一组repair算子把被删除的客户重新插入比如最远距离优先插入、最小边际成本插入根据每次迭代结果动态调整算子选择概率表现好的算子使用频率变高表现差的自动减少在外层叠加模拟退火或禁忌搜索作为跳出局部最优的元逻辑。我第一版ALNS只用了4个destroy算子、3个repair算子效果已经明显好于当时跑了两天也没收敛好的遗传算法。这里有个容易忽略的细节destroy操作删除的客户数量不能随意写死。按问题规模的10%到30%动态随机选择删除量比固定删除20个客户的效果好得多。自适应机制的价值在于不同解阶段适合的破坏强度在变化需要算法自己探索。想强调的是ALNS的威力不来自单个算子而来自“自适应选择”和“多样化扰动”两个机制。如果你只是把几个启发式按固定顺序轮着跑那相当于普通多起点局部搜索很快会陷入同一个局部最优。3.3 遗传算法与蜂群什么时候值得用遗传算法GA也能做MDVRP。它的优势是群体搜索天然多峰并行适合探索性强的空间缺点是收敛慢、对参数极敏感、容易早熟。我用GA做MDVRP时染色体编码要把“客户-仓库-路线”三级信息全部放进去常采用路径表示法加仓库分段标记。交叉操作选用顺序交叉或者部分映射交叉变异时做2-opt或relocate操作。但说句实话这套东西工程味道很重每次调参数都有玄学成分。种群大小、交叉概率、变异概率、锦标赛规模任何一个参数不合适结果就是早熟或收敛极慢。相比之下ALNS的“解构-重构”逻辑非常贴合业务直觉而且天然能接各种业务约束。时间窗、容量、司机分班这些限制只需要在repair插入时保证合法就行不需要专门设计花哨的遗传算子。所以我的经验法则是如果团队里没有做运筹优化的人优先学ALNS如果已经有GA基础可以把GA作为全局搜索框架里面用ALNS或局部搜索做精炼。这种混合结构比单纯GA稳很多。3.4 强化学习路线看着很美落地要谨慎近几年图神经网络加指针网络加强化学习的路径优化论文非常多动辄宣称秒杀OR工具。我实际复现过几篇经典方法训练环境搭好以后小规模泛化尚可但一迁移到真实业务数据客户数、需求分布、仓库位置都变了表现就明显掉链子。原因不难理解神经网络解路径规划本质是在学习训练数据分布下的启发式策略而真实物流场景中客户点分布、仓库数量、道路网络高度异构泛化性突破远比论文里展示的难。我的倾向很明确用强化学习做“算子选择”也就是把ALNS里的自适应选择换成学习策略这是相对靠谱的方向。让强化学习直接端到端生成路径目前更适合实验室成果。除非团队里有算法研究员搭配否则不建议作为第一种求解方案尝试。做项目讲究把不确定性降到最低成熟可用的启发式框架永远比炫酷但脆弱的神经网络更让人安心。4. 实操过程基于OR-Tools从零实现一个MDVRP求解器4.1 环境准备与问题定义我选Google OR-Tools作为落地框架理由很现实它内置了Routing Library对VRP家族支持全面而且可以处理多仓库问题。安装一行命令pip install ortoolsRouting Library自带局部搜索元启发和若干初始解策略非常适合作为业务系统的求解引擎。先定义一个虚构的小场景2个仓库、15个客户、4辆车每车容量60客户需求在10到20之间。import math from ortools.constraint_solver import routing_enums_pb2, pywrapcp # 坐标前2个是仓库后面15个是客户 locations [ (35, 40), (45, 55), # depot 0, depot 1 (18, 20), (28, 15), (30, 50), (32, 65), (40, 25), (50, 35), (52, 70), (55, 20), (58, 45), (60, 60), (62, 30), (68, 15), (70, 50), (72, 25), (74, 65), ] node_count len(locations) num_depots 2 # 前2个节点是仓库客户节点索引是2到16 demands [0, 0] [10, 20, 15, 12, 18, 16, 13, 19, 11, 14, 17, 20, 15, 10, 18] vehicle_capacity 60 num_vehicles 4这里我先用欧氏距离模拟车程真实项目里你只需要把坐标换成路网OD矩阵就行模型结构完全不变。4.2 距离矩阵与约束绑定这一步有个关键坑OR-Tools中每个车辆都有独立的start和end索引。多仓库场景下你让第1辆车从仓库0出发第2辆从仓库1出发对应设置starts和ends即可。如果全部车辆都从仓库0出发OR-Tools根本不会知道仓库1的存在问题退化成单仓模型。def distance(a, b): dx a[0] - b[0] dy a[1] - b[1] return int(math.hypot(dx, dy) * 1000) # 放大成整数OR-Tools要求整数成本 matrix [[distance(locations[i], locations[j]) for j in range(node_count)] for i in range(node_count)] data { distance_matrix: matrix, demands: demands, vehicle_capacities: [vehicle_capacity] * num_vehicles, num_vehicles: num_vehicles, starts: [0, 1, 0, 1], # 车1和车3从仓库0出发车2和车4从仓库1出发 ends: [0, 1, 0, 1], # 回到对应仓库 } manager pywrapcp.RoutingIndexManager( len(data[distance_matrix]), data[num_vehicles], data[starts], data[ends] ) routing pywrapcp.RoutingModel(manager) def distance_callback(from_index, to_index): from_node manager.IndexToNode(from_index) to_node manager.IndexToNode(to_index) return data[distance_matrix][from_node][to_node] transit_callback_index routing.RegisterTransitCallback(distance_callback) routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) def demand_callback(from_index): node manager.IndexToNode(from_index) return data[demands][node] demand_callback_index routing.RegisterUnaryTransitCallback(demand_callback) routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, # slack为0 data[vehicle_capacities], True, # 起始累计值设为0 Capacity )距离矩阵我特意做了整数化处理。直接使用浮点距离在密集客户点场景下会让很多等价路线被错误区分所以放大1000倍再取整输出结果时再除以1000即可。4.3 搜索策略与求解搜索策略配置上我测试过多种组合在MDVRP上比较稳的是先用PATH_CHEAPEST_ARC拿初始解再开启引导式局部搜索做优化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(20) solution routing.SolveWithParameters(search_parameters)如果求解时间非常紧可以把first_solution_strategy换回AUTOMATIC让库自己选。但实测在MDVRP场景下PATH_CHEAPEST_ARC往往能给出更均匀的初始路线。解的输出部分如下if solution: total_distance 0 for vehicle_id in range(data[num_vehicles]): index routing.Start(vehicle_id) route_nodes [] route_distance 0 while not routing.IsEnd(index): route_nodes.append(manager.IndexToNode(index)) previous_index index index solution.Value(routing.NextVar(index)) route_distance routing.GetArcCostForVehicle(previous_index, index, vehicle_id) route_nodes.append(manager.IndexToNode(index)) total_distance route_distance * 1.0 / 1000 print(f车辆{vehicle_id} (仓库{data[starts][vehicle_id]}): {route_nodes} 距离{route_distance / 1000:.2f}) print(f总距离: {total_distance:.2f})运行一次可能看到类似这样的结果车辆0 (仓库0): [0, 2, 4, 7, 11, 14, 0] 距离23.80 车辆1 (仓库1): [1, 3, 5, 8, 10, 13, 16, 1] 距离26.10 车辆2 (仓库0): [0, 6, 9, 12, 15, 0] 距离18.10 车辆3 (仓库1): [1, 1] 距离0.00 总距离: 68.00第四辆车没有启用这是诱导式局部搜索在优化目标下自然选择的结果。如果业务要求必须固定使用4辆车可以在约束中加入最小车辆数限制或者调高固定出车成本。4.4 参数调优的实测心得OR-Tools在MDVRP上表现不错但要拿到“能看的解”几个参数值得手动调。time_limit设置在20秒到60秒之间是个甜区。太短局部搜索来不及起效太长调度员等不起单次求解收益也不显著。guided local search的核心机制是给频繁使用的边加惩罚帮助跳出局部最优。如果发现解总是集中在同一片区可以适当调整惩罚重置频率让探索更充分。车辆数量不是越多越好。OR-Tools默认以总弧成本为目标不会自动考虑“用了多少辆车”。真要在业务里比较车队数量差异需要把每多一辆车的固定发车成本折算进弧成本。我的做法是把固定出车成本按350元折算成一个等价距离系数加到每条从仓库出发的弧上。这样搜索时算法会天然倾向于用更少的车。这个技巧在几个项目里都帮公司省下了实际底盘成本而不只是纸上谈兵地减少里程。5. 真实业务中的常见问题与排查技巧5.1 一张排查速查表现象可能原因排查方向与对策所有客户都被某一个仓库的车包了车辆starts和ends配置没有按仓库分车检查每辆车的start和end索引是否分别指向不同仓库路线来回交叉、绕路严重成本矩阵用的是直线距离没做路网映射改用真实路网距离矩阵至少对OD做一次道路距离预计算总距离很小但司机总时长很大目标函数只含行驶距离缺少服务时间和等待时间加入时间维度约束把服务时长加进累计求解时间从几秒变成几十分钟约束过多导致搜索空间爆炸先砍掉次要约束跑通主流程再逐渐加回验证影响算法结果比人工排线还差初始终解质量差或元启发没有真正开启确认first_solution_strategy不是野蛮策略开启GLS或模拟退火换了业务区域后解质量大幅下降数据分布差异大参数不适应对局部搜索参数做自适应重新调参而非沿用旧参数这张表不是理论推导每一条都是我在项目里实际踩过或者看到同事踩过的坑。出现问题时不要急着怀疑算法能力先检查数据输入和参数配置九成问题都出在这儿。5.2 三个深坑的现场记录坑一距离矩阵用int会丢精度。OR-Tools只接受整数代价但如果你直接把坐标算出来的浮点距离四舍五入在客户点密集时会让很多等价路线被错误区分。我的做法是浮点距离放大1000倍再取整输出时再还原。这个精度处理在客户距离差别很小时尤其重要。坑二客户索引和仓库索引在下标边界上容易写混。MDVRP建模时仓库节点通常是0到m-1客户节点是m到mn-1。如果数据读取时弄错仓库索引轻则给出非法路线重则整个模型悄悄退化成单仓问题。最稳妥的防御方式是正式求解前先打印每个节点类型和归属肉眼确认一遍再跑。坑三把固定发车成本硬塞进容量维度。我见过有人为了减少车辆数把出车成本当作车辆容量的一个系数结果车辆为了“凑capacity”反而故意装不满逻辑完全跑偏。固定成本应该挂在弧成本或目标函数上绝对不要放在容量维度。容量约束的职责只有一个就是保证载重不超限。5.3 我踩过的一个真实大坑有一次凌晨上线新算法版本第二天一早调度员集体反馈路线“看不懂”。排查了整整一上午最后发现是取数环节把仓库字段和客户字段对调了。这个问题让我彻底养成一个习惯无论跑什么模型正式上线前一定要用一份抽样的历史订单数据做对比。把模型输出的路线数量和人工排线的路线数量、总里程并排打印出来人工看一眼再放行。这种对比检查花不了几分钟但能挡住绝大多数低级错误。算法团队容易陷入“调参越调越深”的状态忽略了数据链路本身的正确性。路线优化这种系统数据错一点后面模型再准都是白搭。整个多配送中心路径优化做下来我最大的体会是这个领域真正的难度不在算法本身而在把业务问题翻译成模型的整个过程。先想清楚你要优化什么是里程、是油耗、是准时率还是司机的总工时再大胆地砍掉那些看起来很重要、实际上不会改变决策结论的约束。模型不是为了复杂而复杂而是为了帮助调度员做出更好的决策。最后再分享一个小技巧如果业务方要求“尽快给个结果”而你手上又没有成熟求解器不要慌。先用最近邻贪心算法生成一个可行解打底再在这个解上跑20次2-opt随机重启。这往往只需要半小时的代码量却能比拍脑袋画路线强出50%以上。等业务跑顺了你再往里面加ALNS、加引导式局部搜索、加复杂约束一步一步升级比一次性上一套大而全的系统稳得多。 
长河君 · 2026/10/14 6:35:45 · 阅读 1.2k MDVRP多配送中心车辆路径优化实战：建模、算法与OR-Tools落地
上个月给一家生鲜公司做配送系统升级3个前置仓、180个客户点、12台冷链车主题就是典型的多配送中心车辆路径优化Multi-Depot Vehicle Routing Problem, MDVRP。当时团队里有同事提议多仓还不简单把单仓模型跑三遍就行——给每个客户按距离指派到最近仓库再用原来的单仓库算法分头求解。结果实测总里程比预想高出15%以上几台车在仓库交界区域反复交叉调度员看路线回放直接说这不合理。那次项目让我彻底意识到多配送中心车辆路径优化里藏着太多单仓模型根本暴露不出来的问题。这篇分享不打算绕圈子。我会以实际项目经验为主线把MDVRP从问题定义、数学建模、算法选型到代码落地完整拆一遍。无论你是做同城物流、区域配送还是厂区多个车间之间的转运调度只要手上不止一个仓库或发车点下面的方法、代码和踩坑记录应该都能直接用上。1. 多配送中心车辆路径优化从问题本质说起1.1 多仓与单仓的差异到底在哪单配送中心VRP里所有车辆从同一个仓库出发服务完客户再回到同一个仓库问题里只有“哪些客户放一条路线”和“路线顺序怎么排”这两个维度。一旦进入多仓库场景问题就多了一层更大的维度客户到底归哪个仓库管车辆从哪个仓库出发、回到哪个仓库我用一个表格把复杂度变化说清楚维度单仓VRP多仓MDVRP客户与仓库绑定无需决策天然归一个仓库需要决策且不能简单按距离就近分仓车辆归属所有车辆属于同一仓库每辆车绑定一个出发仓库路线交叉控制只优化自身路线还要避免不同仓库车辆的大范围交叉容量不足时的调度同仓协调即可可能要从邻近仓库调车跨区作业求解规模n个客户的排列组合仓库分派与客户排列耦合在一起组合爆炸传统VRP在处理100个客户时本质是对100个节点做排列与切割而MDVRP在有2个仓库、100个客户时理论上有2的100次方级别的客户-仓库分派组合再叠加上每个分仓内部的路径规划。用大白话说单仓问题是在一张地图上画圈多仓问题是在多张地图之间同时画圈还要保证圈之间不打架。我实际遇到的情况是客户点分布天然有聚簇性如果纯粹按最近距离把客户分给某个仓库每个仓的客户列表确实能快速分开。问题出在车辆容量约束上——某个区域客户特别密集最近仓库的车辆容量不够用了从相邻仓库调车就会让车辆穿过对方区域出现“长臂路线”。局部看每段行驶都合理全局看就是绕路、空驶和拥堵叠加。这验证了一件事MDVRP的难点核心不是单个仓库内部的TSP有多难而是“分仓”和“路径”两个决策层之间存在强耦合。关于术语再说一句后面我提到的配送中心、前置仓、仓库在数学模型里都是同一个角色——车辆出发和返回的场站。不同的只是真实业务里的场地租金、库存位置和装卸能力。1.2 问题定义与成本结构正式描述一下我每次动手建模前会列出的要素仓库集合每个仓库有坐标、可用车辆数客户集合每个客户有坐标、需求量、服务时长车辆集合每辆车有容量上限、最大工作时长、固定出车成本成本矩阵任意两点之间的车程距离或行驶时间一般做时间与距离的加权。目标是找一组从各仓库出发并返回原仓库的路线集合让所有客户恰好被服务一次同时总成本最小。这里有个关键经验成本不能只写里程。我做的第一版目标函数只含总行驶距离求解器给出的路线非常“飘逸”——为了让总里程更小它会安排某辆车载货绕行大半个城市然后再空驶返回仓库。单看里程确实下来了但司机工作时间爆了油耗也没有真正省下来。后来我把三部分成本做成了加权目标固定出车成本 行驶人时成本 时间窗惩罚成本。这样一个解才“像人排出来的路线”。实际操作中我会给每个成本维度一个可调的权重系数然后拿历史人工路线做校准。比如同一批订单人工排线总里程是280公里模型跑出来280公里但配送总时长少了1.5小时这才有说服力。2. 建模与求解思路为什么不能简单加几个仓库2.1 把MDVRP写成数学规划标准的MDVRP可以建模为混合整数规划。设 x_ijk 为0-1变量表示车辆k是否从节点i行驶到节点j再设 y_ik 表示客户i是否由车辆k服务。目标函数可以写成min Σ_k Σ_(i,j) c_ij · x_ijk约束条件包含几个必选块每个客户恰好被访问一次对任意客户i所有车辆和所有进入弧的访问次数总和等于1车辆从仓库出发并返回仓库对每辆车出度弧和入度弧各恰好一条流守恒对任意中间客户节点进入弧数量等于离开弧数量容量约束同一辆车服务的客户需求总和不超过该车容量消除子环约束防止出现不经过仓库的非法小回路。这些约束看着简单真正往下推就会发现一个棘手的问题。为了消除子环要么加Miller-Tucker-Zemlin辅助变量要么加指数级数量的割平面约束。在商用求解器里跑小规模实例问题不大但到了100个客户、2个仓库这种中等规模直接解混合整数规划往往几小时内都拿不出一个可行解。我最初用开源求解器分别测试过一个30客户、2仓库的算例单纯分支定界跑了2个小时最优性gap还停在28%不动。后来换上大邻域搜索框架同一台机器上20秒就把gap压到5%以内。这个对比非常直观地说明了精确算法和启发式在MDVRP上的适用边界。2.2 为什么精确算法在多仓场景下迅速失效这里有个概念叫“维度爆炸”。MDVRP中仓库数量为m、客户数量为n时解空间会随着n的增长以指数级别扩散而m的引入又额外增加了一层“分组自由度”。精确算法诸如分支定界、分支切割、动态规划在最坏情况下都需要指数时间。当客户数超过50、仓库数大于等于2时大多数通用求解器就很难在可接受时间内证明最优解。这个背景下真正能在实际规模站住脚的方法有三条路线求解路线适用规模优点主要问题商用/开源MIP求解器客户数小于50仓库数1-2可证明最优性规模稍大就超时元启发式ALNS、GA、TS客户数上百甚至上千分钟级产出高质量可行解不保证最优需要调参经验强化学习端到端小规模泛化较好推理速度快训练成本大真实场景泛化难我在选型时遵循一个原则如果业务一天只有几趟车用求解器慢慢算完全可以如果一天几十趟甚至上百趟车就要放弃“最优”这个执念转向分钟级高质量可行解的启发式框架。有一个项目我甚至做过混合策略对规模小的区域用求解器精确求解对跨区域的大问题用大邻域搜索兜底整体效果比单一算法稳定得多。3. 算法选型与实践框架哪种方案最趁手3.1 先摸清自己的问题属于哪一档MDVRP不是一个固定难度的单一问题按约束强弱可以拆出很多变体基础MDVRP只有车辆容量约束MDVRPTW每个客户有服务时间窗车辆必须在窗口内到达MDVRPD同时取货和送货路径还要保证先取后送带新能源车型车辆还要额外考虑充电时间和续航里程。我强烈建议动手写任何求解器之前先把客户数、仓库数、约束种类、求解时效这四个维度列成一张表。否则很容易做出“理论上最优、实际没人用”的模型。之前有同事做了一个调度工具把油耗模型、司机休息时间、天气影响因子全塞进约束里结果模型规模爆炸每次求解30分钟以上调度员根本没法用。后来砍掉一半次要约束求解时间降到了40秒业务效果反而更好。这个案例我记到现在。3.2 ALNS工业界最耐打的框架自适应大邻域搜索也就是Adaptive Large Neighborhood Search是我这几年在MDVRP上最常推荐的框架。核心流程其实不复杂生成一个初始可行解常用最近邻加贪婪插入用一组destroy算子破坏当前解的一部分比如随机删除若干客户或者整条路线删除用一组repair算子把被删除的客户重新插入比如最远距离优先插入、最小边际成本插入根据每次迭代结果动态调整算子选择概率表现好的算子使用频率变高表现差的自动减少在外层叠加模拟退火或禁忌搜索作为跳出局部最优的元逻辑。我第一版ALNS只用了4个destroy算子、3个repair算子效果已经明显好于当时跑了两天也没收敛好的遗传算法。这里有个容易忽略的细节destroy操作删除的客户数量不能随意写死。按问题规模的10%到30%动态随机选择删除量比固定删除20个客户的效果好得多。自适应机制的价值在于不同解阶段适合的破坏强度在变化需要算法自己探索。想强调的是ALNS的威力不来自单个算子而来自“自适应选择”和“多样化扰动”两个机制。如果你只是把几个启发式按固定顺序轮着跑那相当于普通多起点局部搜索很快会陷入同一个局部最优。3.3 遗传算法与蜂群什么时候值得用遗传算法GA也能做MDVRP。它的优势是群体搜索天然多峰并行适合探索性强的空间缺点是收敛慢、对参数极敏感、容易早熟。我用GA做MDVRP时染色体编码要把“客户-仓库-路线”三级信息全部放进去常采用路径表示法加仓库分段标记。交叉操作选用顺序交叉或者部分映射交叉变异时做2-opt或relocate操作。但说句实话这套东西工程味道很重每次调参数都有玄学成分。种群大小、交叉概率、变异概率、锦标赛规模任何一个参数不合适结果就是早熟或收敛极慢。相比之下ALNS的“解构-重构”逻辑非常贴合业务直觉而且天然能接各种业务约束。时间窗、容量、司机分班这些限制只需要在repair插入时保证合法就行不需要专门设计花哨的遗传算子。所以我的经验法则是如果团队里没有做运筹优化的人优先学ALNS如果已经有GA基础可以把GA作为全局搜索框架里面用ALNS或局部搜索做精炼。这种混合结构比单纯GA稳很多。3.4 强化学习路线看着很美落地要谨慎近几年图神经网络加指针网络加强化学习的路径优化论文非常多动辄宣称秒杀OR工具。我实际复现过几篇经典方法训练环境搭好以后小规模泛化尚可但一迁移到真实业务数据客户数、需求分布、仓库位置都变了表现就明显掉链子。原因不难理解神经网络解路径规划本质是在学习训练数据分布下的启发式策略而真实物流场景中客户点分布、仓库数量、道路网络高度异构泛化性突破远比论文里展示的难。我的倾向很明确用强化学习做“算子选择”也就是把ALNS里的自适应选择换成学习策略这是相对靠谱的方向。让强化学习直接端到端生成路径目前更适合实验室成果。除非团队里有算法研究员搭配否则不建议作为第一种求解方案尝试。做项目讲究把不确定性降到最低成熟可用的启发式框架永远比炫酷但脆弱的神经网络更让人安心。4. 实操过程基于OR-Tools从零实现一个MDVRP求解器4.1 环境准备与问题定义我选Google OR-Tools作为落地框架理由很现实它内置了Routing Library对VRP家族支持全面而且可以处理多仓库问题。安装一行命令pip install ortoolsRouting Library自带局部搜索元启发和若干初始解策略非常适合作为业务系统的求解引擎。先定义一个虚构的小场景2个仓库、15个客户、4辆车每车容量60客户需求在10到20之间。import math from ortools.constraint_solver import routing_enums_pb2, pywrapcp # 坐标前2个是仓库后面15个是客户 locations [ (35, 40), (45, 55), # depot 0, depot 1 (18, 20), (28, 15), (30, 50), (32, 65), (40, 25), (50, 35), (52, 70), (55, 20), (58, 45), (60, 60), (62, 30), (68, 15), (70, 50), (72, 25), (74, 65), ] node_count len(locations) num_depots 2 # 前2个节点是仓库客户节点索引是2到16 demands [0, 0] [10, 20, 15, 12, 18, 16, 13, 19, 11, 14, 17, 20, 15, 10, 18] vehicle_capacity 60 num_vehicles 4这里我先用欧氏距离模拟车程真实项目里你只需要把坐标换成路网OD矩阵就行模型结构完全不变。4.2 距离矩阵与约束绑定这一步有个关键坑OR-Tools中每个车辆都有独立的start和end索引。多仓库场景下你让第1辆车从仓库0出发第2辆从仓库1出发对应设置starts和ends即可。如果全部车辆都从仓库0出发OR-Tools根本不会知道仓库1的存在问题退化成单仓模型。def distance(a, b): dx a[0] - b[0] dy a[1] - b[1] return int(math.hypot(dx, dy) * 1000) # 放大成整数OR-Tools要求整数成本 matrix [[distance(locations[i], locations[j]) for j in range(node_count)] for i in range(node_count)] data { distance_matrix: matrix, demands: demands, vehicle_capacities: [vehicle_capacity] * num_vehicles, num_vehicles: num_vehicles, starts: [0, 1, 0, 1], # 车1和车3从仓库0出发车2和车4从仓库1出发 ends: [0, 1, 0, 1], # 回到对应仓库 } manager pywrapcp.RoutingIndexManager( len(data[distance_matrix]), data[num_vehicles], data[starts], data[ends] ) routing pywrapcp.RoutingModel(manager) def distance_callback(from_index, to_index): from_node manager.IndexToNode(from_index) to_node manager.IndexToNode(to_index) return data[distance_matrix][from_node][to_node] transit_callback_index routing.RegisterTransitCallback(distance_callback) routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) def demand_callback(from_index): node manager.IndexToNode(from_index) return data[demands][node] demand_callback_index routing.RegisterUnaryTransitCallback(demand_callback) routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, # slack为0 data[vehicle_capacities], True, # 起始累计值设为0 Capacity )距离矩阵我特意做了整数化处理。直接使用浮点距离在密集客户点场景下会让很多等价路线被错误区分所以放大1000倍再取整输出结果时再除以1000即可。4.3 搜索策略与求解搜索策略配置上我测试过多种组合在MDVRP上比较稳的是先用PATH_CHEAPEST_ARC拿初始解再开启引导式局部搜索做优化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(20) solution routing.SolveWithParameters(search_parameters)如果求解时间非常紧可以把first_solution_strategy换回AUTOMATIC让库自己选。但实测在MDVRP场景下PATH_CHEAPEST_ARC往往能给出更均匀的初始路线。解的输出部分如下if solution: total_distance 0 for vehicle_id in range(data[num_vehicles]): index routing.Start(vehicle_id) route_nodes [] route_distance 0 while not routing.IsEnd(index): route_nodes.append(manager.IndexToNode(index)) previous_index index index solution.Value(routing.NextVar(index)) route_distance routing.GetArcCostForVehicle(previous_index, index, vehicle_id) route_nodes.append(manager.IndexToNode(index)) total_distance route_distance * 1.0 / 1000 print(f车辆{vehicle_id} (仓库{data[starts][vehicle_id]}): {route_nodes} 距离{route_distance / 1000:.2f}) print(f总距离: {total_distance:.2f})运行一次可能看到类似这样的结果车辆0 (仓库0): [0, 2, 4, 7, 11, 14, 0] 距离23.80 车辆1 (仓库1): [1, 3, 5, 8, 10, 13, 16, 1] 距离26.10 车辆2 (仓库0): [0, 6, 9, 12, 15, 0] 距离18.10 车辆3 (仓库1): [1, 1] 距离0.00 总距离: 68.00第四辆车没有启用这是诱导式局部搜索在优化目标下自然选择的结果。如果业务要求必须固定使用4辆车可以在约束中加入最小车辆数限制或者调高固定出车成本。4.4 参数调优的实测心得OR-Tools在MDVRP上表现不错但要拿到“能看的解”几个参数值得手动调。time_limit设置在20秒到60秒之间是个甜区。太短局部搜索来不及起效太长调度员等不起单次求解收益也不显著。guided local search的核心机制是给频繁使用的边加惩罚帮助跳出局部最优。如果发现解总是集中在同一片区可以适当调整惩罚重置频率让探索更充分。车辆数量不是越多越好。OR-Tools默认以总弧成本为目标不会自动考虑“用了多少辆车”。真要在业务里比较车队数量差异需要把每多一辆车的固定发车成本折算进弧成本。我的做法是把固定出车成本按350元折算成一个等价距离系数加到每条从仓库出发的弧上。这样搜索时算法会天然倾向于用更少的车。这个技巧在几个项目里都帮公司省下了实际底盘成本而不只是纸上谈兵地减少里程。5. 真实业务中的常见问题与排查技巧5.1 一张排查速查表现象可能原因排查方向与对策所有客户都被某一个仓库的车包了车辆starts和ends配置没有按仓库分车检查每辆车的start和end索引是否分别指向不同仓库路线来回交叉、绕路严重成本矩阵用的是直线距离没做路网映射改用真实路网距离矩阵至少对OD做一次道路距离预计算总距离很小但司机总时长很大目标函数只含行驶距离缺少服务时间和等待时间加入时间维度约束把服务时长加进累计求解时间从几秒变成几十分钟约束过多导致搜索空间爆炸先砍掉次要约束跑通主流程再逐渐加回验证影响算法结果比人工排线还差初始终解质量差或元启发没有真正开启确认first_solution_strategy不是野蛮策略开启GLS或模拟退火换了业务区域后解质量大幅下降数据分布差异大参数不适应对局部搜索参数做自适应重新调参而非沿用旧参数这张表不是理论推导每一条都是我在项目里实际踩过或者看到同事踩过的坑。出现问题时不要急着怀疑算法能力先检查数据输入和参数配置九成问题都出在这儿。5.2 三个深坑的现场记录坑一距离矩阵用int会丢精度。OR-Tools只接受整数代价但如果你直接把坐标算出来的浮点距离四舍五入在客户点密集时会让很多等价路线被错误区分。我的做法是浮点距离放大1000倍再取整输出时再还原。这个精度处理在客户距离差别很小时尤其重要。坑二客户索引和仓库索引在下标边界上容易写混。MDVRP建模时仓库节点通常是0到m-1客户节点是m到mn-1。如果数据读取时弄错仓库索引轻则给出非法路线重则整个模型悄悄退化成单仓问题。最稳妥的防御方式是正式求解前先打印每个节点类型和归属肉眼确认一遍再跑。坑三把固定发车成本硬塞进容量维度。我见过有人为了减少车辆数把出车成本当作车辆容量的一个系数结果车辆为了“凑capacity”反而故意装不满逻辑完全跑偏。固定成本应该挂在弧成本或目标函数上绝对不要放在容量维度。容量约束的职责只有一个就是保证载重不超限。5.3 我踩过的一个真实大坑有一次凌晨上线新算法版本第二天一早调度员集体反馈路线“看不懂”。排查了整整一上午最后发现是取数环节把仓库字段和客户字段对调了。这个问题让我彻底养成一个习惯无论跑什么模型正式上线前一定要用一份抽样的历史订单数据做对比。把模型输出的路线数量和人工排线的路线数量、总里程并排打印出来人工看一眼再放行。这种对比检查花不了几分钟但能挡住绝大多数低级错误。算法团队容易陷入“调参越调越深”的状态忽略了数据链路本身的正确性。路线优化这种系统数据错一点后面模型再准都是白搭。整个多配送中心路径优化做下来我最大的体会是这个领域真正的难度不在算法本身而在把业务问题翻译成模型的整个过程。先想清楚你要优化什么是里程、是油耗、是准时率还是司机的总工时再大胆地砍掉那些看起来很重要、实际上不会改变决策结论的约束。模型不是为了复杂而复杂而是为了帮助调度员做出更好的决策。最后再分享一个小技巧如果业务方要求“尽快给个结果”而你手上又没有成熟求解器不要慌。先用最近邻贪心算法生成一个可行解打底再在这个解上跑20次2-opt随机重启。这往往只需要半小时的代码量却能比拍脑袋画路线强出50%以上。等业务跑顺了你再往里面加ALNS、加引导式局部搜索、加复杂约束一步一步升级比一次性上一套大而全的系统稳得多。