1 简介

VRP问题在现实生活中应用广泛,很多领域的问题都可以抽象成VRP问题进行解决,其研究和应用一直是热点。 本文首先详细介绍了VRP问题的分类,常见的约束条件及基本的研究技术和方法。给出了几个基本VRP问题的介绍及其数学模型。 模拟退火算法(SA)相对于其它智能算法在求解VRP问题时具有收敛速度快且能找到全局最优解的优点。因此本文详细介绍了模拟退火算法的数学模型及其寻优方法,证明了模拟退火算法可以找到全局最优解,研究了模拟退火算法优缺点。基于模拟退火算法给出了固定车辆数单目标VRP问题的MATLAB语言算法​。

模拟退火法（ simulated annealing,SA） 是一种源于 20 世纪 50 年代、基于 Monte Carlo 迭代求解思想的随机搜索算法， 其出发点是将组合优化问题与统计力学的热平衡作类比，把优化的目标函数视作能量函数，模仿物理学中固体物质的退火处理，先加工使之具有足够高的能量，然后再降温，其内部能量也相应下降，在热平衡条件下，物体内部处于不同状态的概率服从分布，若退火步骤恰当，则最终会形成最低能量的基态。 这种算法思想在求解优化问题时，不但接受对目标函数（ 能量函数）有改进的状态，还以某种概率接受使目标函数恶化的状态，从而可使之避免过早收敛到某个局部极值点， 也正是这种概率性扰动能够使之跳出局部极值点，故而得到的解常常很好。 模拟退火算法于 80 年代开始广泛应用于各种组合优化为题的求解。

2 部分代码

% clc; clear; close all; %% Problem Definition model=SelectModel(); % Select Model of the Problem model.eta=0.1; CostFunction=@(q) MyCost(q,model); % Cost Function %% SA Parameters MaxIt=1200; % Maximum Number of Iterations MaxIt2=80; % Maximum Number of Inner Iterations T0=100; % Initial Temperature alpha=0.98; % Temperature Damping Rate %% Initialization % Create Initial Solution x.Position=CreateRandomSolution(model); [x.Cost, x.Sol]=CostFunction(x.Position); % Update Best Solution Ever Found BestSol=x; % Array to Hold Best Cost Values BestCost=zeros(MaxIt,1); % Set Initial Temperature T=T0; %% SA Main Loop for it=1:MaxIt for it2=1:MaxIt2 % Create Neighbor xnew.Position=CreateNeighbor(x.Position); [xnew.Cost, xnew.Sol]=CostFunction(xnew.Position); if xnew.Cost<=x.Cost % xnew is better, so it is accepted x=xnew; else % xnew is not better, so it is accepted conditionally delta=xnew.Cost-x.Cost; p=exp(-delta/T); if rand<=p x=xnew; end end % Update Best Solution if x.Cost<=BestSol.Cost BestSol=x; end end % Store Best Cost BestCost(it)=BestSol.Cost; % Display Iteration Information if BestSol.Sol.IsFeasible FLAG=' *'; else FLAG=''; end disp(['Iteration ' num2str(it) ': Best Cost = ' num2str(BestCost(it)) FLAG]); % Reduce Temperature T=alpha*T; % Plot Solution figure(1); PlotSolution(BestSol.Sol,model); pause(0.01); end %% Results figure; plot(BestCost,'LineWidth',2); xlabel('Iteration'); ylabel('Best Cost'); grid on;

3 仿真结果

4 参考文献

[1]宋燕子. 基于模拟退火算法的启发式算法在VRP中的应用. (Doctoral dissertation, 华中师范大学).

部分理论引用网络文献，若有侵权联系博主删除。