【路径规划】基于模拟退火算法求解单中心的车辆路径规划问题matlab代码
1 简介VRP问题在现实生活中应用广泛,很多领域的问题都可以抽象成VRP问题进行解决,其研究和应用一直是热点。 本文首先详细介绍了VRP问题的分类,常见的约束条件及基本的研究技术和方法。给出了几个基本VRP问题的介绍及其数学模型。 模拟退火算法(SA)相对于其它智能算法在求解VRP问题时具有收敛速度快且能找到全局最优解的优点。因此本文详细介绍了模拟退火算法的数学模型及其寻优方法,证明了模拟退火算法可以找到全局最优解,研究了模拟退火算法优缺点。基于模拟退火算法给出了固定车辆数单目标VRP问题的MATLAB语言算法。模拟退火法 simulated annealing,SA 是一种源于 20 世纪 50 年代、基于 Monte Carlo 迭代求解思想的随机搜索算法 其出发点是将组合优化问题与统计力学的热平衡作类比把优化的目标函数视作能量函数模仿物理学中固体物质的退火处理先加工使之具有足够高的能量然后再降温其内部能量也相应下降在热平衡条件下物体内部处于不同状态的概率服从分布若退火步骤恰当则最终会形成最低能量的基态。 这种算法思想在求解优化问题时不但接受对目标函数 能量函数有改进的状态还以某种概率接受使目标函数恶化的状态从而可使之避免过早收敛到某个局部极值点 也正是这种概率性扰动能够使之跳出局部极值点故而得到的解常常很好。 模拟退火算法于 80 年代开始广泛应用于各种组合优化为题的求解。2 部分代码% clc; clear; close all; %% Problem Definition modelSelectModel(); % Select Model of the Problem model.eta0.1; CostFunction(q) MyCost(q,model); % Cost Function %% SA Parameters MaxIt1200; % Maximum Number of Iterations MaxIt280; % Maximum Number of Inner Iterations T0100; % Initial Temperature alpha0.98; % Temperature Damping Rate %% Initialization % Create Initial Solution x.PositionCreateRandomSolution(model); [x.Cost, x.Sol]CostFunction(x.Position); % Update Best Solution Ever Found BestSolx; % Array to Hold Best Cost Values BestCostzeros(MaxIt,1); % Set Initial Temperature TT0; %% SA Main Loop for it1:MaxIt for it21:MaxIt2 % Create Neighbor xnew.PositionCreateNeighbor(x.Position); [xnew.Cost, xnew.Sol]CostFunction(xnew.Position); if xnew.Costx.Cost % xnew is better, so it is accepted xxnew; else % xnew is not better, so it is accepted conditionally deltaxnew.Cost-x.Cost; pexp(-delta/T); if randp xxnew; end end % Update Best Solution if x.CostBestSol.Cost BestSolx; 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 Talpha*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, 华中师范大学).部分理论引用网络文献若有侵权联系博主删除。
)
