【VRP】基于matlab模拟退火算法求解单中心多车辆路径规划问题【含Matlab源码 1072期】

举报
海神之光 发表于 2022/05/30 23:15:01 2022/05/30
【摘要】 一、模拟退火算法简介 1 模拟退火算法的原理 模拟退火算法(SA)是一种适用于大规模组合优化问题的有效近似算法,来源于对固体退火过程的模拟。统计力学表明,在给定初始温度的条件下,通过将温度缓慢降低,微观...

一、模拟退火算法简介

1 模拟退火算法的原理
模拟退火算法(SA)是一种适用于大规模组合优化问题的有效近似算法,来源于对固体退火过程的模拟。统计力学表明,在给定初始温度的条件下,通过将温度缓慢降低,微观粒子会在各个温度达到热平衡状态,当物体冷却到常温时达到基态,内能达到最小。模拟固体退火的过程,给定一个初始温度和初始解,随着温度的下降,每一个温度状态下,通过解的变换生成新的解。如果解的目标函数值小于前一个解,接受当前解;否则,以概率接受新解。最终的解是迭代寻优的结果。模拟退火算法以概率突跳性,能够跳出局部最优陷阱,找到全局最优解。模拟退火算法依据Metropolis接收准则接受新解,而不是使用完全确定的规则。它构成了模拟退火算法退火过程的基础。当固体从状态i经过降温变化到状态j,它所具有的能量从E(i)变化到E(j)。显然,如果E(j)<E(i),接受新的状态j。否则,依据概率P接受新解。
在这里插入图片描述
其中,K是物理学波尔兹曼常数,T是固体的温度。

这种概率,在路径规划的问题中,就是当新解的目标函数值小于原来的解的函数值,新解仍被接受的概率。以x表示温度T下的一个解,通过退火,可以生成一个新解x′。那么,接收x′的概率为:
在这里插入图片描述
2 模拟退火算法模型的建立
2.1 目标函数
首先,规定解空间。对销售点B,C,U重新进行编号(2,3,…,21),A点为产业园,既是起点也是终点,将它进行两次编号,记为1号和22号,以便于程序计算。问题转化为求解从1出发,走遍所有中间点,到达22的一个最短路径。本文通过运用百度拾取坐标系统,获得产业园和商铺点的经纬度信息。由于,本文选取的点的范围在徐州都市圈,两点之间的曲线距离可以近似看作直线距离。用k1和k2分别表示经度、纬度和千米的换算系数,将经纬度转换为千米。通过改进坐标距离公式计算距离:
计算得到皮草产业园和所有销售点中,任意两点间的距离,构成一个对称矩阵D=(dij)22×22。规定z1,z2,…,z22中,z2,z3,…z21,是由2~21随机打乱得到的一组数,则dzizi+1表示所有可能路径中,第i个和第i+1个经过的点间的距离。目标函数为运输经过所有目标的路径长度最小:
在这里插入图片描述
2.2 模拟退火算法实现过程
Step 1初始化
通过MATLAB随机模拟数给定初始路径,计算得到初始路径长度。设定初始温度T(0)=1。

Step 2产生新解
运用变换法,任选序号a,b(a<b),交换a和b之间的顺序,得到新的路径:
在这里插入图片描述
Step 3判定标准
新路径与原路径长度的差可以表示为:
在这里插入图片描述
当路径差Δf<0时,用新路径代替原路径。否则,以概率exp(-Δf/T)接受新的路径。
Step 4重复步骤2和步骤3,进行迭代。
Step 5结束条件
选用降温系数α,令T←αT,得到新的温度。当温度降至终止温度,算法结束,输出当前状态。

二、部分源代码

clc;
clear;
close all;

T0 = 500 ; % 初始温度
r = 0.997 ; % 温度阻尼率
Ts = 1 ; % 最终温度
iter = 300;

model = initModel();
set(gcf,'unit','normalized','position',[0.1,0.2,0.8,0.7]);

flag = 0;

% 初始化
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);

%模拟退火算法
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


  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53

三、运行结果

在这里插入图片描述
在这里插入图片描述

四、matlab版本及参考文献

1 matlab版本
2014a

2 参考文献
[1] 包子阳,余继周,杨杉.智能优化算法及其MATLAB实例(第2版)[M].电子工业出版社,2016.
[2]张岩,吴水根.MATLAB优化算法源代码[M].清华大学出版社,2017.
[3]王旭颖,杨金云,陈哲,倪秋铭,刘朱丹.基于模拟退火算法的电商物流配送问题研究[J].中国管理信息化. 2021,24(07)

3 备注
简介此部分摘自互联网,仅供参考,若侵权,联系删除

文章来源: qq912100926.blog.csdn.net,作者:海神之光,版权归原作者所有,如需转载,请联系作者。

原文链接:qq912100926.blog.csdn.net/article/details/125035754

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。