基于SA模拟退火优化的TWVRP路径规划matlab仿真

1.算法仿真效果 matlab2022a仿真结果如下：

2.算法涉及理论知识概要 模拟退火算法（simulated annealing，SAA）来源于固体退火原理，是一种基于概率的算法。模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。

   模拟退火算法的搜索过程是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程，通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。

   以上特性使得模拟退火算法具备在路径规划领域应用的价值，比如用于解决旅行商问题（TSP）、有时间窗车辆路径问题（VRP）、有容量限制的VRP问题（CVRP）等.

   模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。
   模拟退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis [1]  等人于1953年提出。1983 年,S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。

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

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

   由于VRP问题的持续发展，考虑需求点对于车辆到达的时间有所要求之下，在车辆途程问题之中加入时窗的限制，便成为带时间窗车辆路径问题（VRP with Time Windows, VRPTW）。带时间窗车辆路径问题（VRPTW）是在VRP上加上了客户的被访问的时间窗约束。在VRPTW问题中，除了行驶成本之外, 成本函数还要包括由于早到某个客户而引起的等待时间和客户需要的服务时间。在VRPTW中，车辆除了要满足VRP问题的限制之外，还必须要满足需求点的时窗限制，而需求点的时窗限制可以分为两种，一种是硬时窗（Hard Time Window），硬时窗要求车辆必须要在时窗内到达，早到必须等待，而迟到则拒收；另一种是软时窗（Soft Time Window），不一定要在时窗内到达，但是在时窗之外到达必须要处罚，以处罚替代等待与拒收是软时窗与硬时窗最大的不同。

3.MATLAB核心程序

model        = data.model;
model.eta    = 0.1;
 
CostFunction = @(q) MyCost(q,model);     
 
MaxIt          = 1000;     
MaxIt2         = 80;      
T0             = 100;       
alpha          = 0.99;    
 
x.Position     = CreateRandomSolution(model);
[x.Cost x.Sol] = CostFunction(x.Position);
 
BestSol        = x;
 
BestCost       = zeros(MaxIt,1);
 
nfe            = zeros(MaxIt,1);
 
T              = T0;
 
for it=1:MaxIt
    it
    for it2=1:MaxIt2
        xnew.Position        = CreateNeighbor(x.Position);
        [xnew.Cost xnew.Sol] = CostFunction(xnew.Position);
        
        if xnew.Cost<=x.Cost
           x=xnew;
        else
           delta=xnew.Cost-x.Cost;
           p=exp(-delta/T);
            
           if rand<=p
              x=xnew;
           end
        end
 
        if x.Cost<=BestSol.Cost
           BestSol=x;
        end
    end
    BestCost(it) = BestSol.Cost;
    nfe(it)      = NFE;
    if BestSol.Sol.IsFeasible
       FLAG=' *';
    else
       FLAG='';
    end
    T=alpha*T;
    figure(1);
    PlotSolution(BestSol.Sol,model);
end