车辆路径规划问题（Vehicle Routing Problem, VRP）是运筹学和组合优化领域中最经典的 NP-Hard 问题之一。而在实际的物流配送、外卖调度、垃圾回收等场景中，车辆往往有着最大载重量的限制，这就是带容量限制的车辆路径规划问题（Capacitated VRP, CVRP）。

在初学启发式算法时，往往会被 VRP 复杂的约束条件劝退。本文将带你拨开迷雾，从数学模型到算法设计，深入浅出地讲解如何使用**遗传算法（Genetic Algorithm, GA）**来求解 CVRP，并给出 MATLAB 核心代码实现。

---

📐 一、 CVRP 的数学模型定义

在动手写代码之前，必须先将现实问题抽象为严谨的数学模型。

假设有一个配送中心（Depot，编号为 $0$）和 $n$ 个客户点（编号为 $1,2,...,n$）。

• 图的定义：完全图 $G=(V,E)$，其中顶点集 V={0,1,2,...,n}V=\{0,1,2,...,n\}V={0,1,2,...,n}。
• 距离矩阵：节点 $i$ 到节点 $j$ 的距离为 $D_{ij}$。
• 客户需求：每个客户 $i$ 有确定的货物需求量 $q_i$。
• 车辆属性：车队中有 $K$ 辆相同的车，每辆车的最大载重量为 $Q$。

我们的优化目标是最小化所有车辆的总行驶距离：
$$\min Z=\sum _{k=1}^K\sum _{i=0}^n\sum _{j=0}^n{D}_{ij}{x}_{ijk}$$

核心约束条件：

1. 容量约束：每辆车服务的所有客户的总需求量不能超过车辆容量 $Q$：
   ∑i=1nqiyik≤Q,∀k∈{1,...,K}\sum_{i=1}^{n}q_iy_{ik}\le Q,\quad\forall k\in\{1,...,K\}i=1∑n​qi​yik​≤Q,∀k∈{1,...,K}
2. 一次访问约束：每个客户必须且只能被一辆车访问一次。
3. 流量守恒约束：车辆到达某个客户点后，必须离开该点（不能原地消失）。

(注：$x_{ijk}$ 为 0-1 变量，表示车辆 $k$ 是否从节点 $i$ 行驶到节点 $j$；$y_{ik}$ 为 0-1 变量，表示客户 $i$ 是否由车辆 $k$ 服务。)

---

🧬 二、 遗传算法（GA）求解 CVRP 的核心设计

将 GA 应用于约束优化问题，最关键的一步是编码方式和解码/约束处理机制。

1. 编码机制：客户全排列（Order-first）

初学者最容易犯的错误是尝试将车辆编号和客户编号混合编码，这会导致交叉和变异时产生大量不可行解。
我们采用纯客户编号的全排列编码。假设有 8 个客户，一个个体的染色体可能长这样：
[3, 1, 4, 5, 2, 8, 6, 7]

2. 解码与约束处理：贪婪切分（Split-second）

拿到全排列后，如何分配车辆？我们采用顺序累加，超载即派新车的策略：

1. 从起点 $0$ 出发，按染色体顺序依次访问客户。
2. 累加当前路线的客户需求 $q_i$。
3. 如果加入下一个客户会导致总需求 $>Q$，则当前车辆返回起点 $0$，下一辆车从 $0$ 出发继续服务。

例如：路线为 [3, 1, 4, 5...]，车辆容量 $Q=100$。
客户 3 ($q=40$)，客户 1 ($q=50$)，客户 4 ($q=30$)。

• 车1：服务 3 -> 服务 1，已载 90。再去 4 会超载 ($90+30=120>100$)。
• 因此，车1 路线为：0 -> 3 -> 1 -> 0。
• 车2 从 0 出发，服务 4…

3. 遗传算子设计

• 选择算子 (Selection)：采用锦标赛选择（Tournament Selection），保留精英个体，加速收敛。
• 交叉算子 (Crossover)：采用顺序交叉（Order Crossover, OX）。传统的单点交叉会产生重复的客户编号，而 OX 完美保留了父代的部分相对顺序，且不产生重复基因。
• 变异算子 (Mutation)：在路径规划中，采用 2-Opt（翻转变异） 效果极佳。随机选择两个基因位，将它们之间的子串逆序，这有助于消除路径中的“交叉打结”现象。

---

💻 三、 MATLAB 核心代码骨架

这里给出 GA 主循环和贪婪解码的核心逻辑，大家可以将这段代码嵌入到自己的框架中。

% GA 求解 CVRP 核心骨架
function [bestRoute, bestDist] = GA_CVRP(customers, depot, Q, popSize, maxGen)
    % customers: n x 3 矩阵 [x坐标, y坐标, 需求量]
    n = size(customers, 1);
    
    % 1. 初始化种群 (生成 1~n 的全排列)
    Pop = zeros(popSize, n);
    for i = 1:popSize
        Pop(i, :) = randperm(n);
    end
    
    % 算法参数
    Pc = 0.8; % 交叉概率
    Pm = 0.1; % 变异概率
    
    % 进化主循环
    for gen = 1:maxGen
        Fitness = zeros(popSize, 1);
        
        % 2. 评估适应度 (解码与计算距离)
        for i = 1:popSize
            Fitness(i) = EvaluateCVRP(Pop(i,:), customers, depot, Q);
        end
        
        % 记录最优解
        [~, bestIdx] = min(Fitness);
        
        % 3. 锦标赛选择
        newPop = TournamentSelection(Pop, Fitness);
        
        % 4. 交叉 (OX交叉)
        newPop = OrderCrossover(newPop, Pc);
        
        % 5. 变异 (2-Opt翻转)
        newPop = ReversalMutation(newPop, Pm);
        
        % 精英保留策略
        Pop = newPop;
        Pop(1, :) = Pop(bestIdx, :); % 强制保留上一代的最优个体
    end
end

% --- 核心：解码与适应度计算函数 ---
function totalDist = EvaluateCVRP(chromosome, customers, depot, Q)
    currentLoad = 0;
    currentLoc = depot(1:2);
    totalDist = 0;
    
    for i = 1:length(chromosome)
        custIdx = chromosome(i);
        demand = customers(custIdx, 3);
        custLoc = customers(custIdx, 1:2);
        
        % 容量判定
        if currentLoad + demand > Q
            % 超载，回程
            totalDist = totalDist + norm(currentLoc - depot(1:2));
            % 派新车
            currentLoc = depot(1:2);
            currentLoad = 0;
        end
        
        % 前往客户点
        totalDist = totalDist + norm(currentLoc - custLoc);
        currentLoad = currentLoad + demand;
        currentLoc = custLoc;
    end
    % 最后一辆车回程
    totalDist = totalDist + norm(currentLoc - depot(1:2));
end

---

🚀 四、 算法调优与进阶探讨

如果你跑完上面的基础版本，发现结果在面对大规模节点（如 100+ 客户）时容易陷入局部最优，这是正常现象。此时你需要思考：

1. 种群多样性维持：标准的 GA 容易早熟收敛。可以考虑引入多模态优化（MMO）中的小生境（Niche）技术，或者当种群相似度过高时强制注入随机变异个体。
2. 局部搜索的混合 (Memetic Algorithm)：在 GA 的每次迭代后，对优秀个体进行局部搜索（如禁忌搜索或模拟退火），能大幅提高解的精度。
3. 多目标扩展 (MO-CVRP)：现实中，我们往往不仅想让总距离最短，还想让使用的车辆数最少，或者负载最均衡。此时问题就变成了经典的多目标优化问题（MOP），可以尝试引入基于 Pareto 支配或拓扑分类的策略来求解前沿。

如果你对进化计算和运筹优化方向感兴趣，欢迎关注我的后续更新！

💡 获取完整源码 https://mbd.pub/o/bread/ZZyVmJlp

本文只展示了核心逻辑。完整代码呢包含完整初始化、路线可视化绘图函数、基准测试集读取（如 Solomon 数据集）的完整可用 MATLAB 源码，我已经打包整理好。有需要的同学可以在评论区留言或私信获取~