简介基于遗传算法求解带时间窗的车辆路径问题VRPTW的Matlab实现资源包面向物流调度、运筹优化方向的研究者与开发者包含完整的算法代码与测试数据。包内共17个文件其中12个m文件负责主程序、遗传算子、时间窗判断、路径长度计算等核心模块另有5个xlsx文件提供不同规模的算例数据如10节点、20节点、30节点便于验证算法效果与对比分析。资源整体仅49KB代码结构清晰函数划分明确适合作为学习遗传算法在组合优化中应用的入门参考也可在此基础上扩展改进策略。已有194人学习说明这一问题模型具有一定代表性。通过阅读源码可掌握从初始解生成、适应度评价到选择、交叉、变异等完整流程理解时间窗约束的处理思路并结合配套数据快速运行测试为实际场景下的路径规划问题提供解决框架。1. 基于遗传算法求解带时间窗的车辆路径问题VRPTW的数学模型带时间窗的车辆路径问题几乎出现在每个物流调度系统里若干车辆从配送中心出发为多个客户送货每个客户有最早开始服务时间 e_i 和最晚开始服务时间 l_i早到只能等晚到被拒绝或产生惩罚。经典模型把决策变量设为“车辆是否从节点 i 驶向节点 j”的 0/1 变量约束包括容量 Q、工作时长 H以及 e_i≤到达时刻≤l_i 的时间窗。同时决定车辆分配与访问顺序并让每条回路满足所有约束精确算法在几十个客户后就经常算不动。遗传算法在 100~200 客户规模上通常几分钟内就能给出可用近似解这是它长期作为工程原型首选的原因。下文从编码、解码、适应度这些容易写错的地方讲起并给出可复现的 MATLAB 代码框架。2. 遗传算法在带时间窗车辆路径问题上的编码、解码与适应度设计2.1 VRPTW 的 NP 复杂度与启发式选型VRPTW 是 VRP 的最常见变体属于 NP-hard 组合优化问题。当客户数量超过 50精确算法列生成、分支定价、分支切割的运行时间会随实例差异产生剧烈波动有时数小时都无法证明最优。工程上更常见的选择是启发式禁忌搜索、自适应大邻域搜索ALNS、模拟退火和遗传算法各有其适用场景。遗传算法实现门槛最低种群天然携带多个候选解适合后续接局部搜索改造成 memetic 算法MATLAB 的矩阵和元胞数组也很适配染色体排列编码。选型理由要从问题结构而不是流行度出发容量约束主要作用于整条路径的累计载重时间窗约束作用于车辆到达每个客户的先后时刻两层约束强耦合算法每次移动一个客户都要重新检查整条路径可行性。遗传算法把可行性修复全部丢给解码器交叉变异只负责在染色体层面做小改动这让它成为 VRPTW 教学与快速原型中出现频率最高的方法。要进一步提升解质量可以在每代之后对最优个体做 2-opt 或 Or-opt 局部搜索就得到常说的混合遗传算法。方法适用规模实现难度在 VRPTW 上的顾虑精确算法分支定价小规模高时间窗使定价子问题明显变难禁忌搜索 / ALNS中大规模中高需要设计移除插入算子与禁忌策略遗传算法中大规模低需要调编码、惩罚系数和变异率模拟退火中大规模低邻域设计依赖问题结构容易陷入局部最优2.2 排列编码与初始种群生成VRPTW 的常规编码是不带分隔符的客户编号排列。长度为客户数 n 的染色体 perm 表示服务顺序例如[3 1 4 2]并不直接等价于一辆车按该顺序访问而是交给解码器按容量和时间窗切成若干路段。这种编码的好处是任何排列都是合法 GA 个体交叉变异不会产生客户编号缺失或重复坏处是车辆边界由解码器决定车辆数不直接体现在染色体里。初始种群一般用两种方式混合生成一种完全随机用randperm(n)直接生成保证多样性另一种用最远插入或节约算法先生成一批较优排列再施加随机扰动。完全随机初始化时GA 开头几代车辆数往往偏多需要适应度函数把车辆数作为主目标才能让搜索进入车辆数较少的区域。如果完全不用启发式初始化种群规模一般要放大 30% 左右才能抵消初始化解质量差的影响。n model.n; % 客户数量 popSize 100; % 种群规模 pop cell(popSize, 1); for i 1:popSize pop{i} randperm(n); % 每个个体是一条客户排列 end这段代码对应最简初始化。参数说明n指客户数不含配送中心pop的每个元素是 1×n 的 double 向量在 Solomon 等标准算例里客户编号通常从 1 开始配送中心单独用 0 表示且只出现在解码后的路线里。randperm(n)保证每个客户在染色体中出现且只出现一次。如果后续要在解码时区分“配送中心出发”和“仓库编号”建议 depot 编号固定在 0并且染色体上始终不放 depot这样交叉变异算子就不需要处理 depot 重复的问题。2.3 适应度函数车辆数优先距离次之VRPTW 的常用目标是最小化使用的车辆数其次最小化总行驶距离因为固定车辆成本通常远大于燃油与通行成本。把两个目标合成一个标量适应度时M 要取一个明显大于最大可能距离的值例如 10000让进化先压缩车辆数。适应度公式为fit M * numRoutedVehicles totalDistance penalty。penalty 只在软时间窗或强制插入不可行客户时出现。硬时间窗一般不要进罚函数否则 GA 会拿不可行解填充种群更稳妥的做法是解码器只接受满足时间窗的客户无法插入的客户新开一辆车从而保证每条 route 都可行。软时间窗允许迟到penalty 用alpha_late * sum(max(0, arrival - l_i))表示alpha 可以取 0.5~2 倍平均单位距离成本具体看业务是时间优先还是路程优先。等待时间也应该被记录但通常只作为诊断指标不直接加入适应度否则会让算法过度牺牲路程去减少等待。2.4 解码器从排列到可行路径集合解码是整套算法成败的关键必须同时检查容量、时间窗、服务时长和最大工作时长。教学实现里最常见的是顺序插入式贪心从染色体头部开始把客户逐一往当前路线尾部尝试能塞下就放进去塞不下就新开一辆车。它不是全局最优的路径划分但计算量小而且把“车辆属于谁”的问题交给适应度去优化。function [routes, totalDist, penal] decodeVRPTW(perm, model) % 顺序解码将客户排列转成满足容量与时间窗的车辆路线集合 ci (i) i 1; % depot 编号 0数组下标需要 1 x model.x; y model.y; Q model.Q; H model.H; demand model.demand; twS model.e; twE model.l; svc model.s; dist (i,j) sqrt((x(ci(i))-x(ci(j)))^2 (y(ci(i))-y(ci(j)))^2); travel (i,j) max(1, dist(i,j)); % 距离当作时间可换成真实时间矩阵 remaining perm; routes {}; penal 0; while ~isempty(remaining) veh [0]; % 0 表示 depot load 0; clock 0; inserted true; while inserted inserted false; for i 1:numel(remaining) node remaining(i); arr clock travel(veh(end), node); % 容量、到达不晚于最晚服务时间、服务后能按时回场 if load demand(node) Q ... arr twE(node) ... max(arr, twS(node)) svc(node) travel(node, 0) H veh(end1) node; %#okAGROW load load demand(node); clock max(arr, twS(node)) svc(node); remaining(i) []; inserted true; break; end end end veh(end1) 0; % 返回 depot routes{end1} veh; %#okAGROW end totalDist 0; for r 1:numel(routes) rc routes{r}; for i 1:numel(rc)-1 totalDist totalDist dist(rc(i), rc(i1)); end end end这段代码的逻辑说明remaining保存还没被分配出去的客户veh(end)是当前路径最后一个节点arr clock travel(veh(end), node)计算从当前路径末端到该客户的到达时刻早于最早服务时间时用max(arr, twS(node))等待到最早服务时间。三个判断分别对应容量不超过 Q、到达时间不超过最晚开始服务时间、服务完成后还能在 H 之前回到 depot。clock max(arr, twS(node)) svc(node)表示服务结束后才继续推进时间轴。如果某个客户单独都无法满足容量或时间窗整个算例无解应在读取数据后提前检查并报错而不是让 GA 去死循环。距离计算放在解码完成后二次遍历虽然多一次遍历但实现清晰追求性能时可以在插入过程中同步累加距离。提示解码器内部出现任何 while 循环时都要先想退出条件。只要每个客户都能独立在时间窗内往返顺序插入式解码就不会出现“空车退出”的死循环。3. MATLAB 遗传算法主循环与交叉、变异算子的代码实现3.1 代码文件怎么组织一套能跑通且方便调参的 GA 通常拆成几个文件主脚本负责数据读取、参数设置、进化循环解码器单独文件便于单元测试选择、交叉、变异各一个函数文件。这样加局部搜索、改惩罚系数都不需要重写主循环。这类代码的常见组织方式如下文件职责易错点main.m读入算例初始化模型执行 GA 主循环depot 编号记忆不一致initPop.m生成初始种群可混合贪心启发式随机解比重过高收敛慢decodeVRPTW.m把排列解码为路径并计算目标时间窗和回场时间都要判断fitness.m车辆数、距离、罚函数加权车辆数权重要远大于距离tournamentSelect.m锦标赛选择精英保留后再做选择orderCrossover.m顺序交叉 OX重复基因剔除顺序错swapMutate.m交换变异变异率按个体算还是按基因算plotRoutes.m绘制车辆路径多车颜色与图例绑定表格里的易错点不是随意列的。主脚本和解码器如果对 depot 编号理解不一致最常见的现象是交叉算子把 0 号 depot 当普通客户参与交换导致某些路径出现两个 depot。初始化时如果完全随机解太多头十几代车辆数会普遍偏高适应度被车辆惩罚主导选择压力集中到少数个体上种群多样性快速下降后面的进化基本失去意义。3.2 GA 主循环骨架主循环的工作量集中在“选择、交叉、变异、评估、精英替换”五个环节。下面给出最简但完整的进化循环适应度值越小越好rng(1); % 固定随机种子便于复现 model loadInstance(C101_25.txt); % 自定义读数函数 param.popSize 100; param.maxGen 300; param.pc 0.9; param.pm 0.1; param.tournamentK 3; pop initPop(model, param.popSize); fit evaluatePop(pop, model); % cellfun((p) fitness(p, model), pop) 的一行封装 for gen 1:param.maxGen [~, bestIdx] min(fit); elite pop{bestIdx}; % 精英个体 parents tournamentSelect(pop, fit, param.tournamentK, param.popSize); offspring cell(1, param.popSize); for i 1:2:param.popSize p1 parents{i}; p2 parents{i1}; if rand param.pc o1 orderCrossoverOne(p1, p2); o2 orderCrossoverOne(p2, p1); else o1 p1; o2 p2; end if rand param.pm, o1 swapMutate(o1); end if rand param.pm, o2 swapMutate(o2); end offspring{i} o1; offspring{i1} o2; end offspring{end} elite; % 精英直接占据最后一个位置 fit evaluatePop(offspring, model); pop offspring; fprintf(gen %d best %.2f avg %.2f\n, gen, min(fit), mean(fit)); end逻辑说明tournamentSelect从父代中选出父本适应度小的个体有更大概率被选中orderCrossoverOne对同一对父本调用两次并互换参数生成两个子代。精英个体覆盖最后一个子代位置保证最优解不会在交叉变异中丢失。参数说明pc是交叉概率pm是变异概率这里按“个体”计算每条染色体有 10% 概率发生一次交换变异若按“基因位”计算变异率通常要降到1/n量级否则每个个体几乎都会被改得面目全非。种群规模应设为偶数for i 1:2:param.popSize才不会在最后越界。3.3 顺序交叉OX正确写法VRPTW 的染色体是排列两点交叉直接交换中间段会产生客户重复和缺失必须使用保序交叉。OX 的思路是子代保留一个父代中的一段基因另一个父代按相对顺序填充剩余空位从而在继承路径片段的同时保持排列合法性。function child orderCrossoverOne(p1, p2) % 生成一个子个体另一个子体对称处理 n numel(p1); a randi(n-1); b randi([a1, n]); child zeros(1, n); child(a:b) p1(a:b); % 保留 p1 片段 rest p2([b1:n, 1:b]); % p2 从 b1 绕回 rest(ismember(rest, child)) []; % 剔除已在片段中的客户 fillIdx [b1:n, 1:a]; % 空位按同样顺序回绕 child(fillIdx) rest; end这里p2([b1:n, 1:b])是 MATLAB 的索引拼接把 p2 尾部到头部连成一圈。rest(ismember(rest, child)) []删除已经在保留片段中出现过的客户注意不能用unique因为unique会排序并打乱顺序OX 要求保持 p2 的原始相对顺序。最后fillIdx也是从交叉段后回绕保证填充顺序和 p2 扫描顺序一致。子代产生的排列不一定满足时间窗这没关系解码器会在适应度计算时重新划分车辆交叉算子只需要保证客户编号不重复。提示测试 OX 时用固定 p1、p2 循环 1000 次检查每次 child 都满足numel(unique(child)) n。这一步能挡住绝大多数索引写反的问题。3.4 变异算子与精英保留三种常用变异算子中交换变异最简单把两个位置互换逆序变异更适合改变访问顺序适合时间窗约束较紧的实例移位变异把一个客户插入到另一个位置相当于小范围的邻域搜索。一般先实现交换再在调优阶段观察是否早熟如果连续 50 代最优不更新就加入逆序变异增加扰动。function p swapMutate(p) % 随机交换两个位置的客户 n numel(p); i randi(n); j randi(n); while j i, j randi(n); end p([i j]) p([j i]); end精英保留在主循环里已经体现把上一代最优个体放到新种群最后一个位置。需要注意替换后必须重新计算整个子代种群的适应度否则下一轮选择会用到旧适应度数据。如果要做更严格的精英策略可以在选择父本之前先复制精英交叉变异完全结束后再替换这样可以避免精英在锦标赛阶段被当作普通个体消耗掉。需要说明的是MATLAB 优化工具箱内置的ga并不适合直接用于排列编码默认二进制或实数编码会产生重复客户必须通过自定义CreationFcn、CrossoverFcn和MutationFcn才能等价于手写版本。网上关于“遗传算法python代码详解”的教程也大多是连续函数优化不能直接搬到 VRPTW核心区别在于染色体是排列而不是连续值向量交叉必须保序变异必须保证客户编号不重复。4. 求解带时间窗车辆路径问题的 GA 核心参数种群、代数、变异率与惩罚系数4.1 不同规模问题的参数区间GA 对参数不算特别敏感但绝不等于“随便设”。对 25 客户的小算例种群 50、迭代 150 已经足够对 100 客户标准算例种群 100~150、迭代 300 以上才能谈得上收敛。业内跑 Solomon 系列时一般按下面这个区间起手再根据收敛曲线微调参数25 客户100 客户200 客户左右调整依据种群规模 popSize50100~150200~300客户越多需要越多解覆盖解空间最大代数 maxGen150300400看最优适应度最后 20 代是否变化交叉率 pc0.90.85~0.950.85~0.95太低搜索退化为随机游走变异率 pm0.10.1~0.150.08~0.12越高越接近随机搜索锦标赛 k233~4k 越大选择压越大越容易早熟车辆权重 M1e41e41e4必须大于最大可能总距离表格里最容易被忽略的是车辆权重 M。如果总距离量纲是几百到几千M 取 1e4 可以保证“少一辆车”永远优先于“少跑一段路”。但如果 200 客户实例总距离能达到两万M 还是 1e4 就会让距离反客为主GA 可能保留 12 辆车却每条路径都很短。更可靠的做法是先跑一次完全随机种群的解码统计总距离上界再令 M 等于上界的 10 倍。4.2 交叉率与变异率的互相牵制交叉率提高会加速信息混合但过高会让种群在 20 代内迅速趋同变异率提高能补充多样性但过高会让优秀片段频繁被打散。两者不是独立参数变异率超过 0.2 时交叉率应降到 0.8 以下。我一般习惯先固定交叉率 0.9 观察收敛曲线如果最优解长时间不更新先不要急着加变异而是检查选择压力和种群多样性如果最优更新频繁但解质量差则优先降变异率把探索重点放在交叉上。判断依据是每次迭代的种群平均适应度。平均适应度快速向最优值靠拢时说明交叉在起作用平均适应度下降速度和最优值几乎一样慢时说明变异或初始种群多样性出了问题。fprintf里同时打印min(fit)和mean(fit)就是为了一眼看清这两个信号的差别。4.3 软时间窗与硬时间窗的惩罚系数硬时间窗实例没有讨价还价空间解码器在插入客户时直接检查arr twE(node)不满足就换下一辆车或新开车辆不产生罚函数项。软时间窗实例允许迟到但要付违约金这时解码器要返回迟到总量适应度函数里再加入alpha_late * totalLateTime。alpha 的标定要结合业务如果客户违约金按分钟计价直接把每分钟违约金作为 alpha如果没有明确费率可以用单次服务的平均货值除以平均迟到容忍时间做粗略估算。软时间窗让解码器可能选择“早到但服务慢”的路线导致路径变长却看似更优。为避免这种偏移建议把等待时间作为次级目标并在输出里单独打印一列waitingTime。解码器里clock max(arr, twS(node)) svc(node)已经隐含等待但没有把等待量返回改进办法是累加wait wait max(0, twS(node) - arr)把它乘以 0.01 左右的小权重加入适应度防止出现大量早到等待却不产生距离惩罚的路线。4.4 两阶段调参顺序一次性设置所有参数很难判断问题出在哪。推荐顺序是先固定种群规模和 M调交叉变异再调锦标赛 k最后调时间窗惩罚。第一阶段观察车辆数是否随代数单调下降如果不降说明 M 不够大或解码器产生过多车辆第二阶段观察最优距离是否下降距离不动但车辆数稳定时检查 OX 是否写对第三阶段才处理软时间窗违约金和等待时间。两阶段法在 MATLAB 里可以用一个带代数参数的适应度函数实现function fit fitnessStage(perm, model, gen, targetVeh) % 第一阶段压车辆数第二阶段放开距离优化 [routes, totalDist, penal] decodeVRPTW(perm, model); nv numel(routes); if gen 200 fit 1e8 * max(0, nv - targetVeh) totalDist penal; else fit 1e4 * nv totalDist penal; end end这里targetVeh可以用最优已知车辆数估计第一阶段把车辆数压到目标附近第二阶段换回完整目标优化总距离。penal始终保留避免算法利用不可行解规避车辆惩罚。主循环中可以用匿名函数(p) fitnessStage(p, model, gen, targetVeh)传入evaluatePop这样每一代都能按进度切换不同搜索目标本质上是一种非常简单的自适应策略。5. 用 Solomon 算例验证 VRPTW 结果与 MATLAB 代码里的 5 个坑5.1 用小算例验证解码器拿到代码后不要直接跑 100 客户算例先构造一个 5 客户、2 辆车的小例子手写一条染色体用纸笔算出预期路线和距离再对照decodeVRPTW输出。Solomon 是带时间窗车辆路径问题最常被引用的基准数据集C1、R1、RC1 三组分别代表地理聚集、随机分散和混合分布时间窗宽度也不同先用其中 25 客户版本跑通再切换 100 客户版本。验证时把随机种子固定成rng(2024)这样每次启动脚本得到相同初始种群排错时不会因为随机性干扰判断。输出格式至少要包含车辆数、总距离、总迟到时间三列把总迟到时间独立显示可以快速判断时间窗约束是否在起作用。5.2 五个高频坑与对应修法坑一depot 编号混用。有的代码用 1 表示 depot有的用 0交叉算子如果照抄其他项目会把 depot 当作客户参与交换。修法是只在解码器内部出现 depot染色体层面永远只出现客户编号交叉变异完全不用感知 depot。坑二硬时间窗写成if max(arr, e) l这会让本来超过最晚时间的客户经过等待后又变成可行。正确写法是先判断原始arr l再决定等待并推进 clock。坑三OX 交叉用unique剔除重复客户导致父代顺序被打乱。修法是rest(ismember(rest, child)) []保持剩余基因的相对顺序。坑四精英替换后忘记重新计算整个子代适应度下一轮锦标赛会把旧适应度当作新个体的值出现明显的选择偏差。坑五for i 1:2:popSize在 popSize 为奇数时最后一对p1, p2越界种群规模一律使用偶数可以避开这个低级错误。5.3 用两张图判断算法是否跑偏第一张画车辆路径第二张画时间轴甘特图。路径图能看出路线交叉是否过多甘特图横轴是时间、纵轴是车辆编号能直观看出等待和服务时间的比例。figure; hold on; colors lines(numel(routes)); for k 1:numel(routes) r routes{k}; plot(model.x(r1), model.y(r1), o-, Color, colors(k,:)); end这里的r1是因为 depot 编号为 0而 MATLAB 索引从 1 开始坐标数组第一位放 depot 坐标后续才是客户坐标。甘特图可以用rectangle(Position, [start, veh-0.4, duration, 0.8])一段段画客户服务区间车辆空闲区域一目了然。如果路径图出现大量长跨度交叉线通常是 OX 之后缺少局部搜索如果甘特图显示某辆车服务间隔中等待时间特别长则要调整解码头部的客户顺序因为顺序解码的车辆按染色体顺序填充等待时间集中在后半段往往意味着该车的路线应该交给下一辆车。本文还有配套的精品资源点击获取