遗传算法（GA）求解容量受限的车辆路径（CVRP）问题MATLAB代码

先明确问题：仓库有若干辆车，每辆车载重有限，要给多个客户送货，每个客户有明确需求。目标是用最少的车辆跑最短的总距离。这里假设所有客户都能被服务，不存在超载情况。

遗传算法（GA）求解容量受限的车辆路径（CVRP）问题MATLAB代码

核心思路就是生成一堆可能的路径方案（种群），然后让这些方案不断进化。咱们分步来说：

% 基础参数设置
numCustomers = 20;        % 客户数量
maxLoad = 100;            % 车辆最大载重
popSize = 50;             % 种群规模
mutationRate = 0.02;      % 变异率

初始化种群是关键，这里用了个取巧的方法——在染色体中插入0表示车辆分隔点。比如[0,5,3,0,2,7]表示两辆车：第一辆跑5→3，第二辆跑2→7。

function pop = initializePopulation()
    pop = zeros(popSize, numCustomers + popSize -1); % 预留分隔符位置
    for i = 1:popSize
        % 随机排列客户，插入分隔符
        route = randperm(numCustomers);
        splitPoints = sort(randi([1,numCustomers],1,randi(5)+1)); 
        chromosome = insertZeros(route, splitPoints);
        pop(i,1:length(chromosome)) = chromosome;
    end
end

适应度函数需要同时考虑车辆数和总距离。这里用了倒数处理，数值越大越好：

function fitness = calculateFitness(pop)
    for i = 1:size(pop,1)
        routes = decodeChromosome(pop(i,:)); % 解码染色体为路径集合
        totalDistance = sum(arrayfun(@(x) calcRouteDist(x), routes));
        numVehicles = length(routes);
        fitness(i) = 1/(totalDistance + numVehicles*100); % 车辆数权重设大些
    end
end

交叉操作要特别注意容量限制。这里用顺序交叉（OX），保证子代不出现重复客户：

function child = crossover(parent1, parent2)
    % 去除分隔符后操作
    p1 = parent1(parent1~=0);
    p2 = parent2(parent2~=0);
    
    % 随机选取交叉段
    startPos = randi(length(p1));
    endPos = randi([startPos, length(p1)]);
    segment = p1(startPos:endPos);
    
    % 保留父代2中不包含交叉段的元素
    remaining = p2(~ismember(p2, segment));
    child = [remaining(1:startPos-1), segment, remaining(startPos:end)];
    
    % 重新插入分隔符
    child = insertSplitPoints(child, maxLoad);
end

变异操作用了三种方式随机触发：交换两个客户位置、反转某段路径、随机插入分隔符。这样可以增加种群多样性：

function mutated = mutate(chromosome)
    if rand() < 0.3 % 位置交换
        pos = randperm(length(chromosome),2);
        mutated = chromosome;
        mutated(pos) = mutated(fliplr(pos));
    elseif rand() < 0.3 % 路径反转
        start = randi(length(chromosome));
        finish = randi([start, length(chromosome)]);
        mutated = chromosome;
        mutated(start:finish) = fliplr(mutated(start:finish));
    else % 随机插入分隔符
        mutated = insertSplitPoints(chromosome, maxLoad);
    end
end

跑起来之后发现几个有趣现象：

1. 初期进化速度很快，30代左右就能找到较优解
2. 车辆数和总距离存在权衡关系，需要调整适应度函数的权重系数
3. 当客户位置呈现明显聚类特征时，算法表现更好

完整跑一次大概需要迭代100-150代，最终解的质量取决于初始种群多样性和变异策略。想进一步提升效果可以试试：

• 加入局部搜索（如2-opt优化）
• 动态调整交叉变异概率
• 用精英保留策略防止优秀个体丢失

代码里有个魔鬼细节：insertSplitPoints函数需要实时检测载重量，当累积需求超过车辆载重时必须插入分隔符。这个约束处理直接关系到解的可行性，实现的时候要特别注意容量计算的准确性。