简介面向物流调度、运筹优化方向的学习者与毕业设计开发者这是一套基于MATLAB求解多车型、多车辆且带时间窗的车辆路径问题VRP源码资源。内容覆盖从初始种群构建、遗传操作到时间窗与载重约束校验的完整流程包含GA_VRPTW.m、InitPopCW.m、draw_Best.m等核心脚本以及c101、c103等标准测试算例数据。资源共29个文件其中以26个m源码和3个mat数据文件为主压缩包仅21KB轻量易用便于快速运行与二次开发。目前已有1765人学习下载。借助该资源读者可以直观理解混合整数规划与启发式算法在VRPTW中的应用掌握自定义目标函数、约束处理及结果可视化的MATLAB实现思路特别适合作为毕业设计或课程项目的基础框架也可根据实际业务场景扩展算法改进与敏感性分析。 前阵子帮一位做城配的朋友梳理配送方案他手头有三十多个门店的补货需求车队八辆车却分大、中、小三种车型而且每家的收货时间窗都不一样——有的早上七点前必须送到有的下午两点以后才接货。这类问题如果用教科书里常见的单车场、单车型VRPTW模型去套出来的方案根本落不了地要么车派得太大空驶成本吓人要么所有时间窗挤在一起司机跑不完。这就是典型的“多车辆、多车型、带时间窗”的路径优化问题在第三方物流、生鲜配送、工程机械调度里非常普遍。这篇文章把我最近用MATLAB从建模、编码到求解、调参的完整过程整理出来代码可以直接改成自己的数据跑。1. 多车型加时间窗为什么教材里的VRP模型不够用先把这个问题的边界说清楚因为很多人一开始就把模型建错了。1.1 传统单车型VRPTW到底缺了什么单车型VRPTW的假设是车队所有车辆一模一样容量相同、固定成本相同、单位行驶成本相同。这在学术论文里很常见但现实里几乎不存在。实际车队里往往是几种车型混用4米2厢货负责小批量门店9米6负责大客户偶尔还有冷链车。如果强行把不同车型抽象成一种结果就是按大车容量去算派车数小车场景空驶率高油费白白烧掉。按小车容量去算大单量客户又装不下还得拆单拆单会把时间窗全部打乱。不同车型的固定使用成本差异非常大大车出一次车的固定成本可能是小车的两倍以上。在大客户集中区域用大车划算在散点客户区域用小车型反而更优。单车型模型的解里根本没有“用哪种车跑哪条路”这个决策维度自然给不出好方案。1.2 时间窗硬约束还是软约束上来就要定清楚时间窗分为两种。硬时间窗指早到可以等待、晚到直接拒绝收货这常见于工厂JIT补货、医院耗材配送软时间窗则允许迟到但会产生惩罚成本比如生鲜配送、快递末端晚一点还能商量。同一个问题里也可能混合存在部分大客户是硬窗普通小客户是软窗。我在MATLAB里实现时默认采用硬时间窗加惩罚机制的做法先按硬时间窗约束去判断可行解所有路径都能满足时间窗才算真正可行如果遗传算法搜索过程中出现违反时间窗的个体不直接淘汰而是通过惩罚项压低其适应度让它在进化中自然被淘汰。这样比“违反即弃”更能保留搜索多样性后面章节会详细讲罚函数怎么设计。1.3 问题输入输出定义要做代码第一步就是把输入输出固化下来输入参数说明车场坐标所有车辆起点和终点客户坐标各客户的经纬度或平面坐标客户需求量每个客户点的货物量时间窗每个客户最早开始服务时间和最晚开始服务时间服务时间在客户点卸货、签收的耗时车型表每种车型的容量、固定成本、单位距离成本、可用数量输出则是每种车型的第几辆车依次访问哪些客户每段路径的行驶方向是什么总成本是多少。这样一套输出才能直接指导调度排班。2. 数学模型决策变量、目标函数与两套核心约束建模是绕不开的一步。虽然我们最终用启发式算法求解但模型写清楚目标函数和约束才不会被代码绕晕。2.1 决策变量如何定义定义两个决策变量x_ij^km第m辆车型k的车辆从客户点i行驶到j取1否则取0。z_k^m第m辆车型k的车被使用取1否则取0。y_i^km客户i由第m辆车型k的车服务取1否则取0。注意这里把“车型”和“车辆序号”都放进下标里了这样每辆车都是独立个体方便约束不同车型的数量上限。比如你有4辆小型车、3辆中型车、2辆大型车那k1时m只能取1到4k2时m取1到3k3时m取1到2。2.2 目标函数固定成本加行驶成本目标函数设计为总成本最小化min Z Σ_k Σ_m f_k · z_k^m Σ_i Σ_j Σ_k Σ_m d_ij · c_k · x_ij^km其中f_k是车型k的固定使用成本c_k是车型k的单位距离行驶成本d_ij是客户点i到j的距离。这里有个容易被忽略的细节多车型问题中大车小车的c_k不能设成一样。大车油耗高单位距离成本必须明显高于小车否则算法会倾向用大车“一车装完”既不符合实际也体现不出优化空间。2.3 约束条件流守恒、容量、时间窗第一组是流守恒约束。每个客户点只能被一辆车访问一次而且进入该点的车必须从同一点离开。用公式写就是Σ_k Σ_m Σ_j x_ij^km 1对所有客户点i成立。这个约束保证了不会出现同一个客户被拆给两辆车服务的情况也排除了路径在某客户点断开的情况。第二组是容量约束。每辆车装载的货物总量不能超过其车型容量Σ_i q_i · y_i^km ≤ Q_k对所有k、m成立。其中q_i是客户i的需求量Q_k是车型k的最大容量。第三组是时间窗约束。车辆到达客户点i的时间记为arr_i必须满足arr_i ≤ b_i如果早于a_i到达则等待到a_i再开始服务。在实际代码里时间是递推计算的。设prev是路径上的前一个客户服务完成离开prev的时间是depart_prev那么到达i的时间是arr_i depart_prev t_prev,i。如果arr_i a_i则服务开始时间start_i a_i否则start_i arr_i。服务完成时间depart_i start_i s_i。这个递推逻辑在解码时高频使用必须写在最核心的代码里。3. 染色体设计与解码逻辑多车型问题最关键的一环模型写完之后最考验功力的就是遗传算法的染色体怎么设计。多车型VRPTW的难点和单车型之间有一个本质差别单车型问题的解只需要确定“客户分组”和“组内顺序”多车型问题还多了一个维度就是“每组由哪种车型执行”。3.1 编码方案一条整数串分成两段我在代码里采用两段式编码。染色体总长度 客户数量N 最大可用车辆数V_max。前N个基因位1到N的一个随机排列表示客户的访问优先级顺序。后V_max个基因位每个基因位取值1到K表示对应编号的车辆采用哪种车型如果取0表示该辆车不出动。为什么不用二进制编码因为客户顺序是一个排列问题二进制编码做交叉变异之后极大概率产生重复客户、缺失客户需要大量修复操作。自然数排列本身就带上“顺序”语义配合部分映射交叉PMX和交换变异子代天然还是合法排列省去很多麻烦。3.2 解码算法贪心切分加可行性回退解码是把基因串翻译成具体路径方案的过程。我的做法是贪心切分加可行性回退维护一个“当前正在构造的路径”初始为空。按客户序列位从前往后扫描尝试把客户i加入当前路径。检查这辆车当前分配好的车型在加入i后容量是否超限时间窗递推是否可行。如果可行加入路径更新车辆的装载量和当前时间。如果不可行关闭当前路径开启下一辆车的路径再把客户i放进新车。如果所有车辆都用完了还有客户没被分配标记为不可行解进入罚函数处理。这个解码策略写起来简单效果也不错。但有一个点必须提醒第5步里“开启下一辆车”时下一辆车的车型是在后段基因里已经定好的。如果后段基因里该车型容量小、成本高解码结果就会很吃亏。这就导致客户序段进化得再好后段车型段不匹配整体适应度仍然上不去。这个耦合关系是遗传搜索中最难处理的地方后文有专门讨论。3.3 时间窗可行性检查的代码细节时间窗检查的递推逻辑看起来不复杂但实现时有个高频错误早到等待时间没有累加。正确写法是arrival max(prevDepart travelTime(prev, i), timeWin(i,1)); if arrival timeWin(i,2) feasible false; return; end depart arrival serviceTime(i);注意arrival取的是“前序离开时间加行驶时间”与“最早开始时间”的较大者。如果只写arrival prevDepart travelTime漏了max那么所有早到客户都会被算成违反时间窗算法几乎找不到可行解。解码的完整流程可以用这样一段伪代码概括函数 decode(individual): 客户序列 individual(1:N) 车型序列 individual(N1:end) 车辆列表 根据车型序列生成容量、固定成本、单位成本 当前车辆指针 1 for 客户 in 客户序列: while True: 尝试将客户加入当前车辆路径 if 容量可行 且 时间窗可行: 加入 break else: 当前车辆指针加1 if 超出车辆数: 返回不可行4. 求解流程与MATLAB核心代码实现编码设计完整之后剩下的就是把遗传算法的框架搭起来。注意遗传算法本身不复杂但MATLAB实现时有几个地方不优化运行起来会非常慢。下面给出我实际调试时用的代码骨架。4.1 数据结构的组织方式先把输入数据打包成一个struct后面所有函数都传这个struct比到处传一堆零散变量清晰得多function model createModel() model.depotXY [50, 50]; % 车场坐标 model.custXY [ 12, 28; 34, 65; 73, 82; 91, 41; 58, 19; 45, 74; 22, 88; 66, 32; 85, 56; 37, 11; 29, 46; 80, 63 ]; % 12个客户坐标 model.demand [18; 25; 30; 12; 22; 17; 35; 20; 28; 15; 19; 26]; model.timeWin [ 0, 120; 30, 90; 60, 180; 45, 150; 0, 100; 80, 200; 100, 240; 50, 160; 90, 210; 20, 110; 40, 140; 70, 190 ]; % 时间窗 [a_i, b_i] model.serviceTime ones(12,1) * 0.3; % 车型表: [容量, 固定成本, 单位距离成本, 可用数量] model.fleet [ 30, 80, 1.0, 4; 50, 120, 1.3, 3; 80, 200, 1.6, 2 ]; model.nCust size(model.custXY, 1); model.vehMax sum(model.fleet(:,4)); % 预计算距离矩阵区分车场(下标1)与客户(下标2~N1) allXY [model.depotXY; model.custXY]; nAll size(allXY, 1); model.dist zeros(nAll, nAll); for i 1:nAll model.dist(i,:) sqrt(sum((allXY - allXY(i,:)).^2, 2)); end end4.2 主程序框架GA主循环的框架如下其中选择用锦标赛交叉用PMX变异用交换加车型重指派精英个体直接保留到下一代rng(42); model createModel(); NP 100; % 种群规模 maxGen 200; % 迭代代数 Pc 0.85; % 交叉概率 Pm 0.15; % 变异概率 nCust model.nCust; vehMax model.vehMax; nTypes size(model.fleet, 1); % 初始化种群 pop zeros(NP, nCust vehMax); for i 1:NP pop(i, 1:nCust) randperm(nCust); % 后段随机分配车型编号0表示该车不出动 typeAssign randi([0, nTypes], 1, vehMax); % 保证至少有一辆车被指派 if all(typeAssign 0) typeAssign(randi(vehMax)) randi(nTypes); end pop(i, nCust1:end) typeAssign; end bestCost zeros(maxGen, 1); for gen 1:maxGen costs zeros(NP, 1); for i 1:NP costs(i) fitness(pop(i,:), model); end bestCost(gen) min(costs); newPop zeros(size(pop)); % 精英保留1个 [~, bestIdx] min(costs); newPop(1,:) pop(bestIdx,:); for i 2:2:NP p1 tournamentSelect(pop, costs, 3); p2 tournamentSelect(pop, costs, 3); if rand Pc [c1, c2] PMXCrossover(p1, p2, nCust); else c1 p1; c2 p2; end if rand Pm c1 mutation(c1, nCust, vehMax, nTypes); end if rand Pm c2 mutation(c2, nCust, vehMax, nTypes); end newPop(i,:) c1; newPop(i1,:) c2; end pop newPop; end4.3 适应度函数解码加罚函数适应度函数是整个算法的核心解码和惩罚都在这里完成。我实现时把不可行解的成本设为一个很大的数但又不是无限大这样算法依然能在种群中保留少量不可行个体用于维持多样性function fit fitness(ind, model) [cost, ~, feasible] decode(ind, model); if feasible fit cost; else fit cost 1e6; % 罚函数 end enddecode函数内部对每条路径计算两部分成本该车的固定成本加上路径中所有相邻点距离乘以该车型的单位距离成本。时间窗可行性的判断就是在构造路径过程中实时检查的。4.4 交叉与变异的实现要点PMX交叉只作用于前N个客户排列段。具体做法是随机选两个交叉点交换两个父代在这段区间内的基因再根据映射关系修复重复客户。这段修复逻辑比较绕但它是保证排列合法性的关键不能省略。变异操作分两段处理客户段随机选两个位置交换保持排列性质车型段则以一定概率随机重置某个车辆的车型编号。我这里特别控制车型段的变异幅度如果变异率太高会导致搜索过程反复重构路径分组收敛速度明显变慢建议变异算子只重置1到2个车位的车型不要整段打乱。5. 算例测试与关键参数调试代码写完之后重点就是验证效果。我拿上面的12客户算例跑了一遍把过程拆开看每一步发生了什么。5.1 算例设置与收敛情况算法参数种群100迭代200代交叉率0.85变异率0.15。三种车型的参数如下车型容量固定成本单位距离成本可用数量小型30801.04中型501201.33大型802001.62前50代目标值下降非常明显从最初的接近2500降到1400左右100代以后进入平缓期到最后收敛在约1280。说明遗传算法对这类规模的问题100代足够找到比较稳定的解。5.2 最终方案解读收敛后的方案用了4辆车3辆小型车、1辆中型车大型车一辆都没用。这个结果其实很符合逻辑这个算例的客户总需求只有267用一辆80容量的大车去跑固定成本200、单位成本1.6还不如用小型车多点几趟。如果某片区域客户密集且单点需求大大车才有优势。从路径结构看4条路径中没有出现路径交叉的现象因为时间窗约束本身就把访问顺序卡住了。比如客户4的时间窗是45到150客户8是50到160如果先访问客户8再访问客户4地理位置绕一圈时间也不一定够。时间窗实际上替搜索过程剪掉了大量低质量路径顺序。5.3 参数敏感性哪些参数最值得调从多组对比测试看影响最大的参数是交叉率和变异率。交叉率低于0.7时前期搜索太慢200代结束时还没收敛变异率高于0.3时后期震荡明显最优解无法稳定保持。建议先跑一组粗略的网格搜索固定其他参数每次只调一个参数记录20次独立运行的平均最优成本和标准差。另外提醒一点种群规模不要迷信越大越好。12客户的问题种群200和种群500的结果几乎一样但耗时增加了1.5倍。对100客户以上的问题可以适当增加种群但对小规模问题维持100到150就足够。6. 高频坑位记录时间窗判罚、车型耦合与收敛陷阱最后这部分是这次实战中最想说的一些经验如果新手照着教程写一遍十有八九会踩在同一批坑上。6.1 时间窗的“早到等待”必须累计开头提过一次这里再展开讲。假设路径是车场→A→BA的时间窗是[50, 100]B的时间窗是[80, 120]车场到A行驶20分钟A到B行驶30分钟。如果你判断A到达时间是20早于50那服务开始时间是50离开A是50加服务时间10等于60到B是90满足B的时间窗。但如果代码里没有max取最大值的逻辑把到达B算成20加30等于50然后误判成违反B的早到时间窗一个本来可行的路径就被标记为不可行了。这个bug会让整个算法在搜索空间里寸步难行。6.2 车型段与客户序段的耦合这是多车型问题特有的坑。我的第一版实现里车型段变异率设得比较高结果每代都把车型配置打乱前面客户序段积累的路径分组信息全部失效目标值一直在高位震荡。后来把车型段变异限制为每次只随机重置一个车位搜索性能立刻改善。另一个相关技巧是初始化种群时不要让车型段全为零。如果你的染色体长度是N加V_maxV_max是总车辆数而后段基因取0时表示该车不出动那么初始化时必须保证至少有两三辆车被分配了实际车型。否则前几十代全在搜索“只出一辆车”的极端方案浪费大量代数。6.3 罚函数的系数要和成本同量级不可行解的罚函数系数设多少直接决定搜索行为。设得太小不可行解可能在种群中占据主导设得太大算法会过早淘汰所有不可行个体搜索多样性下降。我的经验是先跑一次不带罚函数的版本观察可行解的典型成本量级。比如本问题最优成本在1300左右那么罚函数设1e6就比设1e2或者1e10都要稳妥。1e6意味着不可行解基本没有竞争力但也不会因为数值溢出导致浮点异常。6.4 大规模问题的性能瓶颈有读者可能会问这套代码能不能直接跑50个客户、100个客户。坦白说纯遗传算法加贪心解码50客户还能接受100客户就很吃力了主要瓶颈是解码函数里的时间窗递推循环。MATLAB的for循环效率不高建议提前把距离矩阵、时间窗、服务时间都向量化尽量减少decode内部的循环层次。再往上走就得在遗传算法框架内加入局部搜索比如2-opt或者Or-opt对每条路径做邻域搜索。也可以在每次解码后用简单的“客户点交换”微调路径内顺序。这些都能显著提升解的质量但代价是单次解码耗时增加需要在迭代次数和解质量之间重新平衡。6.5 扩展方向这套代码后续扩展空间很大。比如可以把硬时间窗改成软时间窗加上单位迟到惩罚成本可以加入司机最大连续驾驶时长约束变成带休息时间窗的变体还可以把多车场问题拉进来每辆车从不同车场出发后段基因再多一段“车场编号”。模型越贴近真实业务代码的调度价值越高但核心的编码、解码、罚函数框架是不变的。本文还有配套的精品资源点击获取
多车型带时间窗VRPTW的MATLAB遗传算法求解实战
简介面向物流调度、运筹优化方向的学习者与毕业设计开发者这是一套基于MATLAB求解多车型、多车辆且带时间窗的车辆路径问题VRP源码资源。内容覆盖从初始种群构建、遗传操作到时间窗与载重约束校验的完整流程包含GA_VRPTW.m、InitPopCW.m、draw_Best.m等核心脚本以及c101、c103等标准测试算例数据。资源共29个文件其中以26个m源码和3个mat数据文件为主压缩包仅21KB轻量易用便于快速运行与二次开发。目前已有1765人学习下载。借助该资源读者可以直观理解混合整数规划与启发式算法在VRPTW中的应用掌握自定义目标函数、约束处理及结果可视化的MATLAB实现思路特别适合作为毕业设计或课程项目的基础框架也可根据实际业务场景扩展算法改进与敏感性分析。 前阵子帮一位做城配的朋友梳理配送方案他手头有三十多个门店的补货需求车队八辆车却分大、中、小三种车型而且每家的收货时间窗都不一样——有的早上七点前必须送到有的下午两点以后才接货。这类问题如果用教科书里常见的单车场、单车型VRPTW模型去套出来的方案根本落不了地要么车派得太大空驶成本吓人要么所有时间窗挤在一起司机跑不完。这就是典型的“多车辆、多车型、带时间窗”的路径优化问题在第三方物流、生鲜配送、工程机械调度里非常普遍。这篇文章把我最近用MATLAB从建模、编码到求解、调参的完整过程整理出来代码可以直接改成自己的数据跑。1. 多车型加时间窗为什么教材里的VRP模型不够用先把这个问题的边界说清楚因为很多人一开始就把模型建错了。1.1 传统单车型VRPTW到底缺了什么单车型VRPTW的假设是车队所有车辆一模一样容量相同、固定成本相同、单位行驶成本相同。这在学术论文里很常见但现实里几乎不存在。实际车队里往往是几种车型混用4米2厢货负责小批量门店9米6负责大客户偶尔还有冷链车。如果强行把不同车型抽象成一种结果就是按大车容量去算派车数小车场景空驶率高油费白白烧掉。按小车容量去算大单量客户又装不下还得拆单拆单会把时间窗全部打乱。不同车型的固定使用成本差异非常大大车出一次车的固定成本可能是小车的两倍以上。在大客户集中区域用大车划算在散点客户区域用小车型反而更优。单车型模型的解里根本没有“用哪种车跑哪条路”这个决策维度自然给不出好方案。1.2 时间窗硬约束还是软约束上来就要定清楚时间窗分为两种。硬时间窗指早到可以等待、晚到直接拒绝收货这常见于工厂JIT补货、医院耗材配送软时间窗则允许迟到但会产生惩罚成本比如生鲜配送、快递末端晚一点还能商量。同一个问题里也可能混合存在部分大客户是硬窗普通小客户是软窗。我在MATLAB里实现时默认采用硬时间窗加惩罚机制的做法先按硬时间窗约束去判断可行解所有路径都能满足时间窗才算真正可行如果遗传算法搜索过程中出现违反时间窗的个体不直接淘汰而是通过惩罚项压低其适应度让它在进化中自然被淘汰。这样比“违反即弃”更能保留搜索多样性后面章节会详细讲罚函数怎么设计。1.3 问题输入输出定义要做代码第一步就是把输入输出固化下来输入参数说明车场坐标所有车辆起点和终点客户坐标各客户的经纬度或平面坐标客户需求量每个客户点的货物量时间窗每个客户最早开始服务时间和最晚开始服务时间服务时间在客户点卸货、签收的耗时车型表每种车型的容量、固定成本、单位距离成本、可用数量输出则是每种车型的第几辆车依次访问哪些客户每段路径的行驶方向是什么总成本是多少。这样一套输出才能直接指导调度排班。2. 数学模型决策变量、目标函数与两套核心约束建模是绕不开的一步。虽然我们最终用启发式算法求解但模型写清楚目标函数和约束才不会被代码绕晕。2.1 决策变量如何定义定义两个决策变量x_ij^km第m辆车型k的车辆从客户点i行驶到j取1否则取0。z_k^m第m辆车型k的车被使用取1否则取0。y_i^km客户i由第m辆车型k的车服务取1否则取0。注意这里把“车型”和“车辆序号”都放进下标里了这样每辆车都是独立个体方便约束不同车型的数量上限。比如你有4辆小型车、3辆中型车、2辆大型车那k1时m只能取1到4k2时m取1到3k3时m取1到2。2.2 目标函数固定成本加行驶成本目标函数设计为总成本最小化min Z Σ_k Σ_m f_k · z_k^m Σ_i Σ_j Σ_k Σ_m d_ij · c_k · x_ij^km其中f_k是车型k的固定使用成本c_k是车型k的单位距离行驶成本d_ij是客户点i到j的距离。这里有个容易被忽略的细节多车型问题中大车小车的c_k不能设成一样。大车油耗高单位距离成本必须明显高于小车否则算法会倾向用大车“一车装完”既不符合实际也体现不出优化空间。2.3 约束条件流守恒、容量、时间窗第一组是流守恒约束。每个客户点只能被一辆车访问一次而且进入该点的车必须从同一点离开。用公式写就是Σ_k Σ_m Σ_j x_ij^km 1对所有客户点i成立。这个约束保证了不会出现同一个客户被拆给两辆车服务的情况也排除了路径在某客户点断开的情况。第二组是容量约束。每辆车装载的货物总量不能超过其车型容量Σ_i q_i · y_i^km ≤ Q_k对所有k、m成立。其中q_i是客户i的需求量Q_k是车型k的最大容量。第三组是时间窗约束。车辆到达客户点i的时间记为arr_i必须满足arr_i ≤ b_i如果早于a_i到达则等待到a_i再开始服务。在实际代码里时间是递推计算的。设prev是路径上的前一个客户服务完成离开prev的时间是depart_prev那么到达i的时间是arr_i depart_prev t_prev,i。如果arr_i a_i则服务开始时间start_i a_i否则start_i arr_i。服务完成时间depart_i start_i s_i。这个递推逻辑在解码时高频使用必须写在最核心的代码里。3. 染色体设计与解码逻辑多车型问题最关键的一环模型写完之后最考验功力的就是遗传算法的染色体怎么设计。多车型VRPTW的难点和单车型之间有一个本质差别单车型问题的解只需要确定“客户分组”和“组内顺序”多车型问题还多了一个维度就是“每组由哪种车型执行”。3.1 编码方案一条整数串分成两段我在代码里采用两段式编码。染色体总长度 客户数量N 最大可用车辆数V_max。前N个基因位1到N的一个随机排列表示客户的访问优先级顺序。后V_max个基因位每个基因位取值1到K表示对应编号的车辆采用哪种车型如果取0表示该辆车不出动。为什么不用二进制编码因为客户顺序是一个排列问题二进制编码做交叉变异之后极大概率产生重复客户、缺失客户需要大量修复操作。自然数排列本身就带上“顺序”语义配合部分映射交叉PMX和交换变异子代天然还是合法排列省去很多麻烦。3.2 解码算法贪心切分加可行性回退解码是把基因串翻译成具体路径方案的过程。我的做法是贪心切分加可行性回退维护一个“当前正在构造的路径”初始为空。按客户序列位从前往后扫描尝试把客户i加入当前路径。检查这辆车当前分配好的车型在加入i后容量是否超限时间窗递推是否可行。如果可行加入路径更新车辆的装载量和当前时间。如果不可行关闭当前路径开启下一辆车的路径再把客户i放进新车。如果所有车辆都用完了还有客户没被分配标记为不可行解进入罚函数处理。这个解码策略写起来简单效果也不错。但有一个点必须提醒第5步里“开启下一辆车”时下一辆车的车型是在后段基因里已经定好的。如果后段基因里该车型容量小、成本高解码结果就会很吃亏。这就导致客户序段进化得再好后段车型段不匹配整体适应度仍然上不去。这个耦合关系是遗传搜索中最难处理的地方后文有专门讨论。3.3 时间窗可行性检查的代码细节时间窗检查的递推逻辑看起来不复杂但实现时有个高频错误早到等待时间没有累加。正确写法是arrival max(prevDepart travelTime(prev, i), timeWin(i,1)); if arrival timeWin(i,2) feasible false; return; end depart arrival serviceTime(i);注意arrival取的是“前序离开时间加行驶时间”与“最早开始时间”的较大者。如果只写arrival prevDepart travelTime漏了max那么所有早到客户都会被算成违反时间窗算法几乎找不到可行解。解码的完整流程可以用这样一段伪代码概括函数 decode(individual): 客户序列 individual(1:N) 车型序列 individual(N1:end) 车辆列表 根据车型序列生成容量、固定成本、单位成本 当前车辆指针 1 for 客户 in 客户序列: while True: 尝试将客户加入当前车辆路径 if 容量可行 且 时间窗可行: 加入 break else: 当前车辆指针加1 if 超出车辆数: 返回不可行4. 求解流程与MATLAB核心代码实现编码设计完整之后剩下的就是把遗传算法的框架搭起来。注意遗传算法本身不复杂但MATLAB实现时有几个地方不优化运行起来会非常慢。下面给出我实际调试时用的代码骨架。4.1 数据结构的组织方式先把输入数据打包成一个struct后面所有函数都传这个struct比到处传一堆零散变量清晰得多function model createModel() model.depotXY [50, 50]; % 车场坐标 model.custXY [ 12, 28; 34, 65; 73, 82; 91, 41; 58, 19; 45, 74; 22, 88; 66, 32; 85, 56; 37, 11; 29, 46; 80, 63 ]; % 12个客户坐标 model.demand [18; 25; 30; 12; 22; 17; 35; 20; 28; 15; 19; 26]; model.timeWin [ 0, 120; 30, 90; 60, 180; 45, 150; 0, 100; 80, 200; 100, 240; 50, 160; 90, 210; 20, 110; 40, 140; 70, 190 ]; % 时间窗 [a_i, b_i] model.serviceTime ones(12,1) * 0.3; % 车型表: [容量, 固定成本, 单位距离成本, 可用数量] model.fleet [ 30, 80, 1.0, 4; 50, 120, 1.3, 3; 80, 200, 1.6, 2 ]; model.nCust size(model.custXY, 1); model.vehMax sum(model.fleet(:,4)); % 预计算距离矩阵区分车场(下标1)与客户(下标2~N1) allXY [model.depotXY; model.custXY]; nAll size(allXY, 1); model.dist zeros(nAll, nAll); for i 1:nAll model.dist(i,:) sqrt(sum((allXY - allXY(i,:)).^2, 2)); end end4.2 主程序框架GA主循环的框架如下其中选择用锦标赛交叉用PMX变异用交换加车型重指派精英个体直接保留到下一代rng(42); model createModel(); NP 100; % 种群规模 maxGen 200; % 迭代代数 Pc 0.85; % 交叉概率 Pm 0.15; % 变异概率 nCust model.nCust; vehMax model.vehMax; nTypes size(model.fleet, 1); % 初始化种群 pop zeros(NP, nCust vehMax); for i 1:NP pop(i, 1:nCust) randperm(nCust); % 后段随机分配车型编号0表示该车不出动 typeAssign randi([0, nTypes], 1, vehMax); % 保证至少有一辆车被指派 if all(typeAssign 0) typeAssign(randi(vehMax)) randi(nTypes); end pop(i, nCust1:end) typeAssign; end bestCost zeros(maxGen, 1); for gen 1:maxGen costs zeros(NP, 1); for i 1:NP costs(i) fitness(pop(i,:), model); end bestCost(gen) min(costs); newPop zeros(size(pop)); % 精英保留1个 [~, bestIdx] min(costs); newPop(1,:) pop(bestIdx,:); for i 2:2:NP p1 tournamentSelect(pop, costs, 3); p2 tournamentSelect(pop, costs, 3); if rand Pc [c1, c2] PMXCrossover(p1, p2, nCust); else c1 p1; c2 p2; end if rand Pm c1 mutation(c1, nCust, vehMax, nTypes); end if rand Pm c2 mutation(c2, nCust, vehMax, nTypes); end newPop(i,:) c1; newPop(i1,:) c2; end pop newPop; end4.3 适应度函数解码加罚函数适应度函数是整个算法的核心解码和惩罚都在这里完成。我实现时把不可行解的成本设为一个很大的数但又不是无限大这样算法依然能在种群中保留少量不可行个体用于维持多样性function fit fitness(ind, model) [cost, ~, feasible] decode(ind, model); if feasible fit cost; else fit cost 1e6; % 罚函数 end enddecode函数内部对每条路径计算两部分成本该车的固定成本加上路径中所有相邻点距离乘以该车型的单位距离成本。时间窗可行性的判断就是在构造路径过程中实时检查的。4.4 交叉与变异的实现要点PMX交叉只作用于前N个客户排列段。具体做法是随机选两个交叉点交换两个父代在这段区间内的基因再根据映射关系修复重复客户。这段修复逻辑比较绕但它是保证排列合法性的关键不能省略。变异操作分两段处理客户段随机选两个位置交换保持排列性质车型段则以一定概率随机重置某个车辆的车型编号。我这里特别控制车型段的变异幅度如果变异率太高会导致搜索过程反复重构路径分组收敛速度明显变慢建议变异算子只重置1到2个车位的车型不要整段打乱。5. 算例测试与关键参数调试代码写完之后重点就是验证效果。我拿上面的12客户算例跑了一遍把过程拆开看每一步发生了什么。5.1 算例设置与收敛情况算法参数种群100迭代200代交叉率0.85变异率0.15。三种车型的参数如下车型容量固定成本单位距离成本可用数量小型30801.04中型501201.33大型802001.62前50代目标值下降非常明显从最初的接近2500降到1400左右100代以后进入平缓期到最后收敛在约1280。说明遗传算法对这类规模的问题100代足够找到比较稳定的解。5.2 最终方案解读收敛后的方案用了4辆车3辆小型车、1辆中型车大型车一辆都没用。这个结果其实很符合逻辑这个算例的客户总需求只有267用一辆80容量的大车去跑固定成本200、单位成本1.6还不如用小型车多点几趟。如果某片区域客户密集且单点需求大大车才有优势。从路径结构看4条路径中没有出现路径交叉的现象因为时间窗约束本身就把访问顺序卡住了。比如客户4的时间窗是45到150客户8是50到160如果先访问客户8再访问客户4地理位置绕一圈时间也不一定够。时间窗实际上替搜索过程剪掉了大量低质量路径顺序。5.3 参数敏感性哪些参数最值得调从多组对比测试看影响最大的参数是交叉率和变异率。交叉率低于0.7时前期搜索太慢200代结束时还没收敛变异率高于0.3时后期震荡明显最优解无法稳定保持。建议先跑一组粗略的网格搜索固定其他参数每次只调一个参数记录20次独立运行的平均最优成本和标准差。另外提醒一点种群规模不要迷信越大越好。12客户的问题种群200和种群500的结果几乎一样但耗时增加了1.5倍。对100客户以上的问题可以适当增加种群但对小规模问题维持100到150就足够。6. 高频坑位记录时间窗判罚、车型耦合与收敛陷阱最后这部分是这次实战中最想说的一些经验如果新手照着教程写一遍十有八九会踩在同一批坑上。6.1 时间窗的“早到等待”必须累计开头提过一次这里再展开讲。假设路径是车场→A→BA的时间窗是[50, 100]B的时间窗是[80, 120]车场到A行驶20分钟A到B行驶30分钟。如果你判断A到达时间是20早于50那服务开始时间是50离开A是50加服务时间10等于60到B是90满足B的时间窗。但如果代码里没有max取最大值的逻辑把到达B算成20加30等于50然后误判成违反B的早到时间窗一个本来可行的路径就被标记为不可行了。这个bug会让整个算法在搜索空间里寸步难行。6.2 车型段与客户序段的耦合这是多车型问题特有的坑。我的第一版实现里车型段变异率设得比较高结果每代都把车型配置打乱前面客户序段积累的路径分组信息全部失效目标值一直在高位震荡。后来把车型段变异限制为每次只随机重置一个车位搜索性能立刻改善。另一个相关技巧是初始化种群时不要让车型段全为零。如果你的染色体长度是N加V_maxV_max是总车辆数而后段基因取0时表示该车不出动那么初始化时必须保证至少有两三辆车被分配了实际车型。否则前几十代全在搜索“只出一辆车”的极端方案浪费大量代数。6.3 罚函数的系数要和成本同量级不可行解的罚函数系数设多少直接决定搜索行为。设得太小不可行解可能在种群中占据主导设得太大算法会过早淘汰所有不可行个体搜索多样性下降。我的经验是先跑一次不带罚函数的版本观察可行解的典型成本量级。比如本问题最优成本在1300左右那么罚函数设1e6就比设1e2或者1e10都要稳妥。1e6意味着不可行解基本没有竞争力但也不会因为数值溢出导致浮点异常。6.4 大规模问题的性能瓶颈有读者可能会问这套代码能不能直接跑50个客户、100个客户。坦白说纯遗传算法加贪心解码50客户还能接受100客户就很吃力了主要瓶颈是解码函数里的时间窗递推循环。MATLAB的for循环效率不高建议提前把距离矩阵、时间窗、服务时间都向量化尽量减少decode内部的循环层次。再往上走就得在遗传算法框架内加入局部搜索比如2-opt或者Or-opt对每条路径做邻域搜索。也可以在每次解码后用简单的“客户点交换”微调路径内顺序。这些都能显著提升解的质量但代价是单次解码耗时增加需要在迭代次数和解质量之间重新平衡。6.5 扩展方向这套代码后续扩展空间很大。比如可以把硬时间窗改成软时间窗加上单位迟到惩罚成本可以加入司机最大连续驾驶时长约束变成带休息时间窗的变体还可以把多车场问题拉进来每辆车从不同车场出发后段基因再多一段“车场编号”。模型越贴近真实业务代码的调度价值越高但核心的编码、解码、罚函数框架是不变的。本文还有配套的精品资源点击获取