基于 SA 模拟退火算法的多车辆 TSP 问题 Matlab 仿真，实现多车辆单独搜索最优路径

1.算法仿真效果

matlab2022a仿真结果如下：

 

 

2.算法涉及理论知识概要

 

 

 

      在求解TSP这种整数规划问题的时候, PSO显然与ACO不同, PSO需要对算法本身进行一定的修改, 毕竟PSO刚开始是应用在求解连续优化问题上的.

 

    在路径规划中，我们将每一条路径规划为一个粒子，每个粒子群群有 n 个粒 子，即有 n 条路径，同时，每个粒子又有 m 个染色体，即中间过渡点的个数，每 个点（染色体）又有两个维度（x，y），在代码中用 posx 和 posy 表示一个种群。 通过每一代的演化，对粒子群进行演化操作，选择合适个体（最优路径）。

 

 

 

3.MATLAB核心程序

T0 = 500 ; % initial temperature
r = 0.997 ; % temperature damping rate
Ts = 1 ; % stop temperature
iter = 300;
 
model = initModel();
set(gcf,'unit','normalized','position',[0,0.35,1,0.7]);
 
flag = 0;
 
% initialization
while(1)
route = randomSol(model);
if(isFeasible(route,model)) 
    break; 
end
end
 
cost = calculateCost(route,model);
T = T0;
 
cnt = 1;
minCost = cost;
minRoute = route;
    
maxIterate = 2100;
costArray = zeros(maxIterate,1);
 
% SA
while(T > Ts)
    for k = 1:iter
    mode = randi([1 3]);
    newRoute = createNeibor(route,model,mode);
    newCost = calculateCost(newRoute,model);
    delta = newCost - cost;
    
    if(delta < 0)
        cost = newCost;
        route = newRoute;
    else
        p=exp(-delta/T);
        if rand() <= p 
             cost = newCost;
             route = newRoute;
             
        end
    end
    end