m基于ACO蚁群优化的货车运输路线规划matlab仿真,考虑车辆载重,单位运输成本等因素
目录
1.算法描述
2.仿真效果预览
3.MATLAB核心程序
4.完整MATLAB
1.算法描述
蚁群算法是通过对自然界中真实蚂蚁的集体行为的观察,模拟而得到一种仿生优化算法,它具有很好的并行性,分布性.根据蚂蚁群体不同的集体行为特征,蚁群算法可分为受蚂蚁觅食行为启发的模型和受孵化分类启发的模型,受劳动分工和协作运输启发的模型.本文重点研究了前两种蚁群算法模型. 受蚂蚁觅食行为启发的模型又称为蚁群优化算法(ACO),是继模拟退火算法,遗传算法,禁忌搜索等之后又一启发式智能优化算法.目前它已成功应用于求解TSP问题,地图着色,路径车辆调度等优化问题.本文针对蚁群算法收敛时间长,易陷入局部最优的缺点,通过对路径上信息素的更新方式作出动态调整,建立信息素平滑机制,进而使得不同路径上的信息素的更新速度有所不同,从而使改进后算法能够有效地缩短搜索的时间,并能对最终解进行优化,避免过早的陷入局部最优. 聚类是数据挖掘的重要技术之一,它可按照某种规则将数据对象划分为多个类或簇,使同一类的数据对象有较高的相似度,而不同类的数据对象差异较大.
算法基本思想：
（1）根据具体问题设置多只蚂蚁，分头并行搜索。
（2）每只蚂蚁完成一次周游后，在行进的路上释放信息素，信息素量与解的质量成正比。
（3）蚂蚁路径的选择根据信息素强度大小（初始信息素量设为相等），同时考虑两点之间的距离，采用随机的局部搜索策略。这使得距离较短的边，其上的信息素量较大，后来的蚂蚁选择该边的概率也较大。
（4）每只蚂蚁只能走合法路线（经过每个城市1次且仅1次），为此设置禁忌表来控制。
（5）所有蚂蚁都搜索完一次就是迭代一次，每迭代一次就对所有的边做一次信息素更新，原来的蚂蚁死掉，新的蚂蚁进行新一轮搜索。
（6）更新信息素包括原有信息素的蒸发和经过的路径上信息素的增加。
（7）达到预定的迭代步数，或出现停滞现象（所有蚂蚁都选择同样的路径，解不再变化），则算法结束，以当前最优解作为问题的最优解。
1.1发车
选择节点X为发车节点选择该节点的发车数量Y.检索连通节点，排除禁忌表内节点，按照信息素浓度随机选择节点，将该节点加入路径表，将上一节点加入禁忌表，反复调用此方法直至抵达邮件目的地，对路径上节点做一次信息素增加，对全部节点做一次信息素挥发，挥发时判断各个节点车辆数是否过少如果过少则提高挥发率.
1.2到站
节点可看到下一目的地为自身的且当前位置在路上的车辆，当车到达时点击抵达——记录行驶成本，需记录在额外的表中.
1.3中途发车
如果行驶路径中仍有节点，判断当前节点是否有目的地与改车辆路径相符的邮件，如果有则将这些邮件装车直至邮件装完或者到达载重最大值，依行驶路径继续发车，车辆状态改为驶向节点Z。
1.4终点返程
如果行驶路径中没有节点了，将车辆目的地设为车辆归属地，判断当前节点是否有目的地与改车辆路径相符的邮件，如果有则将这些邮件装车直至这些邮件装完或者到达载重最大值，将车辆驶向车辆归属地节点。
2.仿真效果预览
matlab2022a仿真结果如下：
3.MATLAB核心程序
%蚁群算法的参数
n = 9;
%信息素增加量
gamma0 = 0.1;
gamma = gamma0*ones(LEN,n);
%低于一定百分比,这里设置为50%
lvl1 = 0.5;
lvl2 = 0.7;%正常值
rho0 = 0.05; % 信息素挥发因子
rho = rho0*ones(LEN,n);delta = 0.00012;alpha = 0.5; % 信息素重要程度因子
beta = 0.5; % 启发函数重要程度因子
Q = 1; % 常系数
Eta = 1./D; % 启发函数
m = Tlate-Tearly;
Tau = 0.01*ones(LEN,n); % 信息素矩阵
Table = zeros(LEN,n); % 路径记录表
iter = 1; % 迭代次数初值
iter_max = 50;%迭代寻找最佳路径
while iter <= iter_max %%iter if iter==1gamma0=0.1*ones(size(gamma)); end% %首先记录运输车辆的发车时间并对车辆的到达时间做出预估，得出不同时间的各个节点的承运能力记录，for i=1:Tlate-Tearly;%这里按时间段进行分类统计不同整数时间段的邮件数量和重量s1 = Tearly+i-1;e1 = Tearly+i;idx = find(Timee>=s1 & Timee < e1);L = length(idx);Mail_point0{i} = ends(idx);%....Mail_Wpoint0{i} = package2(idx,6);%....Mail_nums0(i,1) = L;%....Mail_weight0(i,1) = sum(package2(idx,6));for j = 1:length(idx)Mail_paths0{i}{j} = mypaths{idx(j)};endMail_idx0{i} = package2(idx,1);endMail_point = Mail_point0;Mail_Wpoint= Mail_Wpoint0;Mail_nums = Mail_nums0;Mail_weight= Mail_weight0;Mail_paths = Mail_paths0;Mail_idx = Mail_idx0;%对Mail_paths进行处理cnt1=1;for i=1:Tlate-Tearly;s1_ = [];e1_ = [];for j1 = 1:length(Mail_paths0{i})path_tmp1 = Mail_paths0{i}{j1};if isempty(path_tmp1)==0s1_(j1) = path_tmp1(1);e1_(j1) = path_tmp1(end);endendbs=[];%得到唯一值ms=[];%唯一值的缩影ns=[];%相同的位置[bs,ms,ns] = unique(e1_);%合并相同的idxx=[];for j1=1:length(bs)idxx = find(ns==j1);%输出唯一路径Mail_paths0_unique{i}{j1} = Mail_paths0{i}{ms(j1)};Mail_point0_unique{i}(j1) = bs(j1);%....%质量合并Mail_Wpoint0_unique{i}{j1} = Mail_Wpoint0{i}(idxx);%....Mail_Wpoint0_sumunique{i}{j1} = sum(Mail_Wpoint0{i}(idxx));%....%统计合并后的各个区间的邮件编号Mail_idx0_total{i}{j1} = Mail_idx0{i}(idxx);%....endendMail_point__ = Mail_point0;Mail_Wpoint__= Mail_Wpoint0_sumunique;Mail_nums__ = Mail_nums0;Mail_weight__= Mail_weight0;Mail_paths__ = Mail_paths0_unique;Mail_idx__ = Mail_idx0_total;%Mail_point%Mail_Wpoint%Mail_nums%Mail_weight%Mail_pathsfigure(1);subplot(211)bar([Tearly:Tlate-1],Mail_nums)title('不同时间段下的邮件数量');subplot(212)bar([Tearly:Tlate-1],Mail_weight)title('不同时间段下的邮件总重量');%%%当蚂蚁出发时，预估到达各个节点时该节点的承运量水平Carrying_capacity1 = zeros(Tlate-Tearly,n);%不同时刻，不同节点的承运量水平Carrying_capacity2 = zeros(Tlate-Tearly,n);%不同时刻，不同节点的承运量水平对应的百分比Carrying_select = zeros(Tlate-Tearly,n);%路节点被选择的概率越来越低。for i=1:Tlate-Tearly;point = Mail_point{i};for j = 1:n%统计各个节点的承运量水平Npoint = find(point==j);if isempty(Npoint)==0Carrying_capacity1(i,j) = [sum(sum(Mail_Wpoint{i}))]/(ceil((Tlate-Tearly)/2));Carrying_capacity2(i,j) = Carrying_capacity1(i,j)/sum(sum(Carrying_capacity1));elseCarrying_capacity1(i,j) = 0;Carrying_capacity2(i,j) = 1; endendend%%%如果预计到达某节点时该节点承运能力低于一定百分比，即使蚂蚁选择了这个节点，通过后信息素增加量也会很少，for i=1:Tlate-Tearly;point = Mail_point{i};for j = 1:n%统计各个节点的承运量水平Npoint = find(point==j);if Carrying_capacity2(i,j) lvl2rho(i,j) = rho0;gamma(i,j)= gamma0(i,j); endendendendend%%addcar = zeros(Tlate-Tearly,n);for i=1:Tlate-Tearly;for j = 1:nif Carrying_capacity2(i,j) < lvl1%如果某个节点滞留的快件过多%增加其他车辆前来的几率帮助此节点减轻快件压力。以此来达到整个运输网络的负载均衡。addcar(i,j)=1;%用这个变量表示当前时刻对应的节点增加车辆，如果是0，则不增加endendend%更新Tablem = LEN;%每个邮件对应一个蚂蚁，构建信息表start = zeros(m,1);for i = 1:mstart(i) = Xsel;end%先将起点写入禁忌表Table(1:m,1) = start; %构建解空间citys_index = 1:n;%禁忌表Table的更新for i = 1:mtarget = mypaths{i};for j = 2:length(target)Table(i,j) = target(j);endfor j = length(target)+1:nTable(i,j) = target(end);endend% 计算各个蚂蚁的路径距离Length = zeros(m,1);for i = 1:mRoute = Table(i,:);target = mypaths{i};for j = 1:length(target)-1Length(i) = Length(i) + D(Route(j),Route(j + 1));endLength(i) = Length(i) + D(Route(n),Route(1));end%概率选择优化，参考文献3.4.2for i = 1:mRoute = Table(i,:);for j = 1:nif mean(Carrying_capacity2(:,j))<0.4miu=0.2; endif mean(Carrying_capacity2(:,j))>0.4 & mean(Carrying_capacity2(:,j))<1miu=0.7; endif mean(Carrying_capacity2(:,j))>=1miu=1; endif j<=n-1PP(i,j) = (1-miu) * Tau(i,j)^alpha*[1/D(Route(j),Route(j + 1))]^beta/sum(sum(Tau(i,:).^alpha.*[1./D(Route(j),:)].^beta)) + miu*gamma(i,j)/gamma0(i,j);elsePP(i,j) = (1-miu) * Tau(i,j)^alpha*[1/D(Route(1),Route(j))]^beta/sum(sum(Tau(i,:).^alpha.*[1./D(Route(j),:)].^beta)) + miu*gamma(i,j)/gamma0(i,j); endPP(i,j) = min(PP(i,j),1);endend % 计算最短路径距离及平均距离for i = 1:LENif iter == 1[min_Length,min_index] = min(Length);Length_best(iter) = min_Length; Length_ave(iter) = mean(Length);%找到最大概率值[VV,II] = max((PP(i,:)));Route_best{iter} = Table(i,1:II); else[min_Length,min_index] = min(Length);Length_best(iter) = min(Length_best(iter - 1),min_Length);Length_ave(iter) = mean(Length);if Length_best(iter) <= min_Length[VV,II] = max(sum(PP));Route_best{iter} = Table(i,1:II); elseRoute_best{iter} = Route_best{iter-1};endend%通过遗传之后，更新mypath这个变量，这样后面的消重合叠加的就是蚁群优化的后的变量了%mypathss{i} = unique(Table(i,1:II)) ; [ioo,joo] = unique(Table(i,1:II),'first');mypathss{i} = Table(i,sort(joo)); end%更新信息素Delta_Tau = zeros(n,n);for i = 1:mfor j = 1:nTau(i,j) = (1-rho(i,j)) * Tau(i,j) + rho(i,j)*gamma(i,j);%论文公式3.11 gamma为要求中提到的每次修正后的增量endend iter = iter + 1;gamma0=Tau;
end
%更新，
mypaths=mypathss;
for i=1:Tlate-Tearly;%这里按时间段进行分类统计不同整数时间段的邮件数量和重量s1 = Tearly+i-1;e1 = Tearly+i;idx = find(Timee>=s1 & Timee < e1);L = length(idx);Mail_point0{i} = ends(idx);%....Mail_Wpoint0{i} = package2(idx,6);%....Mail_nums0(i,1) = L;%....Mail_weight0(i,1) = sum(package2(idx,6));for j = 1:length(idx)Mail_paths0{i}{j} = mypaths{idx(j)};endMail_idx0{i} = package2(idx,1);
end
Mail_point = Mail_point0;
Mail_Wpoint= Mail_Wpoint0;
Mail_nums = Mail_nums0;
Mail_weight= Mail_weight0;
Mail_paths = Mail_paths0;
Mail_idx = Mail_idx0;
%对Mail_paths进行处理
cnt1=1;
for i=1:Tlate-Tearly;s1_ = [];e1_ = [];for j1 = 1:length(Mail_paths0{i})path_tmp1 = Mail_paths0{i}{j1};if isempty(path_tmp1)==0s1_(j1) = path_tmp1(1);e1_(j1) = path_tmp1(end);endendbs=[];%得到唯一值ms=[];%唯一值的缩影ns=[];%相同的位置[bs,ms,ns] = unique(e1_);%合并相同的idxx=[];for j1=1:length(bs)idxx = find(ns==j1);%输出唯一路径Mail_paths0_unique{i}{j1} = Mail_paths0{i}{ms(j1)};Mail_point0_unique{i}(j1) = bs(j1);%....%质量合并Mail_Wpoint0_unique{i}{j1} = Mail_Wpoint0{i}(idxx);%....Mail_Wpoint0_sumunique{i}{j1} = sum(Mail_Wpoint0{i}(idxx));%....%统计合并后的各个区间的邮件编号Mail_idx0_total{i}{j1} = Mail_idx0{i}(idxx);%....end
endMail_point__ = Mail_point0;
Mail_Wpoint__= Mail_Wpoint0_sumunique;
Mail_nums__ = Mail_nums0;
Mail_weight__= Mail_weight0;
Mail_paths__ = Mail_paths0_unique;
Mail_idx__ = Mail_idx0_total;%%
id=0;
for i = 1:Tlate-Tearlypointss=Mail_paths__{i};for j = 1:length(pointss)id=id+1;%把路径记录下来Shortest_Route，d = func_RL2d(Mail_paths__{i}{j},dist2);LL{id} = d;%路径长度RL{id} = Mail_paths__{i}{j}; %路径编号NM{id} = id; %路径编号end
end%如果路径已记录累加路径上通过的邮件质量
%邮件质量
for i = 1:LENMASS2(i) = MASS(i);%重量MASST(i) = package2(i,6); %路径质量
endMASS3=MASS2;
for i = 1:Ynum%将路径记录在车辆信息后，将记录的该路径质量归零，邮件状态设置为在车牌为XXXXX的某辆车上；if MASS3(i)>=MASST(i)%载重大于等于质量最高的路径Info{i}{1} = ['在车牌为',num2str(CARD(NM{i},:)),'的某辆车上'];Info{i}{2} = [MASST(i)];%记录车辆载重MASST(i) = 0;%清零end%则将路径记录在车辆信息后，将记录的该路径质量减去车辆载重的数值，%邮件状态依序设置为在车牌为XXXXX的某辆车上直至车辆满载if MASS3(i)=MASSotherInfo{j}{2} = Info{j}{2}+MASSother;MASS(Ynum+i)=0;Info0{j}{1}=MASSother;elseInfo{j}{2} = MASS(j);Info0{j}{1}= 0;endendendend
end%%
%到站
%节点可看到下一目的地为自身的且当前位置在路上的车辆，当车到达时点击抵达
%——记录行驶成本（按照车辆载重*节点间公里数*收费标准），
%需记录在额外的表中（记录下车牌号，抵达时间，行驶路径段，这段路的载重，产生的费用，这段路运输的邮件数量）
%——更新车辆信息（当前位置），更新车辆上邮件所在地（即更新表中当前运输车辆为车牌XXXXX的车辆的邮件所在地为抵达的节点）
Info2=Info;%这个阶段，用info2去更新for i = 1:Ynumtmps1 = Info2{i}{1};%车牌信息tmps2 = Info2{i}{2};%重量%根据路段计算长度dist = func_RL2d(RL{i},dist2);Info2{i}{3} = tmps2*dist*MONEY;%记录行驶成本按照车辆载重*节点间公里数*收费标准）Info2{i}{4} = RL{i};%行驶路径段%计算时间times = func_RL2T(RL{i},TME2);Info2{i}{5} = times;%这段路运输的邮件数量Info2{i}{6} = tmps2/package2(i,6);%当前位置Info2{i}{7} = RL{i}(end);
end%——判断抵达情况（终点，节点1，不是终点也不是节点1）
for i = 1:Ynumif RL{i}(end)==package2(i,5)%终点Info2{i}{8} = 1;%抵达情况elseif RL{i}(end)==package2(i,4)%节点1Info2{i}{8} = 0;%抵达情况elseInfo2{i}{8} = 2;%不是终点也不是节点1 end
end
%——①如果是终点则将所有邮件从车上卸载（删去当前运输车辆中的属性），
%将已抵达的邮件（当前所在地与目的地相同）状态设置为已抵达，记录抵达时间，然后使用终点返程功能
%——②如果如果到达的节点不是终点但是是节点1，先将目的地与当前所在地一致的邮件卸车，
for ii = 1:Ynumif Info2{ii}{8}==1%终点Info2{ii}{2}=0;%卸载，变为0.Info2{ii}{9}=1;%已抵达Info2{i}{6}为抵达时间%终点返程%如果行驶路径中没有节点了，将车辆目的地设为车辆归属地，%判断当前节点是否有目的地与改车辆路径相符的邮件，%如果有则将这些邮件装车直至这些邮件装完或者到达载重最大值，将车辆驶向车辆归属地节点。for i = 1:LEN-Ynum%——将未装车邮件目的地ends = package2(Ynum+i,5); %未装车邮件目的地的节点MASSother = MASS(Ynum+i);for j = 1:Ynum%未满载车辆路径进行比对Paths = RL{j};%如果未满载车辆%判断当前节点是否有目的地与改车辆路径相符的邮件idx = find(Paths(end)==ends);if isempty(idx) == 1%没有经过，不做处理endif isempty(idx) == 0%有经过Info2{j}{1} = ['在车牌为',num2str(CARD(NM{j},:)),'的某辆车上']; if Info2{j}{2} < MASS(j); %如果没装满if MASS(j)-Info2{j}{2}>=MASSotherInfo2{j}{2} = Info2{j}{2}+MASSother;MASS(Ynum+i)=0;elseInfo2{j}{2} = MASS(j);endendendendendendif Info2{ii}{8}==0%节点1Info2{ii}{2}=Info2{ii}{2}-Info0{ii}{1};%卸载，变为0.先将目的地与当前所在地一致的邮件卸车，即中间临时存放的Info2{ii}{9}=1;%抵达Info2{i}{6}为抵达时间%中途发车功能%如果行驶路径中仍有节点，判断当前节点是否有目的地与改车辆路径相符的邮件，%如果有则将这些邮件装车直至邮件装完或者到达载重最大值，%依行驶路径继续发车，车辆状态改为驶向节点Z。for i = 1:LEN-Ynum%——将未装车邮件目的地ends = package2(Ynum+i,5); %未装车邮件目的地的节点MASSother = MASS(Ynum+i);for j = 1:Ynum%未满载车辆路径进行比对Paths = RL{j};%如果未满载车辆%如果行驶路径中仍有节点，判断当前节点idx = find(Paths(2)==ends);if isempty(idx) == 1%没有经过，不做处理endif isempty(idx) == 0%有经过Info2{j}{1} = ['在车牌为',num2str(CARD(NM{j},:)),'的某辆车上']; if Info2{j}{2} < MASS(j); %如果没装满if MASS(j)-Info2{j}{2}>=MASSotherInfo2{j}{2} = Info2{j}{2}+MASSother;MASS(Ynum+i)=0;elseInfo2{j}{2} = MASS(j);endendendendendendif Info2{ii}{8}==2%不是终点也不是节点1 Info2{ii}{2}=Info2{ii}{2};%将这些邮件卸车Info2{ii}{9}=1;%抵达Info2{i}{6}为抵达时间end
end
%更新价格和时间
for i = 1:Ynumtmps1 = Info2{i}{1};%车牌信息tmps2 = Info2{i}{2};%重量%根据路段计算长度dist = func_RL2d(RL{i},dist2);Info2{i}{3} = tmps2*dist*MONEY;%记录行驶成本按照车辆载重*节点间公里数*收费标准）Info2{i}{4} = RL{i};%行驶路径段%计算时间times = func_RL2T(RL{i},TME2);Info2{i}{5} = times;
end%根据上面的数据分别统计各个邮件的行走信息
xx = 0;
xy = 0;
for i = 1:length(Mail_idx__)tmps = Mail_idx__{i};weigh= Mail_Wpoint0_unique{i};for j = 1:length(tmps)xy = xy+1;tmps2 =tmps{j};weigh2=weigh{j};yx =mod(xy,Ynum)+1;for k = 1:length(tmps2)xx = xx + 1;%邮件对应车辆的车牌信息pkg_info{xx}{1}=Info2{yx}{1};%邮件的本身重量pkg_info{xx}{2}=weigh2(k);%记录重量*节点间公里数*收费标准）pkg_info{xx}{3}=pkg_info{xx}{2}*func_RL2d(Mail_paths__{i}{j},dist2)*MONEY;%%行驶路径段pkg_info{xx}{4}=Mail_paths__{i}{j};%计算时间pkg_info{xx}{5}=func_RL2T(Mail_paths__{i}{j},TME2);%和其相同路段上的邮件数量pkg_info{xx}{6}=length(tmps2);%邮件序号pkg_info{xx}{7}=tmps2(k);endend
end
%%
%核算部分,计算运输成本与平均运达所需时间
for ii = 1:length(Info2)moneys(ii) = Info2{ii}{3};times(ii) = Info2{ii}{5};
end
moneysavg = mean(moneys)
timesavg = mean(times)
02_075m 4.完整MATLAB
V
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！