基于遗传算法的自动化立体仓库路径优化问题求解
- 格式：pdf
- 大小：243.43 KB
- 文档页数：7
基于遗传算法的自动化立体仓库路径优化问题求解
（SolvingPathOptimizationProblemofAutomated
WarehouseBasedonGeneticAlgorithm）
问题描述：
立体仓库中有多个巷道，每一个巷道内都有一台有轨道的堆垛机，它负责两边货架货箱的存
取工作；智能运输车（AGV）从仓库的入库口得到需要入库的货箱并把它们放到相应货架
的货架入库台上，堆垛机从那里得到货箱，并把货箱放到与其相应货格中，再把要取出的货
箱从相应的货格中取出，放到该货架的货架出库台上，再由AGV将它们运送到出货台上，
之后通过货物自动分拣系统分拣，再从分拣口将分拣后货箱通过汽车等运输工具运送到不同的分厂或车间，这就是自动化立体仓库固定货架区工作的全过程。
从上图所示的固定货架的结构图中，我们可以看出，货架中的每一个货格都可以通过两个参
数变量来标识，即（X，Y）。其中的变量X表示为固定货架的列序号，我们规定最靠近
货架入库台的那列为第一列，之后的列依次排列。变量Y表示为层数，最底下的那一层层
数为1，向上依次增加。我们设定货架中的每一个货格的大小都是一样的，货格的宽度为L，
高度为H。
堆垛机在对本巷道内进行拣选操作的时候，从货架入货台附近的巷道入口（0，1）进入，依
照计算好的优化路径依次到达货位1，2，3，…m进行拣选操作，最后回到出发点。
要解决此问题需要进行一系列假设：
（1）堆垛机拣选货物的时间与拣选货物的顺序无关，就是说堆垛机到达不同
位置的货位后，放置或取出托盘和货箱所用的时间都是一样的，即表示为st。
（2）堆垛机在从一个货位向另一个货位移动的过程中，在水平和垂直方向上
可以互不干涉的同时运动，且启动和制动过程可以忽略不计，运动的速度都分
别有两种即低速（ylxlVV,）和高速（yhxhVV,）。
公式中的ijt表示堆垛机从货位i运动到货位j运动的时间，yxVV,为堆垛机的水平和垂直速
度，（iiYX,），（jjYX,）为货位坐标，而自动化立体仓库路径优化问题就是优化T，使
其达到最小。
问题求解：
编码方式我们选用十进制编码，因为这种编码方式简单、实用，易于进行遗传算法TSP问
题中的交叉、变异操作。
参考文献：
[1]郑欢.自动化立体仓库路径优化问题研究[D].吉林大学,2006.
[2]谢树新.自动化立体仓库拣选作业路径优化方法研究[D].苏州大学,2010.
qq：778961303，如有疑问请咨询
部分程序：
%Author:怡宝2号
%Use:基于遗传算法求解自动化立体仓库路径优化问题，交叉采用的是顺序交
叉方法；变异采用交换变异：随机选择串中的两点，交换其基因值。
%输入变量（可修改量）：
%NIND:种群大小
%t：待取货的位置（注意要写成N*2的一个数
组）
%MAXGEN:进化代数
%输出：
%result：取货的路径
%Remark：本人qq：778961303，如有疑问请咨询
clc
clearall
closeall
%%初始参数设置
NIND=20;
t=[];%待优化的取货点,t的第一行为取货的开始点/出发点
constpoint=14;%取货点数
vx=0.5;%x，y方向上的移动速度
vy=0.5;
L=2;%储物货架的宽度
H=2.5;%储物货架的高度
gen=1;%迭代的计数器
MAXGEN=100;%遗传算法最大的遗传代数
PC=0.9;%交叉概率
PM=0.1;%变异概率
GGAP=0.9;%代沟
initialpoint=[0,1];
%-----------------初始化种群-------------------%
fori=1:NIND
chrom(i,:)=randperm(constpoint);
end
%-----------------计算目标函数-------------------%
fori=1:NIND
temp=0;
j=2;
whilej<=constpoint
temp=temp+max(abs(t(chrom(i,j),1)-t(chrom(i,j-1),1))/vx,abs(t(chrom(i,j),2)-t(chrom(i,j-1),2))/vy)
;
j=j+1;
end
temp=temp+max(abs(t(chrom(i,1),1)-initialpoint(1))/vx,abs(t(chrom(i,1),2)-initialpoint(2))/vy);
fitness(i,:)=temp;
end
%迭代开始
whilegen
fitness=1./fitness;%因为要求的是最小的时间，所以适应度取为路径
的倒数
fitness=fitness./sum(fitness);%进行归一化操作
prob=cumsum(fitness);
selch=chrom(1:NIND*GGAP,:);
fori=1:2:NIND*GGAP%选择操作
%--------寻找父代---------
sita=rand();
forj=1:NIND
ifsita<=prob(j)
father=chrom(j,:);
break;
end
end
%--------寻找母代---------
sita=rand();
forj=1:NIND
ifsita<=prob(j)
mother=chrom(j,:);
break;
end
end
%----------交叉操作--------------%
%----------变异操作--------------%
%-----------------计算目标函数-------------------%
%------------------得到子代种群-----------------
tempfitness=tempfitness./sum(tempfitness);
temppro=cumsum(tempfitness);%归一化
sita=rand();
fork=1:size(tempchrom,1)
ifsita<=temppro(k)
selch(i,:)=tempchrom(k,:);
break;
end
end
sita=rand();
fork=1:size(tempchrom,1)
ifsita<=temppro(k)
selch(i+1,:)=tempchrom(k,:);
break;
end
end
end
%------------------计算子代的目标函数和适应度-----------------
fitness=1./fitness;
trace(gen)=min(fitness);%记录每一代最小的适应度值
gen=gen+1;
end
%绘制解得变化图
plot(trace)
gridon
xlabel('遗传代数')
ylabel('解得变化')
title('距离变化')
%最短的路径
index=find(fitness==min(fitness));
result=[];%最优种群
result=chrom(index(1),:);
display(['求解的最优路径为：',num2str(result)]);
disp(['最短路径的长度为：',num2str(min(trace))]);
%画出路径图
figure(2);
plot(initialpoint(1),initialpoint(2),'r-*');
text(initialpoint(1),initialpoint(2),['''出发点'])
holdon
fori=1:constpoint
plot(t(i,1),t(i,2),'-*');
text(t(i,1),t(i,2),[''num2str(i-1)])
holdon
end
gridon
title('待优化的货位');
figure(3)
plot(initialpoint(1,1),initialpoint(1,2),'b-*');
text(initialpoint(1,1),initialpoint(1,2),['''出发点'])
holdon
plot([initialpoint(1,1),initialpoint(1,2)],[t(result(1),1),t(result(1),2)],'r-');%
画出出发点到第一个点的路径
holdon
plot([t(result,1)],[t(result,2)],'r-*');
holdon
fori=1:constpoint
text(t(result(i),1),t(result(i),2),['''次序：'num2str(i)]);
holdon
end
gridon;结果：
