【路径规划】基于遗传算法实现外卖订单动态变换模型求解附matlab代码.zip

clear clc close all tic %% 读取数据 load('shuju7'); bl=0; %% 提取数据信息 E=shuju(1,4); %初始点时间窗开始时间 L=shuju(1,5); %初始点心时间窗结束时间 zuobiao=shuju(1:end-2,2:3); %所有点的坐标x和y zb=shuju(1:end,2:3); dtzb=shuju(end-1:end,2:3); zuobiao=[zuobiao(:,1),-zuobiao(:,2)]; zb=[zb(:,1),-zb(:,2)]; customer=zuobiao(2:end,:); %顾客坐标 dtcustomer=zuobiao(end-1:end,:); cusnum=size(customer,1); %顾客数 v_num=1; %车辆数 a=shuju(2:end,4); %顾客时间窗开始时间[a[i],b[i]] b=shuju(2:end,5); %顾客时间窗结束时间[a[i],b[i]] F=shuju(2:end,1); % dist=Distanse(zb); %根据坐标的欧式距离矩阵 dist=load('shiji7.mat');%D导入距离矩阵 dist=struct2cell(dist); dist=cell2mat(dist); %% 遗传算法参数设置 chesu=300;%车速 alpha=100000; %违反的容量约束的惩罚函数系数 belta=chesu/1000;%违反时间窗约束的惩罚函数系数 belta2=1; NIND=100; %种群大小 MAXGEN=100; %迭代次数 Pc=0.9; %交叉概率 Pm=0.05; %变异概率 GGAP=0.9; %代沟(Generation gap) N=cusnum; %% 初始化种群 FF=F(1:end-2,:); [s,g,sj,gk,Chrom]=init(cusnum,NIND,FF); %构造初始解 %% 输出随机解的路线和总距离 disp('初始种群中的一个随机值:') [VC,TD,violate_cus]=decode(Chrom(1,:),cusnum,a,b,L,dist,chesu,bl); % disp(['总距离：',num2str(TD)]); disp(['车辆行驶总距离：',num2str(TD)]); disp('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~') %% 优化 gen=1; subplot(2,2,1); hold on;box on xlim([0,MAXGEN]) title('优化过程') xlabel('代数') ylabel('最优值') [ObjV,bsv,gs,w1,w2]=calObj(Chrom,cusnum,a,b,L,dist,alpha,belta,belta2,chesu,bl); %计算种群目标函数值 preObjV=min(ObjV); %% while gen<=MAXGEN %% 计算适应度 [ObjV,bsv,gs,w1,w2]=calObj(Chrom,cusnum,a,b,L,dist,alpha,belta,belta2,chesu,bl); %计算种群目标函数值 line([gen-1,gen],[preObjV,min(ObjV)]);pause(0.0001)%画图 最优函数 preObjV=min(ObjV); FitnV=Fitness(ObjV); %% 选择 SelCh=Select(Chrom,FitnV,GGAP); %% OX交叉操作 SelCh=Recombin(SelCh,Pc,s,g,sj,gk); %% 变异 SelCh=Mutate(SelCh,Pm,s,g,sj,gk); %% 重插入子代的新种群 Chrom=Reins(Chrom,SelCh,ObjV); %% 打印当前最优解 [ObjV,bsv,gs,w1,w2]=calObj(Chrom,cusnum,a,b,L,dist,alpha,belta,belta2,chesu,bl); %计算种群目标函数值 [minObjV,minInd]=min(ObjV); disp(['第',num2str(gen),'代最优解:']) [bestVC,bestTD,best_viocus]=decode(Chrom(minInd(1),:),cusnum,a,b,L,dist,chesu,bl); disp(['车辆行驶总距离：',num2str(bestTD)]); fprintf('\n') %% 更新迭代次数 gen=gen+1 ; end %% 画出最优解的路线图 [ObjV,bsv,gs,w1,w2]=calObj(Chrom,cusnum,a,b,L,dist,alpha,belta,belta2,chesu,bl); %计算种群目标函数值 [minObjV,minInd]=min(ObjV); %% 输出最优解的路线和总距离 disp('最优解:') bestChrom=Chrom(minInd(1),:); [bestVC,bestTD,best_viocus]=decode(bestChrom,cusnum,a,b,L,dist,chesu,bl); disp(['车辆行驶总距离：',num2str(bestTD)]); disp('-------------------------------------------------------------') subplot(2,2,2) draw_Best(bestVC,zuobiao,b,bsv,gk,sj,cusnum,F); gs w1 w2 % save % toc~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ % pause %% jdsj=10; %%% 动态开始时间点 chesu=350; sy1=[]; for i=1:cusnum if jdsj<bsv(1,i) jqsj=bsv(i); csd=bestVC(i); sy1=bestVC(i:end); break end end sy=sy1; % dtc=find(mod(bestVC,2)==0); % sy=bestVC(dtc(3):end); sygs=[sy]; %动态变化后待配送点 cus=size(sygs,2)-1; b(1:end-2)=max(b(1:end-2)-jqsj,0); %动态变化后顾客时间窗变化 a(1:end-2)=max(a(1:end-2)-jqsj,0); %动态变化后商家时间窗变化 disp(['动态配送起点为',num2str(sygs(1))]) %% 初始化种群 [dtgk,dtsj,dts,dtg,CHrom]=init1(cus,NIND,sygs,csd); %% 动态优化 [VC,TD,violate_cus]=decode1(CHrom(1,:),cus,a,b,L,dist,chesu,bl,sygs); %% 优化 gen=1; subplot(2,2,3); hold on;box on xlim([0,MAXGEN]) title('优化过程') xlabel('代数') ylabel('最优值') [ObjVv,bsv1,gs1,w1,w2]=calObj1(CHrom,cus,a,b,L,dist,alpha,belta,belta2,chesu,bl,sygs); %计算种群目标函数值 preObjV=min(ObjVv); while gen<=MAXGEN %% 计算适应度 [ObjVv,bsv1,gs1,w1,w2]=calObj1(CHrom,cus,a,b,L,dist,alpha,belta,belta2,chesu,bl,sygs); %计算种群目标函数值 line([gen-1,gen],[preObjV,min(ObjVv)]);pause(0.0001)%画图 最优函数 preObjV=min(ObjVv); FitnV=Fitness(ObjVv); %% 选择 SelCh1=Select(CHrom,FitnV,GGAP); %% OX交叉操作 % dtsj1=dtsj; % if size(dtsj)>1 % for i=1:dts % while dtsj(i)==bestVC(csd); % dtsj1(i)=[]; % break % end % end % end SelCh2=Recombin1(SelCh1,Pc,dts,dtg,dtsj,dtgk,csd); %% 变异 SelCh3=Mutate(SelCh2,Pm,dts,dtg,dtsj,dtgk); %% 重插入子代的新种群 CHrom=Reins(CHrom,SelCh3,ObjVv); disp(['动态第',num2str(gen),'代最优解:']) [bestVCC,bestTD,best_viocuss]=decode1(CHrom(minInd(1),:),cus,a,b,L,dist,chesu,bl,sygs); disp(['车辆行驶总距离：',num2str(bestTD)]); fprintf('\n') %% 更新迭代次数 gen=gen+1 ; end %% [ObjVv,bsv1,gs1,w1,w2]=calObj1(CHrom,cus,a,b,L,dist,alpha,belta,belta2,chesu,bl,sygs); %计算种群目标函数值 [minObjV,minInd]=min(ObjVv); % %% 输出最优解的路线和总距离 % disp('最优解:') % bestChrom=Chrom(minInd(1),:); % [bestVC,bestTD,best_viocus]=decode1(bestChrom,cusnum,a,b,L,dist,chesu,bl,sygs); % disp(['车辆行驶总距离：',num2str(bestTD)]); % disp('-------------------------------------------------------------') %% % draw_Best1(bestVCC,zb,b,bsv,dtgk,dtsj,cus,bestVCC,sygs); if gs1>0 disp(['配送距离较远，不建议接单']); draw_Best1(bestVCC,zb,b,bsv,dtgk,dtsj,cus,bestVCC,sygs); else disp(['重新为您规划路线']); draw_Best1(bestVCC,zb,b,bsv,dtgk,dtsj,cus,bestVCC,sygs); end