外卖配送VRPTW路径优化：MATLAB遗传算法建模与调优

简介：围绕外卖配送路径优化，这份MATLAB遗传算法项目面向物流方向学生、算法初学者与配送调度研究者，用于理解如何用全局搜索方法求解订单分配与路线安排问题。压缩包共4个文件，含3个m脚本与1份pptx演示文稿，整体约191KB，分别承载算法实现、配送匹配、等待时间计算及问题背景与实验结果讲解。代码部分涵盖种群初始化、适应度评估、选择、交叉和变异等遗传算法核心环节，并把配送距离、等待时间等因素纳入方案评价；配套演示则从模型构建、算法原理到结果分析展开，便于把抽象思路与可运行脚本对应起来。已有3614人学习，适合作为课程设计、毕业项目或调度优化的入门参考，读者可据此梳理算法流程、复现实验并迁移到同类配送优化场景。

1. 外卖配送路径优化：为什么直接套 TSP 模板会失效

外卖配送的路径优化，如果直接套用旅行商问题那套遗传算法模板，跑出来的路线在现实里基本没法执行：骑手先取了 5 号单的餐，绕三公里去送 12 号单，等折回 5 号单的商家时餐已经凉了。外卖配送从来不是 TSP，而是带时间窗、带取送配对、带多骑手装载上限的 pickup-delivery VRPTW。用 MATLAB 做外卖配送遗传算法优化，真正难的地方在于把「先取后送」「出餐等待」「超时惩罚」「骑手工作量均衡」这些约束编码进染色体，并且保证交叉变异时不把它们打碎；写几十行选择交叉变异本身并不构成难点。一旦保序性和可行性被算子破坏，适应度再漂亮也只是数值游戏。

2. 染色体编码与解码：一串数字怎么变成骑手的行驶轨迹

遗传算法在路径问题上遇到的第一个关键分界点，是基因型到表现型的映射到底由谁承担。有两种截然不同的流派：一种把「哪个骑手送哪一单」直接写进染色体，让基因型几乎等于表现型；另一种只编码订单的先后次序，骑手分配完全交给解码器现场决定。选哪一种，直接决定了后面交叉算子好不好写、搜索空间有多大。

2.1 显式骑手基因与隐式分配的分野

最常见的做法是双段染色体：前半段是一个长度 N 的订单排列（N 为待配送订单数），后半段是一个长度 N 的骑手编号数组，第 i 位表示排列中第 i 单派给哪个骑手。这种编码的好处是直观、易调试、约束注入方便——想让某个骑手休息，直接把对应基因位锁死就行。代价是搜索空间被放大了约 K^N 倍（K 为骑手数），大量染色体其实是同一个解的重复表达，收敛速度会被稀释。

另一条路是经典的 2N 编码：每单拆成取餐节点 +i 和送餐节点 −i，染色体是 2N 个带符号基因的排列，隐含「+i 必须出现在 −i 之前」的优先级约束。这套写法在 pickup-delivery problem 里很正统，但放到外卖场景有点过度设计。外卖的取送是强耦合的，骑手取到餐之后几乎不会再去别处闲逛，一单就是一个不可分割的服务单元；拆成两个独立节点后，交叉算子极容易生成「先送后取」的非法个体，反而要额外写修复逻辑。

实务上更常用的是「订单排列 + 贪心插入解码」的组合：染色体只保留一个 N 长的排列，骑手分配由解码器按最小增量成本现场决定。这种 split 式解码把一部分组合优化交给了启发式，搜索空间从 K^N 降到 N!，收敛明显更快。代价是失去了对单个骑手工作量的直接控制，得靠适应度里的均衡项去拉回来。

提示：如果订单规模在 50 单以内、骑手数不超过 10，双段编码加修复算子的组合更稳；订单上百单以后再考虑 split 解码，否则 N! 的空间也撑不住。

2.2 解码器：早到等待与多骑手时间线推进

解码器才是整个算法里最容易被低估的部分。它的任务是把一条抽象的订单序列翻译成若干条带时刻的行驶路线，并在这个过程中把「商家出餐时间」「骑手当前所在位置」「顾客时间窗」全部推进一遍。这里和普通 VRPTW 最大的差别是早到必须等待：普通配送可以提前送达，外卖不行，餐没做好骑手只能在店门口刷手机。这个max(arrive, ready)的动作看起来无害，实际上会让成本函数变成非线性的——同一单插在路线前面还是后面，超时量可能差出一大截。

function [routes, detail] = decodeGreedy(chrom, prob) % chrom : 1×N 订单排列，第 k 位是订单编号 % prob : 问题结构体，含 D(行驶时间矩阵) / ready(出餐时刻) / due(承诺送达) % 对每单尝试插入所有骑手路径的所有位置，取增量成本最小者 routes = cell(1, prob.nRider); % 每个骑手一条订单序列 detail = struct('arrivePick', [], 'arriveDrop', [], 'late', []); for k = 1:numel(chrom) o = chrom(k); bestDelta = inf; bestR = 0; bestPos = 0; for r = 1:prob.nRider % pos = 0 表示插在整条路径最前面，numel 表示插在末尾 for pos = 0:numel(routes{r}) d = insertionDelta(routes{r}, pos, o, prob); if d < bestDelta bestDelta = d; bestR = r; bestPos = pos; end end end % 增量最小未必全局最优，但单步贪心在 90% 的算例上已足够 routes{bestR} = [routes{bestR}(1:bestPos), o, routes{bestR}(bestPos+1:end)]; end end function delta = insertionDelta(route, pos, o, prob) % 计算把订单 o 插到 route 的第 pos 位之后，该骑手总成本的变化量 % 成本 = 行驶时间 + 早到等待折算 + 超时罚 + 容量越界罚 seq = [route(1:pos), o, route(pos+1:end)]; delta = routeCost(seq, prob) - routeCost(route, prob); end function c = routeCost(seq, prob) t = 0; node = prob.depot; c = 0; load = 0; for i = 1:numel(seq) o = seq(i); p = prob.pickup(o); d = prob.drop(o); tArrive = t + prob.D(node, p); tPick = max(tArrive, prob.ready(o)); % 早到等待，外卖的关键差异点 tDrop = tPick + prob.svc(p) + prob.D(p, d); c = c + prob.D(node,p) + prob.D(p,d) ... + prob.wWait * (tPick - tArrive) ... + prob.wLate * max(0, tDrop - prob.due(o)); load = load + 1; if load > prob.cap, c = c + prob.wCap * (load - prob.cap); end t = tDrop + prob.svc(d); node = d; end end

insertionDelta用「重算整条路径再相减」这种朴素方式，时间复杂度是 O(L)，套在 O(N·K·L) 的插入循环里，一次解码大约是 O(N²K)。N=100、K=10 的量级下单次解码在几十毫秒，对遗传算法动辄上万次评估来说偏贵，常见的加速手段是用前缀时间数组做增量计算，把 O(L) 压到 O(1)。wWait、wLate、wCap这三个权重就是下一章要拆的适应度设计，它们与解码器里的成本口径必须严格一致，否则会出现「解码器算出来很好、适应度函数算出来很差」的错位。

3. 适应度函数：超时、超载、不均衡怎么折算成一个数

遗传算法本身只会比较大小，它不理解什么是「超时」，也不理解什么是「公平」。所有现实约束最终必须压缩成一个标量，这个过程叫标量化（scalarization），而它是整个项目里最容易留下隐患的地方——权重设错，算法会非常认真地朝错误方向优化。

3.1 成本项拆解与量纲统一

外卖场景里通常要同时兼顾四类目标，它们的物理意义完全不同，必须先换算到同一量纲才能相加。最常见的做法是统一折算成「分钟」：行驶时间本身就是分钟，超时是分钟，早到等待也算分钟，骑手工作量不均衡则折算成「最长骑手时长与平均时长之差」。这样所有权重都变成一个无量纲的相对系数，调参时凭直觉调不会崩。

权重之间是此消彼长的关系，不存在一组万能参数。经验上超时罚必须比行驶时间高一个数量级，否则算法会用「多绕五分钟换一次准点」这种明显不划算的交易去凑解；而均衡项一旦超过 2，算法会开始牺牲总时长去强行拉平，总配送成本反而上升。

3.2 罚系数为什么不能一设了之

静态罚函数的问题在于它假设搜索过程中可行域的位置是固定的，但遗传算法早期种群几乎全是不可行解，此时罚系数太小会让不可行解凭借更短的行驶距离胜出，种群被带偏；罚系数太大又会让所有个体的适应度都被罚项主导，等于在比较「谁违规少」，搜索梯度消失，早熟收敛。这个现象在迭代曲线上表现得很典型：目标值前 30 代下降很快，之后完全走平，而实际解的质量还很差。

常见的解法是让罚系数随代数递增，早期宽容、后期严格。另一种更平滑的思路是让罚系数与当前种群的违约率挂钩：如果当代 80% 的个体都超时，说明这个约束在当前搜索阶段太难满足，罚系数就该温和一点；如果只有 5% 的个体超时，说明大部分解已经可行，此时该重罚，把剩下那批赶出可行域边界。

function [fit, stats] = fitness(pop, prob, gen, cfg) % pop : 种群矩阵，每行一条染色体 % gen : 当前代数，用于动态罚系数 % 返回归一化后的适应度（越小越好）与违约统计 n = size(pop, 1); raw = zeros(n, 1); lateRate = zeros(n, 1); % 罚系数随代数从 alpha0 线性升到 alpha1 alpha = cfg.alpha0 + (cfg.alpha1 - cfg.alpha0) * gen / cfg.maxGen; for i = 1:n [routes, det] = decodeGreedy(pop(i,:), prob); [cTravel, cLate, cWait, cBal] = evalRoutes(routes, det, prob); raw(i) = cTravel + cfg.wWait*cWait + cfg.wBal*cBal; lateRate(i) = cLate / numel(pop(i,:)); % 超时订单占比 raw(i) = raw(i) + alpha * cLate; % 动态罚项只作用于超时 end % 锦标赛选择需要「越大越好」，这里做一次线性变换 fit = 1 ./ (raw + eps); stats.meanLate = mean(lateRate); stats.feasible = mean(lateRate < 0.02); % 可行个体比例，用于诊断 end

alpha0一般取 1～3，alpha1取 20～50，比例控制在 10 倍以上。stats.feasible这一项是排查阶段最有价值的观测量：健康的情况下它应该在前 20% 的代数里从接近 0 爬升到 0.9 以上；如果一直停在 0.1 附近，基本可以断定是罚系数涨得太慢或者解码器本身有问题，而不是种群规模不够大。

4. 遗传算子：OX 交叉、变异与局部搜索怎么配合

算子设计的核心矛盾只有一句话：既要打散基因产生新组合，又不能让组合变得非法。路径问题里这个矛盾被放大得尤其明显，因为一个位置的改动会连带影响后面所有节点的时间推进。

4.1 OX 交叉的保序性为什么正好匹配路径问题

单点交叉在排列编码上会产生重复基因和缺失基因，需要额外修复，而且修复后的子代和父代往往差异巨大，等于把父代的优良片段全毁了。顺序交叉（Order Crossover，OX）的做法是：随机截取父代 A 的一段连续片段直接复制到子代相同位置，剩余位置按父代 B 中基因的相对顺序依次填入。这样既保证每个订单恰好出现一次，又保留了 B 中「谁在谁前面」的相对次序。

保序性对路径问题来说是极其宝贵的性质。一条好的配送路线，其价值主要体现在「哪些单被排在一起」这个局部结构上，绝对位置并不重要——A 段在染色体的第 3 位还是第 30 位无所谓，只要它内部那几单的相对先后还在，这段路线的时间窗可行性大概率还能维持。OX 恰好保护了这种相对结构，所以它在 VRPTW 上的表现长期优于 PMX 和循环交叉。

如果用的是双段编码，骑手基因段要单独处理：常见做法是整段从父代 A 复制，或者按订单基因的对应关系从 B 里挑——后者更严谨，能保证「同一单的订单基因和骑手基因不被拆散」。这一点如果漏了，会出现染色体里订单顺序来自 A、骑手分配来自 B 的混乱个体，解码出来的路线质量随机性极大。

function [c1, c2] = oxCrossover(p1, p2) % p1, p2 : 1×N 订单排列，元素为 1..N 的一个排列 N = numel(p1); a = sort(randperm(N, 2)); % 随机选两个切点 c1 = zeros(1, N); c2 = zeros(1, N); c1(a(1):a(2)) = p1(a(1):a(2)); % 片段原样继承 c2(a(1):a(2)) = p2(a(1):a(2)); % 剩余基因按另一父代的相对顺序环形填入 c1 = fillRemain(c1, p2, a); c2 = fillRemain(c2, p1, a); end function c = fillRemain(c, donor, a) N = numel(c); used = c(c > 0); % 从切点之后开始扫描 donor，跳过已被继承的基因 donorSeq = [donor(a(2)+1:end), donor(1:a(2))]; donorSeq(ismember(donorSeq, used)) = []; idx = [a(2)+1:N, 1:a(1)-1]; % 填回的顺序也必须环形 c(idx) = donorSeq; end

idx这一行的环形处理是最容易写错的地方。如果直接按[1:a(1)-1, a(2)+1:N]的顺序填，子代的基因顺序会从中间断开，原本在 donor 里相邻的两个订单被强行拆到路线两端，交叉的意义就损失了一大半。这种错误不会报错，也不会产生非法解，只是默默地让算法性能下降 10%～20%，属于典型的隐性 bug。

4.2 变异算子的实际有效性排序

路径问题上常见的变异有三种：交换（swap，随机交换两个位置）、逆序（inversion，翻转一段连续片段）、插入（relocate，取出一个基因插到别处）。三者的破坏力完全不同，实测下来在带时间窗的问题上效率排序通常是插入 > 逆序 > 交换。

原因不难理解。交换只改变两个订单的位置，扰动最小，但产生的变化往往不改变路线的整体结构，容易陷入局部；逆序会反转一整段的顺序，在 TSP 上很有效，但外卖配送有严格的时间窗，把一段路线的方向翻过来几乎必然造成大量超时，等于在制造不可行解；插入相当于把一单从路线的某个位置搬到另一个位置，正好对应现实中「调单」这个动作，扰动量适中且大概率仍可行。

变异概率的设定也要跟着算子走。插入变异因为破坏力温和，概率可以设到 0.2～0.3；逆序变异超过 0.1 就会让种群质量剧烈震荡。

4.3 模因化：每代对精英做一次邻域下降

纯遗传算法在 100 单以上的算例上，通常收敛到某个平台后就再无进展，因为交叉变异只能做粗粒度的组合，做不了「把第 7 单和第 12 单对调能省 3 分钟」这种细粒度优化。把局部搜索嵌进遗传算法每一代（这种结构叫 memetic algorithm）是性价比最高的一步改进。

具体做法不必复杂：每代选出前 10% 的精英个体，对每个个体做一次 or-opt 邻域扫描——把某一单取出，尝试插入原路线的其他位置，如果成本下降就接受，扫描一轮或者改进次数超过阈值就停。这个操作的计算量是 O(N²)，比一次完整解码还便宜，但收益远超多跑 50 代遗传迭代。

注意：局部搜索的评估口径必须和解码器完全一致，包括早到等待的折算方式。曾经见过一份实现里局部搜索只算行驶时间、不管超时，结果精英个体被优化成了「跑得快但全部超时」的形态，再喂回种群后把整个种群带偏，收敛曲线看着挺好，实际准点率跌到 60%。

5. 排查：跑不出可用解时先看这五处

遗传算法有个让人头疼的特性：它不会报错。代码跑完、图也画出来了、迭代曲线还挺好看，但解是错的。下面这几条是这类项目里反复出现的症状，按「现象 → 原因 → 解决」逐条拆。

5.1 解质量类：曲线好看，路线不可执行

现象一：迭代曲线单调下降得很漂亮，但把最优染色体解码出来，几乎每单都超时。原因基本锁定在罚系数上——罚项权重太低，算法发现「无视时间窗」能换来更短的行驶距离，于是全体朝这个方向进化。解决方式是先把wLate提到行驶时间的 20 倍跑一次，确认能产出可行解，再逐步往下调，找到准点率和总时长的平衡点。反过来调（从小到大）很容易在错误的参数区间里浪费一整天。

现象二：最优解里出现「先送达再取餐」，或者同一单被服务两次。这是编码层面的问题。双段编码如果交叉时把订单基因段和骑手基因段分开独立交叉，就会产生订单顺序来自父代 A、骑手分配来自父代 B 的失配个体；而 2N 编码如果不做优先级修复，交叉后必然出现 −i 排在 +i 前面。解决方式是为每对取送节点维护一个位置索引，交叉后扫描一遍，凡是违反先取后送的，把 −i 强行挪到 +i 之后，或者直接对这条染色体重新解码。

现象三：跑 200 代以后完全不再改进，种群内个体几乎一模一样。典型的早熟收敛。除了提高变异率，更根本的原因是初始化太单一——如果种群全是随机生成的排列，前几代的选择压力会把稍微好一点的那批迅速复制满全场。可行的改法是初始化时混入一部分用贪心插入构造的解（比如按承诺送达时刻排序后依次插入），让初始种群的质量分布拉开，同时保留足够的随机个体维持多样性。

5.2 复现与效率类：每次结果都不一样、越跑越慢

现象四：同样的输入数据，今天跑出 82 分钟，明天跑出 96 分钟，无法复现。MATLAB 的随机数生成器默认以时间为种子，遗传算法本身又是强随机的，不复现是必然的。解决方式是在脚本开头显式固定种子并记录版本信息，把「某次跑出来的好结果」变成可追溯的实验记录，而不是靠记忆。

rng(20240501, 'twister'); % 固定种子，保证同一次实验可复现 cfg.popSize = 200; cfg.maxGen = 500; cfg.alpha0 = 2; cfg.alpha1 = 40; result = runGA(prob, cfg); save(fullfile('runs', sprintf('seed_%d.mat', 20240501)), 'result', 'cfg');

单次结果的好坏其实参考价值有限，我一般会固定五组不同种子各跑一遍，看最优值的分布区间。如果五次的结果标准差超过均值的 8%，说明算法稳定性不足，问题多半出在种群规模太小或者变异率太低，而不是「这次运气不好」。

现象五：跑到一百多代以后单代耗时越来越长，内存也一路涨。常见原因是种群矩阵在循环里用pop = [pop; newInd]这种方式增长，MATLAB 每次都要重新分配并复制整块内存，复杂度是 O(n²)。另一个原因是把每一代的全种群和解码明细都存进了结构体数组，500 代 × 200 个体 × 每条路线的完整时刻表，几个 GB 很容易就吃满了。解决方式是预分配pop = zeros(popSize, N)，历史记录只保留每代的最优值和平均违约率这两个标量。

提示：想保留完整轨迹做分析时，不要存全种群，只存每代最优个体的染色体和它的解码结果。信息量足够复现问题，体积小两个数量级。

6. 设计取舍：遗传算法在这个流程里到底该负责哪一段

把遗传算法用在外卖配送优化上，最需要想清楚的问题其实是它适合承担哪一段工作，「它能不能用」反而在其次。这类问题有三类成熟解法：精确求解（混合整数规划）、构造式启发式（贪心插入、 saving 算法）、元启发式（遗传算法、禁忌搜索、自适应大邻域）。三者的能力边界差得很远。

精确求解在 20 单以内可以拿到最优解和明确的下界，是验证其他算法质量的黄金标准，但规模一过 50 单，求解时间就从秒级跳到小时级，且对时间窗这类强约束极度敏感。构造式启发式极快，一次插入扫描就能出一个能跑的方案，缺点是解的质量天花板明显，遇到骑手数量紧张、时间窗密集的算例会明显劣化。遗传算法的位置在中间：它没有最优性保证，也不保证每次都收敛到同一个解，但它能在可接受的时间内处理上百单规模，而且约束的添加方式极其灵活——想加一条「同一骑手连续送餐不超过 6 单」，只需要在适应度里加一项，不用重构整个模型。这个灵活性在业务规则频繁变动的场景里是决定性的优势。

因此我倾向于把遗传算法放在流程的第二段：先用构造式启发式生成一个质量尚可的初始解集，把它混进随机种群，让遗传算法从一个不错的起点出发；再用局部搜索在每代对精英做精修。三步组合起来，收敛所需代数通常能压到纯随机初始化的一半以下。

验证方式上，我一般不看单次最优值，而是看三个指标：五次独立运行的最优值标准差、可行个体比例爬升到 0.9 所需的代数、以及和构造式启发式解相比的相对改进幅度。如果相对改进低于 5%，说明遗传算法在这个算例上没有发挥空间，不如直接用启发式，把省下来的时间拿去做别的。如果标准差很大，先别急着加种群规模，检查一下变异率和初始化策略更划算。

说个自己的教训。刚接触这类问题时，我把注意力全放在迭代曲线上，看到曲线平滑下降就以为成了，直到把最优路线画到地图上才发现，有一半的订单被安排给了同一个骑手，其他人几乎空跑——因为适应度里根本没写均衡项，算法当然会往「集中派单减少空驶」的方向优化，这在数学上完全正确，在业务上完全不可接受。从那以后我每次建模都强制走一遍「把约束逐条翻译成成本项」的清单，宁可多写三项罚函数，也不让任何一个业务规则只存在于口头约定里。希望帮到你。

本文还有配套的精品资源，点击获取