MDVRP1_测试可用_MDVRP_cast2ka_遗传算法_matlabMDVRP

%遗传算法 VRP 问题 Matlab实现 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %tic%计时器 clear; clc %W=80; %每辆车的载重量 %Citynum=50; %客户数量 %Stornum=4;%仓库个数 %C %%第二三列 客户坐标，第四列 客户需求 51,52,53,54为四个仓库 %load('p01-n50-S4-w80.mat'); %载入测试数据，n客户服务点数，S仓库个数,w车辆载重量 %load('p02-n50-S4-w160.mat'); %load('p04-n100-S2-w100.mat'); %load('p05-n100-S2-w200.mat'); load('p06-n100-S3-w100.mat'); %load('p12-n80-S2-w60.mat'); % load('ppp-n30-s3-w-60.mat') %load('ppp-n25-s3-w-50.mat') w=[];%存储每代的最短总路径 G=100;%种群大小 v1=60; v2=300; [dislist,Clist]=vrp(C);%dislist为距离矩阵 ，Clist为点坐标矩阵及客户需 L=[];%存每个种群的回路长度 for i=1:G Parent(i,:)=randperm(Citynum);%随机产生路径 L(i,1)=curlist(Citynum,Clist(:,4),W,Parent(i,:),Stornum,dislist); end Pc=0.8;%交叉比率 Pm=0.3;%变异比率 species=Parent;%种群 children=[];%子代 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% disp('正在运行，时间比较长，请稍等.........') g=50; for generation=1:g %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% tic fprintf('\n正在进行第%d次迭代，共%d次..........',generation,g); Parent=species;%子代变成父代 children=[];%子代 Lp=L; %选择交叉父代 [n m]=size(Parent); %交叉，代处理 for i=1:n for j=i:n if rand<Pc crossover end end end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% [n m]=size(Parent); for i=1:n if rand<Pm parent=Parent(i,:);%变异个体 X=floor(rand*Citynum)+1; Y=floor(rand*Citynum)+1; Z=parent(X); parent(X)=parent(Y); parent(Y)=Z; %基因交换变异 children=[children;parent]; end end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %计算子代适应值(即路径长度) (这块用时比较长) [m n]=size(children); Lc=zeros(m,1);%子代适应值 for i=1:m Lc(i,1)=curlist(Citynum,Clist(:,4),W,children(i,:),Stornum,dislist); end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %淘汰子代 剩余前G个最优解 [m n]=size(children); if(m>G) [m n]=sort(Lc); children=children(n(1:G),:); Lc=Lc(n(1:G)); end %淘汰种群 species=[children;Parent]; L=[Lc;Lp]; [m n]=sort(L); species=species(n(1:G),:); %更新世代 L=L(n(1:G)); %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %加入Opt优化 %分配仓库进行opt temp=initialStor(Citynum,Clist(:,4),W,species(1,:),Stornum,dislist);%存储分配仓库后的结果【52 14 5 52 53 6 9 8 53......】 Rbest=temp; L_best=L(1); [m n]=size(temp); start=1; car=[];%存放opt优化后的结果 i=2; while (i<n+1) if (temp(i)>Citynum) cur=[]; cur=Opt(i-start,[1:i-start,1:i-start],dislist,temp(start:i-1),Citynum); car=[car,[cur,cur(1)]]; start=i+1; i=i+2; else i=i+1; end end L1=CalDist(dislist,car,Citynum);%计算进行优化后的回路长度 if( L1<L(1)) fprintf('Opt优化有效! %f --> %f',L(1),L1); Rbest=car; car(find(car>Citynum))=[];%去掉编码中的仓库，再加入父代 species=[species;car]; L=[L;L1]; L_best=L1; end L_best w=[w,L_best]; toc %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% end %% Rbest%最优线路 L_best%最优解 %%画图 plot(1:g,(w(1:g)/v1+sum(Clist(:,4))/v2),'-*') hold on; xlabel('generation'); ylabel('mintime'); [m n]=size(Rbest); start=1; temp=[]; i=2; while(i<=n) if(Rbest(i)>Citynum) temp=Rbest(start:i); figure(2);plot(Clist(temp,2),Clist(temp,3),'-*') xlabel('x');ylabel('y'); hold on; start=i+1; i=i+2; else i=i+1; end end plot(Clist(Citynum+1:Citynum+Stornum,2),Clist(Citynum+1:Citynum+Stornum,3),'or') %toc