Matlab车辆配送路径规划问题 各类vrp代码 带时间窗的路径规划问题 遗传算法 蚁群算法 模拟退火算法 混合粒子群算法解决 tsp cvrp dvrp cdvrp vrptw问题 tsp:旅行商问题，寻找最短闭合路径 cvrp:带容量约束的车辆路径规划 dvrp:带距离约束的车辆路径规划 cdvrp:带距离+容量约束的车辆路径规划 vrptw：带距离+容量+时间窗约束的车辆路径规划

最近在折腾物流调度系统的仿真，发现Matlab真是个宝藏工具箱。今天咱们就聊聊怎么用各种智能算法解决不同等级的车辆路径规划问题（VRP），顺手撸点代码片段方便各位直接实操。

Matlab车辆配送路径规划问题 各类vrp代码 带时间窗的路径规划问题 遗传算法 蚁群算法 模拟退火算法 混合粒子群算法解决 tsp cvrp dvrp cdvrp vrptw问题 tsp:旅行商问题，寻找最短闭合路径 cvrp:带容量约束的车辆路径规划 dvrp:带距离约束的车辆路径规划 cdvrp:带距离+容量约束的车辆路径规划 vrptw：带距离+容量+时间窗约束的车辆路径规划

先来个热身，旅行商问题（TSP）这种单线程任务最适合练手。用遗传算法处理的话，关键是把路径编码成染色体。比如用randperm生成初始种群：

function pop = initPop(popSize, cityCount)
    pop = zeros(popSize, cityCount);
    for i=1:popSize
        pop(i,:) = randperm(cityCount);
    end
end

适应度函数就是路径总距离的倒数，这里用矩阵运算加速计算：

function fitness = calcFitness(pop, distMatrix)
    [N, n] = size(pop);
    fitness = zeros(N,1);
    for i=1:N
        route = pop(i,:);
        fitness(i) = 1/(sum(distMatrix(sub2ind(size(distMatrix),...
                       route, [route(2:end) route(1)]))));
    end
end

交叉操作推荐用OX交叉，比单点交叉更能保持路径有效性。注意这里的环形索引处理：

function child = oxCrossover(parent1, parent2)
    n = length(parent1);
    cut1 = randi(n-1);
    cut2 = randi([cut1+1 n]);
    
    segment = parent1(cut1:cut2);
    remaining = parent2(~ismember(parent2, segment));
    child = [remaining(1:cut1-1) segment remaining(cut1:end)];
end

进阶到带容量约束的CVRP问题时，编码方式就要变了。这时候每个染色体需要包含配送点和仓库的交替序列。比如用0作为仓库分隔符，[0,1,2,0,3,4,0]表示两辆车分别配送1-2和3-4。

适应度计算时需要同时检查载重约束：

function [totalDist, isValid] = cvrpFitness(route, demand, capacity, distMatrix)
    currentLoad = 0;
    totalDist = 0;
    prevNode = 1; % 仓库起始
    
    for node = route(2:end)
        if node == 0
            totalDist = totalDist + distMatrix(prevNode, 1);
            currentLoad = 0;
            prevNode = 1;
        else
            if currentLoad + demand(node) > capacity
                isValid = false;
                return;
            end
            totalDist = totalDist + distMatrix(prevNode, node);
            currentLoad = currentLoad + demand(node);
            prevNode = node;
        end
    end
    isValid = true;
end

处理时间窗约束的VRPTW时，算法复杂度直线上升。这时候模拟退火的退火策略反而可能比遗传算法更有效。关键是在邻域搜索时加入时间校验：

function newRoute = vrptwNeighbor(route, timeWindows, serviceTime)
    newRoute = route;
    i = randi(length(route)-1);
    j = randi(length(route)-1);
    newRoute([i j]) = newRoute([j i]);
    
    % 时间窗校验
    currentTime = 0;
    for k = 2:length(newRoute)
        arrivalTime = currentTime + distMatrix(newRoute(k-1), newRoute(k));
        if arrivalTime < timeWindows(newRoute(k),1)
            currentTime = timeWindows(newRoute(k),1) + serviceTime;
        elseif arrivalTime > timeWindows(newRoute(k),2)
            newRoute = route; % 回退无效移动
            return;
        else
            currentTime = arrivalTime + serviceTime;
        end
    end
end

混合粒子群算法在处理多约束问题时表现亮眼，特别是结合了遗传算法的交叉变异操作。这里有个速度更新的小技巧——用路径相似度作为速度量度：

function velocity = updateVelocity(particle, pbest, gbest)
    % 交换序列作为速度分量
    swap1 = getSwapSequence(particle, pbest);
    swap2 = getSwapSequence(particle, gbest);
    velocity = [swap1; swap2];
    
    % 随机丢弃部分交换避免过长
    if size(velocity,1) > 5
        velocity = velocity(randperm(size(velocity,1),5),:);
    end
end

实际工程中经常要处理30个以上配送点的情况，这时候单纯的智能算法可能力不从心。个人经验是先用聚类算法（比如K-means）分区，再在每个分区内做路径规划，最后用动态规划调整区域边界点。

function clusters = kmeansClustering(customers, vehicleCount)
    [idx, ~] = kmeans(customers(:,2:3), vehicleCount);
    clusters = cell(vehicleCount,1);
    for i=1:vehicleCount
        clusters{i} = customers(idx==i, 1)';
    end
end

最后给个忠告：永远别相信单次运行结果！智能算法带有随机性，至少跑五次取最优解。碰到路径突然暴涨的情况，记得检查距离矩阵是不是对称的——现实中的单行道问题会让矩阵不对称，这个坑我掉进去过三次...