兄弟们今天咱们来盘一盘Matlab里搞车辆路径规划的那些事儿。说实话配送路线优化这个领域最劝退新人的不是算法有多难而是各种约束条件跟不要钱似的往你身上叠车辆容量、时间窗、服务时长、司机最大工时、单双行限制……随便拎出来一条都能让一个看似完美的路线当场翻车。我也是被客户一句“就简单排个路线”坑过好几回之后才老老实实把经典问题一个个啃下来的。这篇就当作给萌新的科普帖先把几个绕不开的经典问题理清楚再把怎么在Matlab里建模、选算法、避免常见坑这些经验统统讲明白想入坑的兄弟可以直接拿这篇当索引看。先说点题外的。我在Matlab里折腾VRP这么久最大的感受是这个工具箱确实适合当试验场。优化类工具箱的函数封装得很完整矩阵运算又天生适合处理距离矩阵和约束条件尤其适合在投入真实系统之前快速验证想法。但Matlab也有它的脾性——你如果不理解它底层怎么处理约束、怎么编码决策变量后面很容易被各种莫名其妙的报错和“不收敛”折磨。所以这篇不会只丢一段能跑的代码我会把背后的建模思路、变量设计逻辑、算法选型依据都讲透。1. 先盘清楚路径规划家族里那几个绕不开的经典问题很多人一上来就搜“车辆路径规划代码”结果下了一堆文件发现变量命名都不一样约束条件也看不懂。我建议你先别急着跑代码先把问题分类搞清楚。VRP不是一个单一问题而是一整个问题家族。你手里的业务场景一定能在这个家族里找到对应位置。搞错了位置后面的模型和解法全都会错位。1.1 TSP所有VRP的“心法基础”旅行商问题TSP是整个路径规划家族最底层的那个。它描述的场景很朴素一位销售从仓库出发把所有客户点挨个访问一遍每个点只能去一次最后回到仓库问怎么走能让总路程最短。TSP本身没啥实用价值因为现实里几乎没有不限载、不限时间、只用一车跑完的情况。但它是理解一切复杂VRP的钥匙。你一旦理解了TSP的变量怎么定义、目标函数怎么表达、为什么局部搜索有用后面再加容量约束、时间窗约束不过是在这个骨架上添肉。这里必须提一个让我当年很震惊的事实哪怕只有20个客户点所有可能路线的数量也是天文数字。(20-1)!/2 ≈ 6×10^16你用再快的计算机枚举也得跑到地老天荒。所以TSP教会我的第一课就是别追求“绝对最优”要学会用启发式找“足够好的解”。1.2 CVRP加上容量约束世界瞬间不美好带容量约束的车辆路径问题CVRP是现实中出现频率最高的一个变种。场景一般是仓库有一批货物车辆的最大载重有限每个客户有不同大小的需求量需要若干辆车把货物送完。问你用几辆车、每辆车去哪些点、以什么顺序去才能让总行驶距离最短很多人觉得CVRP只是TSP多套一层循环实际上难度完全不一样。TSP只需要解决“顺序问题”CVRP还要解决“分组问题”——哪个客户分给哪辆车。顺序问题加分组问题叠加在一起搜索空间的复杂度直接起飞。这也是为什么纯精确算法在CVRP上跑不了几个点因为解空间不是线性增长而是组合爆炸。举个简单例子仓库总需求是1200件货每车容量400件那就至少需要3辆车。但具体怎么把客户分成3组才让每组内部的路线都不交叉、总路程最短这就是个很难的优化问题。新手最爱犯的错就是所有客户直接按地理位置就近分堆分完再解TSP。这个“两阶段法”在很多场景下效果不差但一旦客户点分布不均匀它就会离最优解越来越远。1.3 VRPTW时间窗一出成堆的约束就开始叠罗汉带时间窗的车辆路径问题VRPTW是在CVRP基础上再加一层“要命”的约束每个客户都有自己接受服务的时间区间比如“早上8点到10点之间必须送到”。车辆早到了就只能等晚到了就违约通常还要承担惩罚成本。VRPTW最让人头大的地方在于时间约束会反过来重构路线结构。一个从空间上看非常顺路、总路程很短的路线很可能因为客户A要求上午送到、客户B要求下午送到而变得完全不可行。路程最优和时间窗最优往往是冲突的解法就是在成本和违约之间找一个平衡点。我自己的观感是VRPTW是“约束状态”的一个典型代表突出在它会让一个单纯的“空间排序问题”变成“时空联合排序问题”。你在Matlab里建模时时间约束的表述比容量约束麻烦得多因为它需要引入车辆到达时刻、服务时长、等待时间等多个辅助变量。稍不注意约束就会非线性求解器直接罢工。1.4 其他变种MDVRP、VRPPD、OVRP当心看花了眼除了上面三个还有一堆更复杂的变种。我列个表方便兄弟们按图索骥问题简称全称在经典模型基础上增加了什么典型业务场景TSP旅行商问题无容量限制一条回路单车辆、小样本、路线规划启蒙CVRP带容量约束的车辆路径问题车辆容量限制、多辆车仓配、日化品配送、货运VRPTW带时间窗的车辆路径问题客户服务时间区间生鲜配送、快递上门、售后安装MDVRP多仓库车辆路径问题多个起点仓库连锁门店补货、多中心配送VRPPD取送一体化车辆路径问题既有取货又有送货且常要求配对快递揽派一体、退换货物流OVRP开放型车辆路径问题车辆送完无需返回原仓库第三方物流外包车、租车配送一般情况下我建议新手的学习路径是 TSP → CVRP → VRPTW。先把这三个吃透再去碰变种。因为每个变种都是在某个经典数学结构上加约束或者改目标核心逻辑没有变。2. 从“人话”到“MATLAB能算的话”约束条件的数学建模很多同学卡在“我知道约束是什么可我不知道怎么写进Matlab”。这中间缺的其实是数学建模这一步。你不把现实业务翻译成变量、目标、约束这三件套代码写得再花哨也是空中楼阁。2.1 决策变量用二进制矩阵表达“谁到谁”在Matlab里做路径规划最常用的决策变量是[ X_{ijk} \begin{cases} 1 \text{第k辆车从点i直接开往点j} \ 0 \text{其他情况} \end{cases} ]其中点0一般表示仓库客户点编号从1到n。为什么要加车辆下标k因为CVRP和VRPTW下有多辆车如果只用X_ij你就无法区分某一段路是哪辆车跑的容量约束和时间窗约束也就没法表达。在Matlab代码里我会用三维矩阵或者元胞数组来装X。三维矩阵的好处是很多内置优化函数能直接接受线性不等式组的矩阵形式坏处是当客户点较多时三维矩阵会占大量内存。比如50个客户、8辆车X的维度是51×51×8约两万个变量intlinprog能处理但已接近“慢速区”了。2.2 目标函数与约束每一个都要能对应到现实目标函数很简单就是让所有车辆的总行驶成本最小[ \min \sum_{i0}^{n} \sum_{j0}^{n} \sum_{k1}^{m} d_{ij} \cdot X_{ijk} ]其中d_ij是点i到点j的距离。现实业务里还可以在d_ij上乘单位运输成本或者额外加上“每使用一辆车就算一次固定费用”。常用约束是什么印象里最常用的一共有四类每个客户只被访问一次对每个客户点j所有车辆、所有前置点i的X_ijk之和等于1。路线连续性如果第k辆车进了某个客户点那它必须再从同一个点出来。这就是流量守恒做调度的人一眼就能看懂。容量约束第k辆车服务的所有客户需求量之和不能超过该车的最大载重。时间窗约束到达客户点j的时刻要在允许的时间区间内至少不能晚于最晚时限。在Matlab里面写约束新手容易把一切约束都堆成一个巨大的不等式矩阵A*x≤b。这样写出来的代码不仅难调试而且求解速度会变慢。我现在的习惯是能用矩阵表达的就用稀疏矩阵拼表达不了的非线性约束就用惩罚函数放进目标里。怎么取舍下面讲。2.3 建模代码骨架先把数据和初始化捋顺实际动手时我会先把坐标、需求、时间窗这些数据准备好。模拟一个20个客户点的例子rng(42); % 固定随机种子保证结果可复现 n 20; % 客户数量 coords rand(n, 2) * 50; % 客户坐标单位公里 demands randi([2, 15], n, 1); % 每客户需求量单位件 capacity 60; % 每辆车最大载重 coords [0 0; coords]; % 0号点设为仓库 demands [0; demands]; % 仓库无需求接下来计算距离矩阵。大多数入门代码都用欧氏距离但如果你做的是真实城市配送最好换成真实道路距离否则解出来的路线在实际路网里根本跑不通。m size(coords, 1); D zeros(m, m); for i 1:m for j 1:m if i ~ j D(i, j) sqrt((coords(i,1)-coords(j,1))^2 ... (coords(i,2)-coords(j,2))^2); else D(i, j) inf; % 禁止i到i的“原地环路” end end end距离矩阵对角线设为inf特别重要。如果不设求解器经常会给出原地绕一圈的无效路线因为“自己到自己”的距离是0它就不想走了。2.4 车辆数量的上下界不是拍脑袋定的车辆数m是整个模型里最容易被拍脑袋决定的参数。拍错了会出两种问题m给大了车辆固定成本蹭蹭涨m给小了约束无解。我的经验是先用一个下界热热身m_lower ceil(sum(demands) / capacity);比如总需求540件车容量60那么至少需要9辆车。这个下界不是永远够用——由于客户点分散、时间窗纠缠实际可能需要11辆甚至12辆。所以在建模阶段我习惯把m设为一个略大于下界的值先跑一遍看有解无解再把m逐步往下压看总成本怎么变。这个“车辆数敏感性测试”是我自己在实际项目里摸索出来的土办法。流程很简单m从10试到14每轮跑一次优化记录总路程和是否可行。你会发现总路程通常随着m增大先下降后平稳然后在一个临界值附近大幅反弹。这个临界值往往就是最优配车数。3. 算法选择不迷路精确解、启发式与元启发式在MATLAB中的分工很多新手问我“Matlab里不是有遗传算法工具箱吗是不是直接就能解VRP”理论上是能但实际上不是一回事。你自己先要搞清楚不同算法适用什么复杂度才能对症下药。3.1 什么时候能用精确算法intlinprog与小规模硬解当客户点数量很小通常10到15个以内且约束种类相对规范时可以直接用混合整数线性规划。Matlab的intlinprog就是干这个的它接受线性目标、线性等式、线性不等式和整数变量约束VRP只要形式化得当完全可以硬解。我给它起外号叫“硬解”是因为它本质上在做分支定界和割平面。它在小规模问题上能找到全局最优解这对验证模型的正确性非常有价值。如果在跑大规模问题之前先用小规模数据验证一次你的模型表达没有逻辑错误后面就算换算法心里也有底。但精确算法对规模极为敏感。从15个点涨到20个点求解时间翻个几十倍太正常了。我建议你把intlinprog当成“标定工具”用而不是指望它解决大规模生产问题。3.2 启发式策略构造解法 局部改进启发式算法的核心思想是三步先快速构造一个可行解再不断局部改进直到改进收益变小。构造解最常见的套路有最近邻法每次从当前点去最近的未访问点和节约法把两条线路合并计算能节省的距离。这两种方法都能在极短时间内给出一个“能跑”的解哪怕不是最优也比拍脑袋强。局部改进最经典的就是2-opt把路线中的一段线路翻转过来如果新路线的总距离更短就接受这次翻转一直重复到无法改进为止。2-opt实现简单、效果直观特别擅长解开那种“交叉路径”。我刚接触VRP那阵只用最近邻加2-opt就把一个30个点的模拟配送案例从600多公里优化到了400公里上下效果立竿见影。3.3 元启发式遗传算法和模拟退火的正确打开方式规模再大、约束再杂就得请元启发式了。Matlab自带的ga遗传算法和simulannealbnd模拟退火都是比较通用的全局优化工具但它们在VRP问题上有个限制默认支持的是连续变量优化而VRP的路径是离散的排列问题。直接丢给ga它根本不知道“一条路线”长什么样。所以你要做的是自定义编码和解码。通常会把一条路线编码成整数排列比如[3 7 2 9 ...]表示车辆按这个顺序拜访客户。ga每生成一个新个体你就在适应度函数里把排列解码成实际路径算总距离加惩罚。这样绕一圈工具箱才能用。模拟退火对VRP的实现要更顺手一些。它的思路是允许偶尔接受一个差解概率随着“温度”降低而降低从而跳出局部最优。你只需要定义“怎么从当前解生成邻居解”——比如随机交换两个客户点的访问顺序或者把一路车的某个客户挪到另一路车——然后交给算法去迭代。三个算法我做用户常见误区却被反复推着走把遗传算法当成“万能药”不定义排列编码结果算出来根本不是一条合法路径或者以为默认参数可以跑结果种群规模太小人收敛到了明显的坏解。记住参数和编码往往比算法本身更决定成败。3.4 选择路线图我的个人判定标准我自己选算法时有个简单判断流程客户点 ≤ 15求解时间要求不苛刻用intlinprog找最优解。客户点 20~100约束主要是容量最近邻/节约法构造 2-opt/3-opt局部搜索。客户点 100或者时间窗复杂遗传算法 / 模拟退火并做多次随机重启。车辆数也要优化优先用带车辆惩罚项的元启发式。这个路线图在绝大多数场景下都不会太离谱。你越往后做越会发现路径规划项目里真正的瓶颈往往不是“算法不够高级”而是“模型没建清楚”和“约束处理不干净”。4. 写一个能跑起来的算法骨架最近邻导入 2-opt 优化光说不练假把式下面我直接给一套最简单的、能跑通的骨架代码。这套东西我已经在多个模拟项目里反复用过扩展性也不错值得复制下来当底盘。4.1 最近邻启发式先拿一个可行性解“垫底”最近邻法的逻辑非常直白从仓库出发找最近的未访问客户点走到那里再从那里找下一个最近的未访问点直到所有客户点都走完最后返回仓库。它的优点是快缺点是一旦前面选错一个点后面就容易走“冤枉路”。function route nearestNeighbor(D) n size(D, 1); route 1; % 从仓库1号点出发 visited false(1, n); visited(1) true; current 1; while sum(~visited) 0 unvisited find(~visited); dists D(current, unvisited); [~, idx] min(dists); current unvisited(idx); route [route, current]; visited(current) true; end route [route, 1]; % 最后回到仓库 end注意这里我默认仓库就是编号1。如果是先有客户坐标再预留仓库要小心编号偏移不然索引错一位路线数据就全乱了。4.2 2-opt 改进把交叉路线“掰”直2-opt的核心操作是把路径上i和j之间的一段反转过来。比如原路径是 A→B→C→D→E如果把B到D那段翻转就变成 A→D→C→B→E。如果翻转后总距离变短就保留这个新路径。function route twoOpt(route, D) n length(route); improved true; while improved improved false; for i 2:n-2 for j i1:n-1 % 当前边序和翻转后边序 before D(route(i-1), route(i)) D(route(j), route(j1)); after D(route(i-1), route(j)) D(route(i), route(j1)); if after before - 1e-9 route(i:j) route(j:-1:i); improved true; end end end end end我在实际使用时会再套一层外层循环或者把2-opt放进模拟退火的邻居生成器里。你需要留意路线数组的两端是仓库所以翻转时不要动route(1)和route(end)这就是循环从2到n-2的原因。4.3 计算路径长度并验证改进效果路径总长度可以用这个函数算function L pathLength(route, D) L 0; for k 1:length(route)-1 L L D(route(k), route(k1)); end end拿之前生成的那组20个客户的模拟数据跑一遍效果大概是这样最近邻初始路线长度: 286.4 2-opt优化后路线长度: 192.7从286到192这不是一个巧合。最近邻法会制造大量长距离“跳变”2-opt本质上就是把那些跳变找出来并消掉。你如果自己跑一次大概率也能见到类似幅度的改进。如果只有一辆车算法骨架到这里就算完整了。但现实中通常要面临多辆车的容量约束我会在最近邻构造时加一道“容量门”每尝试加入下一个客户点之前先判断当前车的剩余容量是否足够不够就先把这辆车锁死回仓库再开下一辆车。这一步很简单但能直接把路线规划从TSP推广到CVRP。4.4 多车辆处理容量门再加一组“回仓库”动作伪代码如下function routes capacitatedNN(D, demands, capacity) n size(D, 1) - 1; % 客户数 routeSets {}; visited false(n, 1); while any(~visited) route 1; % 从仓库出发 load 0; current 1; while true unvisited find(~visited); if isempty(unvisited), break; end distToUnvisited D(current, unvisited 1); % 客户点索引加1对齐 [~, idx] min(distToUnvisited); cand unvisited(idx); if load demands(cand) capacity route(end1) cand 1; load load demands(cand); current cand 1; visited(cand) true; else break; % 容量不够返回仓库开新车 end end route(end1) 1; % 回到仓库 routeSets{end1} route; end routes routeSets; end这段代码不是效率最高的但足够清晰。等你把这个版本调通再往里面加时间窗、加多仓库、加车辆固定成本顺序展开就行。5. 我在实际项目中被约束逼到墙角时攒下的排坑套路到了最后一部分我不想再堆理论直接说几个坑。这些坑基本都来自我自己的真实调试经历属于那种“公式没写错、算法没选错但结果就是不对劲”的情况。5.1 坑1硬约束和软约束没分开很多新手把“尽量准时”和“绝对不能超载”都当成硬约束写进模型结果模型直接无解。正确的区分是硬约束违反一次就不可行。比如车载重量超限、危险品不能混装。软约束违反了会难受但可以接受。比如迟到15分钟内、司机加班2小时以内。我会把软约束全部转成罚函数塞进目标函数里系数据实际情况调。这样求解器在“少绕路”和“少迟到”之间自动权衡不会因为一个软约束死锁。判断硬软的标准只有一个业务上能不能接受例外。5.2 坑2总把线路最优当成全局最优你在Matlab里可能把总路线距离优化得很好但现实中司机可能超时工作或者有的客户要“优先服务”全局最优在业务现场就是一张废纸。解决思路不是把约束无限堆上去而是分层建模。先做路径优化再做班次排班两层之间留一个人工干预的缓冲。我在处理这种问题时会把“硬性业务规则”放在路径层“柔性现场调整”放在调度层两层解耦出问题至少知道是哪个环节背锅。5.3 坑3单位不统一算法“自我欺骗”这是最隐蔽的Bug。距离如果用公里表示时间如果用分钟表示速度就必须用“公里/分钟”而不是“公里/小时”。我曾经在一个模拟案例里把速度单位写成了公里每小时而时间窗用的是分钟结果算出来的到达时刻全部偏了60倍但目标函数还在照常下降。我现在会在代码开头固定写一段单位声明比如unit_d km; unit_t min; speed 40; % km/h speed speed / 60; % 转为 km/min这样写很土但能救很多命。5.4 坑4调试时只看目标函数不看路径图目标函数数值下降不快时第一直觉是“算法参数不对”但很多时候是约束写错了导致路径根本不符合实际。我强烈建议你在迭代过程中用Matlab的plot把当前路径画出来一眼就能看出车辆是不是在乱飞、是不是出现了明显的交叉路径、是不是某些点被漏访问。路径可视化除了能帮助你校准模型也能在给老板汇报时甩出一张“改造前vs改造后”的对比图比解说一百句都管用。5.5 坑5随机种子不固定结果无法复现Matlab里的ga、模拟退火以及我上面手写的最近邻/2-opt如果带有随机初始化或者随机重启每次跑出的结果都可能不同。如果你不做研究记录优化结果自己都解释不清。我的习惯是在每次main运行的最前面加上rng(2024);然后所有实验都用同一个种子。等调试稳定后再改成多个种子跑多次取统计最优避免“只靠一次好运气交差”。最后再分享一个小技巧很多兄弟拿到这个问题第一反应就是把所有约束全部塞进intlinprog或者ga里然后祈祷求解器给面子。其实对于实际项目来说我更建议把复杂约束拆出来单独写一个“可行性校验函数”。也就是说让求解器先在一个简化模型里搜出一个大致可行的路线然后你在校验函数里检查这条路线是否满足时间窗、是否超容量、是否超司机工时不合格就打回或者加惩罚。这样做的调试成本会低非常多而且能让求解器集中精力去做核心的路径搜索。路径规划这行本质上就是在“成本”和“约束”之间做权衡。约束堆得越狠你越要有耐心把模型一层一层拆开。先跑通TSP再上CVRP再啃VRPTW每一步都是在给后面的复杂情况打地基。希望这篇能给刚开始接触Matlab路径规划的朋友们一点帮助少走点我当年走过的弯路。