假设你接了一个真实的配送优化需求手头几十个客户点每个点不光给坐标和货量还附带一个严格的收货时间窗早到没人接、晚到要承担违约金。这时候光会跑一个最短路径算法是远远不够的你面对的是典型的带时间窗车辆路径问题VRPTW组合优化里出了名的NP-hard难题。我刚做完的一套MATLAB方案就是用遗传算法GA做VRP路径优化把带时间窗当成默认配置来处理同时给多车型、多车场这些扩展需求留好了口子。这篇就把这套程序的建模思路、编码设计、MATLAB实现模块以及我实测踩过的坑完整复盘一遍。无论你是做物流调度、无人机或AGV路径规划还是在写相关毕业设计这套思路都能直接参考着用。1. VRP家族到底在优化什么从纯距离到时间窗的现实进化1.1 基础VRP为什么在真实配送中不够用经典的VRP车辆路径问题描述得非常简洁一个车场、若干客户点、若干辆车每辆车有容量上限目标是用最少的车辆或最短的总行驶距离完成所有客户的配送每辆车从车场出发最终还要回到车场。单独看这个定义很多人会以为这不就是多辆车的旅行商问题TSP吗但实际项目恰恰最容易栽在这个认知偏差上。当我拿第一版代码去做真实算例时立刻发现了问题真实配送里客户并不是给个坐标就完事几乎每个客户都有自己的门禁条件。最常见的就是时间窗比如客户只允许周二上午十点到十二点之间收货太早送过去仓库没人接太晚又耽误人家营业。除此之外还有服务时间、卸货时长、车辆固定成本、司机工时限制。如果把这些约束全部忽略只做纯距离最短优化得到的路线很可能在实际中根本执行不了。所以现在的VRP研究里带时间窗版本VRPTW反而是实际应用最多的变体Solomon基准算例的一大半精力都在研究如何平衡距离、车辆数和时间窗可行性。对做项目的人来说掌握如何在最短路线与现实约束之间权衡比单纯会套一个遗传算法重要得多。1.2 VRPTW的数学模型与四组核心约束先把模型摆清楚。VRPTW定义在一个有向图 G (V, E) 上V {0, 1, ..., n}其中0是车场1到n是客户。每条边(i, j)有一个旅行成本 c_ij一般是距离或行驶时间。每个客户i有一组属性需求量 q_i、服务时间 s_i、允许开始服务的时间窗口 [e_i, l_i]。车队共有K辆车每辆最大载重为Q。决策变量是 x_ijk表示车辆k是否从客户i直接驶向客户j是则取1否则为0。目标函数通常是最小化总行驶距离即所有车辆、所有路段成本之和。约束条件里四组核心约束一个都不能少每个客户的入度和出度均为1也就是每个客户恰好被服务一次且必须由同一辆车完成。车辆从车场出发后必须回到车场形成闭合路线。每辆车沿途累积需求不能超过容量Q。车辆到达客户j的时间 t_j 必须落在时间窗口[e_j, l_j]内违反即违约。时间部分的递推公式是初学者最容易写错的点。正确的逻辑不是简单写 t_j t_i s_i travel_time(i,j)因为如果车辆到得太早应该在客户处等待到窗口开启所以是 t_j max(t_i s_i travel_time(i,j), e_j)。这个早到可以等的细节直接决定了适应度函数怎么写后面我会重点展开。另外还有一个容易被忽略的点车场本身也要当作一个节点参与建模每辆车必须先访问车场、再经过若干客户、最后回到车场车场的时间窗口等同于全天开放。如果数据结构里不把车场的角色统一写代码时很容易出现车辆在车场-客户之间折返穿越的bug。1.3 时间窗的软与硬惩罚函数设计的前置判断时间窗在建模里分硬时间窗和软时间窗。硬时间窗意味着 l_i 是绝对底线晚到一点方案就作废通常需要精确算法或非常可靠的约束处理手段软时间窗则允许迟到但迟到时长会被计入目标函数的惩罚成本。遗传算法作为启发式算法处理硬约束时我试过两种方案。第一种是在解码时直接淘汰违反时间窗的个体但问题规模一旦扩大到30个客户以上不可行解比例会明显升高种群的进化效率很低经常在500代内都收敛不到像样的结果。第二种是我实际采用的方案把时间窗设计成软约束在适应度函数里加惩罚项让进化过程从先找到可行区域、再在可行区域内精细优化自然展开。实测下来即使初始种群质量很差算法也能靠一部分路径可行、一部分路径违约的中间状态逐步修正收敛速度和解质量都有明显提升。惩罚系数也别拍脑袋定。我第一版代码把早到和晚到一律按同等系数惩罚结果算法为了躲惩罚拼命绕路延长行驶时间把总距离推得很高。后来改成早到只记录等待时间不计惩罚晚到按单位时间乘以惩罚系数计入成本目标函数的引导作用才恢复正常。2. 遗传算法解VRPTW的核心决策编码、解码与适应度函数2.1 染色体编码0分割的整数排列我选的编码方案是整数编码 0分隔符这也是MATLAB实现里最直观、最容易调试的方式。染色体长度固定为 n maxK - 1n为客户数maxK为允许的最大车辆数基因由0和客户编号共同构成客户编号恰好各出现一次0负责把整条染色体切成多段每一段代表一辆车的服务顺序。举个例子假如有5个客户、2辆车染色体是 [0 2 1 5 0 3 4]解码结果就是第一辆车从车场出发依次服务客户2、1、5然后回厂第二辆车服务客户3、4回厂。如果出现连续两个0比如 [0 0 1 2 3 4]第二辆车从第二个0开始但没有实际客户相当于该车闲置解码依然合法只是目标函数里多了一辆空车的固定成本。这种编码最大的好处是操作直观交叉、变异都能直接在整数序列上进行。但它有两个必须处理的缺点第一0会重复出现交叉后0的数量可能变化导致隐式车辆数变动需要设计修复逻辑第二标准遗传算子作用在这种编码上并不天然保证每个客户只出现一次所以每次交叉变异后都要做合法性修复。这两个点我在第三章会给出具体的处理办法。2.2 解码把一串整数变成车辆的一天解码是整个程序里最核心的公共步骤因为适应度计算、局部搜索、迭代过程可视化都要反复调用它。我实现的decode函数输入是染色体、客户坐标、需求量、时间窗、服务时间、车辆容量等参数输出一个结构体包含每辆车的客户访问顺序、累积载重和到达时间序列。解码流程从前往后扫基因遇到0就表示开启新车遇到客户编号就追加到当前车的路径末尾。如果0的数量少于车辆上限剩下的车不会出现相当于闲置车如果解码时发现某段路径的总需求超过该车容量我不会马上把整条染色体判死而是先记录容量违约值交给适应度函数处理。时间计算顺序是这样的对每一段路径从车场出发开始先算边(i,j)的行驶时间用欧氏距离除以速度或者直接查实测旅行时间矩阵到达j点后记录到达时刻arrival[j]。如果arrival[j]早于e[j]车辆等待e[j] - arrival[j]时间然后再开始服务服务完成后带着新的时刻前往下一个客户。全部扫完后累计所有车辆的行驶距离、等待时间、迟到时间和总载重作为目标函数的基础量。解码这一步一定要把边界条件处理干净我最初写解码器时因为连续0没处理好导致空车段里出现车场访问车场的伪路径适应度计算直接崩掉。建议你在实现时把染色体开头结尾的0连续两个0某段只有车场没有客户三种情况分别画到测试用例里跑通了再往下走。2.3 适应度函数总距离、容量惩罚、时间惩罚如何加权适应度函数我采用最小化目标函数的形式遗传算法的选择环节基于它的倒数或排序值。我定义的目标函数如下totalCost alpha * totalDistance beta * totalLatePenalty gamma * totalOverloadPenalty vehicleFixedCost * usedVehicleNum其中alpha通常取1表示单位距离成本beta是迟到惩罚系数gamma是超载惩罚系数vehicleFixedCost是每启用一辆车的固定成本。惩罚系数要设置得足够大让违反约束的方案明显劣于可行方案但也不能大到把距离差异完全抹平。经过多组实验我发现beta取平均单次运输成本量级的3到5倍、gamma取超载量平均价值10倍以上比较合理趋势是惩罚力度足够进化过程才舍得花代数去修正违约部分。如果时间窗是硬性的可以把惩罚系数调得更大等价于拒绝违约方案如果业务上允许一定弹性可以适当调低允许算法在旺季容忍少量迟到换取明显缩短的总里程。这个取舍本质上是一个业务决策不是纯算法决策。我建模时把权重都做成了参数调用方传入一个struct对象就能灵活调整。还有一个我踩过的重要误区把早到时间也放进惩罚里。第一版适应度函数我对早到和晚到一视同仁结果出现了一个很反直觉的现象——算法为了让某个点恰好踩点到达不惜大量绕路去拖延时间总距离比不调时间窗的方案高出不少。后来我把等待时间从惩罚项中剔除只作为统计信息输出问题立刻缓解。这个改动小但效果非常明显第四节我会给出详细对比。3. MATLAB实现核心模块的拆解与代码骨架3.1 主循环与参数配置程序主循环严格遵循初始化—评估—选择—交叉—变异—局部搜索—精英保留的标准框架最大进化代数用maxGen控制每个世代记录当代最优和全局最优。为了让MATLAB跑得高效我在进入循环前就预计算好距离矩阵和客户属性主循环里只做索引运算避免每代反复算坐标距离。关键参数我统一放在配置文件里方便批量实验参数取值说明popSize100~200种群规模问题规模大时取大maxGen300~500最大进化代数pc0.85交叉概率pm0.10变异概率eliteRatio0.10精英保留比例penaltyLate4~6迟到惩罚系数penaltyOverload10超载惩罚系数这些参数不是凭空定的而是我用Solomon C101一类标准算例做了20轮实验比对后的偏好值。你可以从这一组起点出发再拿自己的数据重新调。3.2 种群初始化随机加贪心混合初始化这一步决定了种群的起点质量直接影响收敛速度。我用了20%贪心 80%随机的混合策略。随机初始化就是把客户编号随机打散后插入0贪心初始化则是从车场出发每次选当前车辆容量和时间窗允许范围内、离当前位置最近的未访问客户找不到可行客户时就开启新车直到所有客户都被纳入。为什么不全用贪心因为全贪心会让前几代所有个体长得很像种群多样性迅速丢失遗传算法很容易早熟。为什么不全用随机因为全随机的初始路线质量太差前几百代里大量时间都花在从完全混乱阶段往外爬。两者混合以后贪心个体提供了不错的基线随机个体保留了搜索空间覆盖实测收敛曲线平滑很多。3.3 交叉与变异操作交叉是产生新个体的关键环节。我在VRPTW里主要用部分匹配交叉PMX思路是选取两个父代染色体上的两个交叉点把交叉片段复制到子代对应位置再通过映射关系把非交叉段的冲突基因一一修复。由于VRPTW染色体里有多个重复的0我加了一个小改进交叉前先暂存车辆分隔标记交叉后根据0的位置恢复分隔信息。变异方面我实现了三种基础操作单点交换、插入、反转。单点交换是随机交换两个位置的基因插入是把某段路径片段插入到另一个位置反转是把路径局部倒序。每代随机选一种执行变异个体数量由变异率控制。反转操作在TSP路径优化里效果显著在VRPTW里同样能消除路线交叉。交叉变异之后必然出现染色体合法性变化我通常在评价前调一次修复函数先把重复客户基因合并再把缺失客户基因按策略补回空位最后检查0的分隔是否符合车辆上限。这段修复逻辑看似不起眼但每次跑实验都绕不开是整个工程里最容易被低估、却对稳定性影响最大的部分。3.4 2-opt与局部搜索增强光靠基础GA算子在较大规模算例上解质量仍然不理想所以我在每代结束后对最优的几个个体执行2-opt局部搜索。2-opt的原理很朴素在某段路径上选两条不相邻的边尝试把连接关系调换如果换完总距离减少且时间窗仍然可行就接受这次改进。对VRPTW我额外加了一条判定换边后重新解码整条子路径确认没有新增严重时间窗违约才接受。从实际数据来看加入2-opt后同样代数下的平均改善幅度大约在5%到12%之间尤其是客户点密集、路线容易交叉的场景效果更明显。代价是每代运行时间增加20%左右但考虑到整体运行时间本来就不长这笔投入非常划算。4. 实测中的坑与调优这些细节决定程序能不能用4.1 早到可以等背后的惩罚陷阱先说我踩得最狠的一个坑。第一版适应度函数里我把早到和晚到都计入违约惩罚结果出现前面讲到的绕路拖延现象。举例来说客户A和B的时间窗分别是[10:00,11:00]和[14:00,15:00]距离最优路线是先到A再到B但到达B的时间是12:40早到了1小时20分钟。惩罚项会让算法觉得这段等待是成本负担于是它故意选择绕远路把到达B的时间拖到接近14:00。表面上看准时了实际上路线从直线变成了大绕圈行驶里程和司机工时白白浪费。把这种现象单独拎出来看其实很荒谬实际业务里车提前到了司机在车上等一会儿并不会产生大量额外成本绕路却实实在在消耗油费、时效和车辆损耗。所以我在后续版本里对早到一律不惩罚只记录等待时长用于统计对晚到才按违约时长乘系数惩罚。改完之后同样参数下总路线成本平均降低了8%左右车辆利用率也更高了。4.2 交叉后重复基因修复带来的假收敛另一个容易翻车的点出现在染色体修复环节。如果你只是机械地把缺失客户随机补进空位会发现算法跑着跑着停滞在某个局部最优这其实是假收敛。原因是随机补位没有利用客户在父代中出现过的位置信息等于把已经积累的良好基因模式重新打乱。我改进后的逻辑是修复时优先把缺失客户填回它在父代里出现过的附近位置也就是参考两个父代的邻接关系这样交叉产生的新个体在大概率上保留了两个父代共同倾向的基因片段。改进之后程序在C101、C201这类Solomon算例上前100代收敛速度几乎翻倍而且更好的全局最优能保留更久。4.3 参数敏感性别照抄论文参数很多刚接触GA的朋友上来直接抄论文里的pop500、gen1000、pc0.9、pm0.01结果在MATLAB里跑到怀疑人生。我建议先用小算例做快速参数实验方法很简单固定同一个算例把popSize依次设成50/100/200maxGen设成100/300/500多跑几个随机种子观察最优解的均值和方差。同一个问题参数差一倍最优解质量可能相差10%到20%。尤其变异率太低容易早熟太高会破坏精英个体。以我实测的经验30到50个客户的VRPTW场景下随着问题规模变大种群和代数应同步放大交叉率保持在0.8到0.9附近比较鲁棒变异率从0.05逐步升到0.15效果更稳定。当然这些数值不是放之四海皆准但它能给你一个调试起点比自己凭空乱试高效得多。4.4 Solomon算例的快速对标结果为了确认程序不是自我感觉良好我拿标准算例做了粗略对标。Solomon的C101系列小规模实例这套程序能在几十秒内找到接近已知最优解的路线对100客户规模的C101我会记录遗传算法找到的最优值、运行代数和车辆数用来追踪改进幅度。算例客户数代数最优总距离使用车辆数备注C101-2525300约1924接近已知最优C101-5050400约3725结果合理C101-100100500约8356仍有优化空间这类对标的价值不在于刷出一个宇宙纪录而是确认代码没有逻辑错误、参数在合理区间同时知道当前实现的水平线大概在哪里。如果你要做对比实验或写论文建议把这个表格作为自己研究进展的持续记录。5. 从VRPTW到其他各类需求怎么把这个框架扩出去5.1 多车型扩展标题里提到的其他各类需求均可其实是这类程序最实用的部分。车型扩展非常自然给每辆车增加一个车型ID车型决定容量、单位距离成本和是否具备特殊功能比如冷链、危险品资质。解码时遇到0开启新的路段按顺序从车型队列中取车型容量检查就使用该车型的容量。由于每辆车的固定成本不再相同目标函数里总使用车辆数这一项可以直接改成车辆使用成本之和遗传算法会自然倾向优先派出便宜车型等于把车辆调度也一起优化了。实测中我发现引入多车型后便宜车型的使用率显著上升整体路线成本不一定会比单一车型高这是很实用的业务结果。5.2 多车场与客户分配多车场问题MDVRP比单一场站复杂一点因为每个客户不仅要知道被哪辆车服务还要知道车从哪个车场出发。一种自然的编码方式是把客户先划到某个车场分区然后在每个分区内部做原有的单场VRPTW。这样染色体可以分成两部分分区分配向量加上分区内的路线序列适应度按全部分区总成本之和计算。分区分配在做交叉时要注意保持每个客户恰好属于一个车场这会带来额外的合法性修复。如果业务分区固定不动还可以把我前面写好的单场求解器作为子程序每个分区独立调用几乎不用改遗传算法主框架只调整外层数据组织方式非常省事。5.3 真实路网、动态调整与实操小建议真实项目里影响结果最大的一项改动是把欧氏距离换成真实路网距离。很多MATLAB用户通过地图API批量拉取OD矩阵存成 n x n 矩阵后程序内部完全不用改只需要把距离计算从几何公式换成查表。这是我做过一次之后认为ROI最高的一处升级。另外一个实操建议如果要在MATLAB里跑较大规模的VRPTW建议用profiler分析一下热点。我遇到的速度瓶颈常常不在遗传算子本身而在于解码时反复计算坐标距离改成预计算矩阵查表后整体速度提升非常明显。最后我也不建议把这套代码过度封装成黑盒。遗传算法的价值在于参数可调、日志可看、解可解释。遇到复杂业务场景时多打印几轮迭代日志、多画几幅路线图很快就能定位问题是出在编码、解码还是目标权重上。这也是很多朋友让我远程帮调时我给出的最重要的建议先自己把可视化和日志做起来剩下的调参工作其实没那么玄。