这几年做配送相关系统和路径规划打交道的次数不算少。要说最容易被低估的约束条件我一定提名容量约束。很多朋友一开始上手 VRPVehicle Routing Problem车辆路径问题时学的都是不带约束的 TSP觉得路径规划嘛就是找一条最短路线把所有点串起来。可真到了业务里车装不下路线再短也白搭。这篇我就把带容量约束的 VRP也就是大家常说的 CVRPCapacitated VRP从头到尾拆一遍容量约束为什么会让问题难度陡增、怎么建模、主流求解路线有哪些、一个能跑通的最小 Python 实现长什么样以及真正落地到配送线路时还会遇到哪些坑。这篇内容适合正在做物流调度、AGV 搬运、无人机航线规划的工程师也适合写运筹优化作业或论文的同学。读完你至少能搞定三件事第一用数学语言说清楚一个带载重限制的路径规划问题第二手写一个能出不错结果的节约算法第三知道真实业务里容量约束的常见变形和陷阱不至于拿个毕业设计级别的 Demo 就去怼生产环境。1. 为什么装得下会让路径规划难度陡增1.1 从跑一圈变成跑几圈CVRP 和 TSP 的本质差异普通的 TSP 只有一个旅行商一个人把所有客户点走完目标是总路径最短。这个模型很优雅但它默认了一个前提这个旅行商能无限装载或者说他访问每一个点都不需要带任何货物。现实世界里没有这样的车。加入容量约束之后问题结构发生了根本性变化一辆车装不下所有客户的需求就必须把客户拆成多个小组每一组由一辆车服务每组车辆从仓库出发、服务完组内客户再回到仓库。于是原来的一条回路变成了多条回路。举一个最简单的例子三个客户分别需要 60、60、60 单位的货车辆载重上限是 100。TSP 模型会给你一条 0-1-2-3-0 的回路很美但实际这条路线上车辆总载重是 180早就超了。容量约束逼着系统把这三个客户拆成两条路线比如 0-1-2-0 和 0-3-0或者 0-1-3-0 和 0-2-0。到底怎么拆会让总行驶距离最短这就是 CVRP 要回答的核心问题。所以说容量约束并不是往 TSP 里加一个不等式那么简单它改变的是问题的解空间形态。解的粒度从一条路线变成了一组路线搜索空间大了不止一个量级。1.2 现实场景中容量约束的四种典型形态很多教程把容量约束抽象成CVRP 里每个客户有需求量车辆有最大载重写得干干净净。但真实业务的容量约束五花八门我列几个最常见的形态约束类型典型场景度量单位计算要点载重约束生鲜配送、建材运输千克、吨装货总重量不超过额定载重容积约束快递干线、家具运输立方米、方量总包裹体积不超过车厢容积托盘位约束商超百货、批发配送托盘数量按托盘占用计算注意堆叠限制包裹数量约束外卖、同城急送件数骑手箱体容量按单件占位估算这里面最容易出问题的是混合约束。比如做家具配送一张床垫占 2 个托盘位但只有 40 公斤一批五金件只有 0.5 个托盘位却有 800 公斤。如果只按重量排线车不超重但装不下只按体积排线车没装满却压爆轮胎。CVRP 的基础模型解决不了这种问题但理解基础模型仍然是处理复杂约束的第一步。1.3 容量约束是业务排线的第一道硬门槛在物流调度系统里路径规划通常分两层先决定哪些订单装同一辆车再决定这辆车按什么顺序跑。容量约束卡在第一层。排线引擎如果输出了一条超载路线落到执行端就是两种结果要么调度员人工拆单导致车辆利用率低下、总里程变高要么司机硬装出现安全隐患。我见过不少团队在系统初期只按行政区域或者快递站点分组完全不看订单重量和体积结果一辆 4.2 米厢车被塞到超载一倍到了客户现场又要退货重排。这个问题的根子不是调度员不负责而是算法一开始就没把容量约束当硬约束。所以要聊 CVRP第一件事就是把容量约束从备注信息提升到模型约束的层面。2. CVRP 的数学模型先别急着写代码2.1 问题定义与符号体系做任何优化问题第一步是定义清楚参数和变量否则写代码一定会乱。标准 CVRP 通常这样定义有一个仓库depot记为节点 0有 n 个客户节点记为 1 到 n。每个客户 i 有一个需求 q_i通常 q_0 0。车队由若干辆完全相同的车辆组成每辆车的最大载重是 Q。任意两个节点 i 和 j 之间的行驶成本一般用距离或时间记为 c_ij。决策变量通常有两组。第一组是路线变量 x_ijk取值 1 表示车辆 k 从节点 i 直接开到节点 j第二组是分配变量 y_ik取值 1 表示客户 i 由车辆 k 服务。实际工程里更多人直接用每条路线的节点序列来表示解比如 route [1, 5, 3] 就表示车辆从仓库出发依次访问 1、5、3最后回仓库。这种表达在实现启发式算法时更直观。2.2 目标函数和约束条件的完整拆解CVRP 的目标函数一般是总行驶距离最小也就是最小化所有车辆行驶路径的长度之和。用符号表达就是[ \min \sum_{k1}^{m} \sum_{i0}^{n} \sum_{j0}^{n} c_{ij} x_{ijk} ]这里 m 是可用车辆数。约束条件分四类每个客户必须被服务且只能被服务一次(\sum_k y_{ik} 1)每辆车从仓库出发最后回到仓库每个节点的流入量等于流出量容量约束一辆车服务的所有客户需求总和不超过 Q子回路消除约束不能出现不经过仓库的封闭环路前两条好理解容量约束也不难。容易漏的是第四类。举个例子如果没有子回路消除约束算法可能输出一个不经过仓库的环比如 1-2-3-1这个环里每辆车都从仓库出发但这个环里的客户没被服务而车辆从仓库出发后直接跳过了这些客户从模型角度看它不违反流量守恒单独看环内需求也没超过容量。所以要专门加约束来禁止这种非法路线。经典的子回路消除写法有两种DFJ 写法对所有客户子集 S要求离开 S 的边数至少为 1和 MTZ 写法引入节点访问顺序变量 u_i加约束 (u_i - u_j m \cdot x_{ij} \leq m - 1)。DFJ 更紧但约束数量是指数级的MTZ 约束数量是多项式级的但线性松弛更松。工程实现里如果是精确求解一般用 DFJ 配合割平面动态添加如果是启发式算法直接在构造路线时保证每条路径不形成非仓库回路就行不需要显式写这个约束。2.3 为什么说 CVRP 是 NP-hard 问题CVRP 是 TSP 的推广这一点很好证明如果把容量约束设成无限大也就是 Q 大于所有客户需求之和CVRP 就退化成了单个车辆的 TSP。因为 TSP 是经典的 NP-hard 问题所以 CVRP 一个也跑不掉困难程度只增不减。这带来一个非常实际的后果暴力枚举所有路线组合的做法只适用于 20 个节点以内的玩具规模精确算法能处理到几十个客户再往上只能靠启发式和元启发式。很多刚接触 VRP 的人会问为什么不直接枚举算一个 50 客户的 CVRPLKH 这种顶级启发式算法一秒左右能出很好的解但你想验证它是不是最优可能需要跑几小时甚至几天。业务系统要的是一分钟内给出能用且稳定的解不是陪算法熬夜。3. 求解路线选型精确解、启发式还是元启发式3.1 小规模场景的精确求解如果客户节点数在 50 以内而且路线规划不需要实时响应精确算法是值得考虑的。常见方案有分支定界、分支切割、列生成工程上可以直接用 Google OR-Tools 的 CP-SAT 求解器或者 Gurobi、COPT 这类商业求解器配合 2.2 里的数学模型。精确求解的价值是能给出最优解或最优性间隙optimality gap。如果你的业务场景是日度静态排线比如第三方物流仓每天凌晨根据当天订单统一规划几十辆车的路线那完全可以用 OR-Tools 建个 CVRP 模型设一个几分钟的求解时间上限。最优解通常能在几分钟内找到找不到也能给出一个质量不错的可行解。但精确求解有个缺点模型参数一变比如增加时间窗、多车型、装卸时长数学建模难度会明显上升求解时间也可能剧烈波动。所以我的建议是先判断业务规模再决定是否走精确路线。3.2 中等规模的首选启发式与元启发式当客户规模超过 100或者你需要秒级响应的动态调度就必须上启发式算法了。这个领域有几个经典算法值得掌握节约算法Clarke-Wright Savings Algorithm是 CVRP 启发式算法里最基础的一类。它的核心思想是两条路线如果能合并省下的距离就是节约值 (s_{ij} c_{0i} c_{0j} - c_{ij})。把所有客户对按节约值从大到小排序依次判断能不能合并能合并且不超载就合并。速度快、逻辑简单、容易实现适合作为初始解生成器或者教学示例。序列插入法Insertion Heuristic的思路是逐步构建路线每次选择插入成本最小的客户放入已有路线。插入时同样要检查容量约束。ALNSAdaptive Large Neighborhood Search自适应大邻域搜索是目前求解 CVRP 以及各种扩展问题的主流元启发式。它通过破坏算子比如随机移除若干个客户、移除距离最远的客户和修复算子比如贪婪插入、后悔插入反复迭代配合模拟退火式的接受准则来跳出局部最优。工程上 ALNS 的算子设计决定了求解质量属于上限很高、下限也不低的选择。3.3 怎么选一张决策表不同算法在业务里怎么挑我按自己的实践经验整理了一个选择参考表解法适用规模求解质量单次耗时工程难度适合场景精确求解器≤ 50 客户最优或接近最优秒级到分钟级中日度静态全局排线节约算法≤ 200 客户中等通常有提升空间毫秒级低快速生成初始解局部搜索2-opt 等≤ 500 客户中上毫秒到秒级低对已有解做后处理元启发式ALNS/GA/TS100~2000高秒级到分钟级高中大规模静态/动态调度我在实际项目里最常看到的组合是先跑节约算法生成初始解再用 2-opt 或 Or-opt 做局部改进最后把结果喂给 ALNS 做一轮大规模优化。这样既保证了解的质量下限又能灵活调整求解时间。4. 一个能跑通的最小 CVRP 实战节约算法 Python 实现4.1 数据准备仓库、客户、需求、容量为了演示我构造了 1 个仓库、8 个客户的小例子。仓库坐标是 (50, 50)车辆载重上限是 100每个客户的需求量各不相同coords [ (50, 50), # 仓库 (82, 76), # 客户1 (96, 44), # 客户2 (50, 5), # 客户3 (49, 8), # 客户4 (13, 7), # 客户5 (29, 89), # 客户6 (58, 30), # 客户7 (84, 60), # 客户8 ] demand [0, 20, 25, 30, 15, 20, 22, 18, 26] capacity 100总共 8 个客户的需求量之和是 176容量上限 100所以无论如何都会被拆成至少两条路线。这个规模够小适合展示算法的每一步逻辑又不至于让读者被输出结果淹没。4.2 距离矩阵与节约值计算节约算法的第一步是计算任意两个节点之间的距离。示例里我用的是欧氏距离业务里这里通常会替换成路网距离或者实际行驶时间后文会讲原因。import math def calc_dist_matrix(coords): n len(coords) dist [[0.0] * n for _ in range(n)] for i in range(n): for j in range(n): dist[i][j] math.hypot(coords[i][0] - coords[j][0], coords[i][1] - coords[j][1]) return dist然后计算每个客户对 (i, j) 的节约值。节约值的直观含义是如果 i 和 j 分别由两辆车单独服务总距离是 (2 \times c_{0i} 2 \times c_{0j})如果把 i 和 j 放到同一辆车上最理想的情况下总距离是 (c_{0i} c_{ij} c_{0j})。两者一减就得到合并能省下的距离。4.3 合并过程端点检查与容量检查缺一不可核心循环是按节约值从大到小扫描尝试合并路线。这里有两个关键条件待合并的两个点必须分别是各自路线的端点否则会把客户从路线中间拆开重新拼接产生乱序路线。合并后整条路线的总需求不能超过车辆容量如果超了再省距离也不能合并。完整代码如下def cvrp_savings(coords, demand, capacity): dist calc_dist_matrix(coords) n len(coords) # 初始每个客户单独一条路线 routes [[i] for i in range(1, n)] # 计算所有客户对的节约值 savings [] for i in range(1, n): for j in range(i 1, n): s dist[0][i] dist[0][j] - dist[i][j] savings.append((s, i, j)) savings.sort(keylambda x: -x[0]) for s, i, j in savings: ri rj None for idx, route in enumerate(routes): if i in route: ri idx if j in route: rj idx if ri is None or rj is None or ri rj: continue # 端点检查 if i not in (routes[ri][0], routes[ri][-1]): continue if j not in (routes[rj][0], routes[rj][-1]): continue # 容量检查 load_ri sum(demand[node] for node in routes[ri]) load_rj sum(demand[node] for node in routes[rj]) if load_ri load_rj capacity: continue # 合并路线四个方向都由端点位置决定 if routes[ri][-1] i and routes[rj][0] j: routes[ri] routes[ri] routes[rj] elif routes[ri][-1] i and routes[rj][-1] j: routes[ri] routes[ri] routes[rj][::-1] elif routes[ri][0] i and routes[rj][0] j: routes[ri] routes[rj] routes[ri] else: routes[ri] routes[rj][::-1] routes[ri] routes.pop(rj) return routes合并的四个方向很多人会写错。我自己的记忆方法是先固定 i 和 j 的位置然后调整另一条路线的方向保证最终路线是一条从 0 出发、连续访问、最后回 0 的序列。比如一条路线是 [3, 4]另一条是 [7]想把 4 和 7 接上就得到 [3, 4, 7]想把 3 和 7 接上就得到 [7, 3, 4]。每次合并后删除被合并掉的那条旧路线。4.4 运行结果解读用上面这份数据跑了一遍我得到的结果是两条路线Route 0: 0 - 6 - 1 - 8 - 2 - 0, load93/100 Route 1: 0 - 5 - 3 - 4 - 7 - 0, load83/100两条路线总载重分别是 93 和 83都没有超过容量上限。总距离大约 323 左右。如果不用容量约束TSP 最优解可能只需要一条路线但载重会达到 176显然不现实。这个结果已经是一个可行解但远不是最优解。节约算法是贪心思路先合并节约值最大的点对可能在局部看起来最优但全局不一定最优。比如它可能把 6 号客户和 1 号客户放在一辆车上导致 5 号这种偏远客户孤零零地和其他客户凑成一条低效路线。改进方式很简单在得到节约算法解之后对每条路线内部跑 2-opt 优化对路线之间尝试交换客户节点一般都能进一步缩短总距离。5. 从示例走向真实业务容量约束的六种扩展形态5.1 时间窗约束从 CVRP 到 VRPTW大部分配送场景是有时间窗要求的比如生鲜冷链 9 点到 11 点必须送到、门店补货要求下午高峰期前完成。加了时间窗之后容量约束仍然存在但优先级常常会被放在时间窗之后先看哪个客户的时间窗更紧再在满足时间窗的前提下尽量合并路线。VRPTW带时间窗的车辆路径问题的求解思路通常是先把客户按时间窗排序然后插入路线时同时检查两个条件——车辆到达时间不早于最早服务时间、不晚于最晚服务时间而且整条路线的载重不超容量。我踩过的坑是只检查了当前插入点的时间窗忘了后续客户因为前序客户延误而超时所以迭代检查时需要重新计算整条路线的时间可行性。5.2 多车型与异质车队真实车队的车辆往往不是一个型号有 3 吨车、5 吨车、8 吨车容积也不同。CVRP 扩展成 HFVRPHeterogeneous Fleet VRP后容量约束从一个 Q变成每辆车有自己的 Q_k。算法上的处理方法是在合并路线时路线候选池里每辆车的剩余容量是不同的贪心合并需要优先把需求大的客户分配给容量大的车型。工程上的简化做法是先把订单按重量区间粗分到车型再对各车型分别跑 CVRP。这种做法虽然不保证全局最优但是实现简单、运维成本低。等业务规模上来以后再考虑联合优化。5.3 三维装载与装卸顺序容量不只是重量总和整车运输场景里重量满足不代表装得下。快递包裹有长宽高托盘货物有堆叠限制甚至有些货物不能倒放、不能压重货。CVRP 的纯容量约束完全覆盖不了这些问题。比较务实的处理方式是把三维装载问题降维成体积 托盘位 重量三个维度分别设上限。算法检查容量时只有三个维度同时满足才算可行。如果还要考虑装卸顺序比如先卸货的客户不能压在里面那就需要在路线构建时增加额外的后进先出检查这时候普通的 CVRP 求解器就不够用了需要定制邻域算子或者引入装载仿真模块。5.4 同时取送货和回程揽收同城配送经常出现送完一单顺便取一单的情况模型变成 VRPSPDVRP with Simultaneous Pickup and Delivery。此时每个客户有两个需求量送货量 d_i 和取货量 p_i。车辆从仓库出发时载重是所有送货量之和随着路线推进逐步卸货、装货车上的净载重是动态变化的。这个场景下容量约束要检查的是整条路线任意前缀的累计载重都不能超过 Q而不是简单加总。我在实现时习惯把每个节点的出发时载重算出来从仓库开始模拟一遍任何时刻超过容量就判定不可行。5.5 动态需求与实时重规划外卖平台、即时零售的订单是随时进来的静态 CVRP 每天跑一次根本不够。动态场景下容量约束变成了当前车上已经装了哪些订单、还剩多少剩余容量每次插入新订单时都需要实时校验。常用的方案是滚动时域把已接单但未发车的订单放进待排池每 5~15 分钟重排一次未发车但已装车的订单则只能微调路线不能随意换车。容量约束在这样的系统里更像是软硬结合硬约束是车绝对不能超载软约束是尽量少变动已生成的路线以免扰动司机执行。5.6 容量约束与其他路径规划场景的互通很多人会问AGV 搬运、无人机配送、停车场泊车规划里也有路径规划它们和 CVRP 是一回事吗我的看法是CVRP 关注的是多个点之间的车辆分配与访问顺序核心是组合优化AGV 路径规划很多是单机在环境地图上的连续空间运动规划核心是避障和几何约束无人机路径规划还要叠加禁飞区、续航里程和高度限制。但它们之间有一个共通点如果 AGV 每次搬运有载重上限无人机有最大载荷那么把多任务-多机器一起调度的问题本质上就是 CVRP 的不同载体。理解了 CVRP 的容量约束建模思路换到无人机载重调度、AGV 搬运任务分配时核心逻辑是相通的。6. 我踩过的容量约束求解坑数据、检查顺序与目标选择6.1 数据校验个别需求超过单车容量算法直接卡死第一次把 CVRP 跑起来时我的算法脚本报了个莫名其妙的错误有一个客户的需求是 120而车辆容量只有 100。节约算法初始化时每个客户单独一条路线一检查负载就发现超了导致这个客户永远无法被合法合并后续逻辑全部紊乱。后来我在所有求解器前面加了一层数据清洗如果任意一个客户的需求大于最大车辆容量直接给出告警提示运营拆分订单或更换更大车型。这个问题听起来低级但在真实业务里很常见——大件家具、整批商超货都可能超过单车运力。解决方式不是让算法去尝试不可能的任务而是在数据入口就拦截。6.2 容量检查的位置合并前查还是合并后查节约算法的合并过程里容量检查必须放在合并之前。假如你先合并再检查一旦发现超载还要回滚。回滚不仅增加代码复杂度如果连续几次回滚还会让路线状态变得难以追踪。更隐蔽的一个坑是你检查的是合并后总需求不超过 Q但忘了路线内部可能存在更严格的条件。比如车辆在路径中途卸货理论上中段的载重应该比后段高这类动态载重检查不能只靠开头的总需求判断需要模拟整条路线逐点更新载重。我在 5.4 节提到的取送货场景里就因为这个吃过亏——只算了总载重没算路径前缀载重结果解出来在中间某个点超载了。6.3 距离矩阵用欧氏距离还是路网距离差别比想象中大示例代码里我用的是欧氏距离因为坐标是模拟的。但真实配送里两点的欧氏距离和实际驾驶距离常常差 30% 以上。比如客户 A 和客户 B 在地图上直线距离 1 公里中间隔了一条河实际开车要绕行 5 公里。如果算法用的是欧氏距离它会拼命把直线距离近的客户合并到同一路线结果司机的实际行驶里程并不短甚至更差。解决办法是用路网距离或实际驾驶时间作为 c_ij。接高德、百度、Google 的路线规划 API 都可以但要注意 API 有日配额限制而且频繁调用会拖慢算法速度。我的折中方案是离线批量拉取城市内 OD 矩阵存成服务端缓存或者用开源路网数据加 Dijkstra 预先计算这样可以兼顾精度和速度。6.4 目标函数只压距离容易忽视固定出车成本CVRP 教科书里目标函数是总行驶距离最小但业务里每派一辆车就有司机工资、油费、车辆折旧这些固定成本往往比多跑 10 公里路更贵。所以真实排线目标更倾向于先用最少的车把所有订单装完再在这个前提下让总距离最短。这个优先级可以通过目标函数加权体现最小化固定出车成本 × 车辆数量 可变行驶成本 × 总距离。改成这个目标之后你会发现算法可能宁可让某辆车绕一点远路也要把客户塞进去因为少一辆车节省下来的固定成本远大于额外距离成本。我在一次生鲜配送项目里把目标改为双层加权后车辆数从 18 辆降到了 15 辆总里程反而只增加了 6%算下来月度运输成本明显下降。6.5 元启发式不是跑一次就万事大吉如果你用的是 ALNS、遗传算法这类带随机性的元启发式求解结果每次可能都不一样。我见过有人跑了一版结果就直接上线隔了两天运营说路线变了其实就是随机种子导致的震荡。工程上的应对方式很固定固定随机种子用于回归测试每次求解跑多个独立批次比如 5 轮保留最优解记录每轮的最优值和耗时便于后续调参。对于日度排线系统我会在凌晨统一跑 5 到 10 轮挑最好的结果推给调度员这样既保证了稳定性又能利用夜间闲置时间提升解质量。最后再分享一个我在项目里养成的检查习惯排完线之后输出一张载重利用率表列出每条路线的装载率。如果连续几条路线装载率都低于 60%大概率是容量约束设置得太保守或者算法目标里车辆固定成本权重偏低。把装载率指标和路线图放在一起看比只看总距离更能快速发现排线系统的异常。这个习惯帮我排查过不少问题建议你也试试。