基于SA模拟退火算法的多车辆TSP问题求解matlab仿真

1.程序功能描述
       基于SA模拟退火算法的多车辆TSP问题求解matlab仿真，三个车辆分别搜索其对应的最短路径，仿真后得到路线规划图和SA收敛曲线。

2.测试软件版本以及运行结果展示
MATLAB2022A版本运行

（完整程序运行后无水印）

3.核心程序

while(T > Ts)
    % 对于每次迭代
    for k = 1:Miter
        % 随机选择邻域操作模式
        mode      = randi([1 3]);
        % 生成新路径
        XLine_new = func_Neibor(Xline,Para,mode);
        % 计算新路径的成本
        Jnew      = func_fitness(XLine_new,Para);
        % 计算成本差值
        delta     = Jnew - JJ;
        
        % 如果新路径的成本更低
        if(delta < 0)
           JJ    = Jnew;
           Xline = XLine_new;
        else
           % 计算接受概率
           p=exp(-delta/T);
           % 随机数小于接受概率则接受新路径
           if rand() <= p 
              JJ = Jnew;
              Xline = XLine_new;
           end
        end
    end
    
    % 记录当前成本
    Jsave(cnt) = JJ;
    % 如果当前成本低于最低成本
    if JJ<Jmin
       Jmin  = JJ;
       XLmin = Xline;
    end
    
    % 更新温度
    T   = T*deacy; % 退火
    cnt = cnt+1;
    
    % 绘图
    figure(2);
    if mod(cnt,50)==1
       func_show(XLmin,Para);
    end
    drawnow
end
 
% 新建一个图形窗口
figure;
plot(Jsave);
xlabel('迭代次数');
ylabel('SA适应度值收敛');
grid on

4.本算法原理
       基于模拟退火算法（Simulated Annealing, SA）求解多车辆旅行商问题（Vehicle Routing Problem with Multiple Traveling Salesmen, VRPMTS）是一个复杂而有趣的问题。在这个问题中，我们需要为一组车辆规划一条路径，使得每辆车从起点出发，访问一系列城市后返回起点，同时使得总的旅行成本（通常是总距离）最小化。模拟退火算法因其全局寻优能力和避免陷入局部最优解的能力而成为求解此类问题的有效工具。

       多车辆旅行商问题（VRPMTS）是指给定一组城市和一组车辆，要求为每辆车规划一条路径，使得每辆车从起点出发，访问所有城市恰好一次，并最终回到起点，同时使总的旅行成本最小化。

       模拟退火算法通过一个温度参数T 控制搜索过程。在初始阶段，T 设定得很高，允许算法接受劣质解（即成本增加的解）。随着算法运行，T 逐渐降低，最终趋向于零。这样，算法能够跳出局部最优解，探索更广阔的解空间，最终收敛到全局最优解或接近最优解。

       算法步骤如下：

       模拟退火算法因其全局寻优能力和避免陷入局部最优解的能力而成为求解多车辆旅行商问题的有效工具。通过合理设定初始温度、温度衰减率以及停止温度，结合适当的邻居解生成方法和成本计算方法，模拟退火算法能够有效地找到接近最优解的解决方案。