多种群遗传算法处理基于电动汽车的带时间窗的路径优化问题（VRPTW）

%% 主函数 % 结合电动汽车的特点构建了以总配送成本最小为目标的带有惩罚函数的基于电动汽车的VRPTW模型 % 采用多种群遗传算法，设计了染色体编码方式和遗传算子。 %约束条件包括电动汽车续驶里程、电动汽车额定载重量、物流配送中心电动汽车的数量、配送任务以配送中心为起点和终点、时间窗。 %初始化 clear all; close all; clc; %% 参数设置 k=3; % 3辆车 m=25; % 25个客户点 ch=2; % 2个充电站 % 各客户点需求量，其中配送中心/充电站需求量为0，其中q(1)为配送中心，q(27)、q(28)为充电站，以此类推 q = [0 0.2 0.3 0.3 0.3 0.3 0.5 0.8 0.4 0.5 0.7 0.7 0.6 0.2 0.2 0.4 0.1 0.1 0.2 0.5 0.2 0.7 0.2 0.7 0.1 0.5 0 0]; % 配送中心、充电站和客户点的坐标位置，配送中心在第1位，充电站点在最后 X=[ 56 56 66 78 56 27 88 72 88 32 24 48 40 48 32 80 16 69 88 96 48 96 32 104 80 56 48 40 24 16 48 8 16 32 8 48 32 64 24 96 72 104 72 32 72 16 88 8 104 56 104 32 83 45 32 40]; % 时间参数 % 客户要求到货的时间始点(最早点)，充电站0 ET=[0 1 2 7 5 3 0 7 1 4 1 3 0 2 2 7 6 7 1 1 8 6 7 6 4 0 0]; % 客户要求到货的时间终点(最晚点)，充电站最晚100 LT=[1 2 4 8 6 5 2 8 3 5 2 4 1 4 3 8 8 9 3 3 10 10 8 7 6 1000 1000]; % 客户点的停留时间，充电站停留时间为0.4 TT=[0.2 0.3 0.3 0.3 0.3 0.5 0.8 0.4 0.5 0.7 0.7 0.6 0.2 0.2 0.4 0.1 0.1 0.2 0.5 0.2 0.7 0.2 0.7 0.1 0.5 0.4 0.4]; % 成本参数 Ck=10; % 第k辆车运行单位距离的费用(运输成本) C1=20; % 车辆在任务点处等待单位时间的机会成本(早到惩罚) C2=30; % 车辆在要求时间之后到达单位时间所处的惩罚值(晚到惩罚) % 汽车参数 Dis = 160; % 续驶里程 Qk = 5; % 车辆额定载重量 speed = 40; % 汽车的行驶速度 % 遗传算法参数 NIND = 200; % 种群大小，一般种群大小在100到200之间比较好 MP=50; %种群数目 gen=0; %初始遗传代数 gen0=0; %初始保持代数 MAXGEN=10; %最优个体最少保持代数 maxFit=0; %最优值 pc=0.85+(0.95-0.85)*rand(MP,1); %在【0.85,0.95】范围i内随机产生交叉概率 pm=0.08+(0.15-0.08)*rand(MP,1); %在【0.08,0.15】范围内随机产生变异概率 %% 模型求解 D = GA_Distance(X);%各个点之间的距离 for i=1:MP Chrom{i}=GA_chushihua(NIND,m,ch,k,q,Qk);%初始化种群 end for i=1:MP ObjV{i} = GA_fitness(Chrom{i},m,Ck,C1,C2,LT,ET,Qk,q,k,Dis,speed,ch,TT,D);%计算各初始种群个体的目标函数值 end MaxObjV=zeros(MP,1); %记录精华种群 MaxChrom=zeros(MP,m+ch+k+1); %记录精华种群的编码 while gen0<=MAXGEN gen=gen+1; %遗传代数加1 for i=1:MP scro{i} = GA_cro(Chrom{i},m,pc(i),Ck,C1,C2,LT,ET,Qk,q,k,Dis,speed,ch,TT,D);%交叉操作 smut{i} = GA_mut(scro{i},m,k,Ck,C1,C2,LT,ET,Qk,q,Dis,speed,ch,TT,pm(i),D);%变异操作 [Chrom{i},s_gen{i},ObjV{i}] = GA_reins(Chrom{i},smut{i},m,Ck,C1,C2,LT,ET,Qk,q,k,Dis,speed,ch,TT,D,NIND);%记录并更新全局最优解 end [Chrom,ObjV]=immigrant(Chrom,ObjV); % 移民操作 [MaxObjV,MaxChrom]=EliteInduvidual(Chrom,ObjV,MaxObjV,MaxChrom); % 人工选择精华种群 best_fit(gen) = max(MaxObjV); if best_fit(gen)>maxFit %判断当前优化值是否与前一次优化值相同 maxFit = best_fit(gen); %更新最优值 gen0=0; else gen0=gen0+1; %最优值保持次数加1 end end %% 模型输出 [Fit,I]=max(MaxObjV); %找出精华种群中最优的个体 best_path = MaxChrom(I,:); %输出最优解的路线和最优目标函数值 disp('最优解：') disp(best_path) %最优路线 disp(['目标函数值：',num2str(1/Fit)]) %% 绘图 % 遗传图 figure; hold on; box on; %% 进化过程图 plot(1:gen,best_fit); xlabel('进化代数') ylabel('最优解变化') title('MPGA进化过程') %配送路径图 figure plot(X(1,1),X(1,2),'o','markersize',10) % 配送中心 hold on plot(X(2:(m+1),1),X(2:(m+1),2),'.','markersize',10) % 需求点 hold on plot(X((m+2):(m+3),1),X((m+2):(m+3),2),'^','markersize',10) % 充电站 for i = 1:m+k+ch line([X(best_path(i)+1,1),X(best_path(i+1)+1,1)],[X(best_path(i)+1,2),X(best_path(i+1)+1,2)]); end xlabel('横坐标X') ylabel('纵坐标Y')