1、外卖配送中与普通路径优化的区别

（1）外卖配送中必须先取订单在进行配送，所以染色体是有序排列的

（2）两点间的距离并不代表十几的距离

（3）在进行交叉与变异时也只能运用特殊的方法

（4）如有载货限制顾客-1，商家+1进行计算

原始数据

（1）第一列0为原点，1-5为商家 6-10为顾客

（2）二三列为坐标

（3）四五列为时间窗的开始与结束

产生种群

5 2 3 4 10 1 8 9 7 6

如上，在产生种群时，商家1的订单对应客户6，以此类推，所以1必须在6的前面，2、3、4、5都是如此。

选择

选择采用锦标赛，适应度为距离的倒数

交叉与变异

采用保续的交叉法如下

变异

结果

gs为超过顾客最晚时间窗的订单个数，

w1为软时间窗违反的总时间

优化过程

优化结果，其中超过客户最晚时间窗的用三角在图中标了出来。

主程序如下

clearclcclose alltic%% 读取数据load('shuju');bl=0;%% 提取数据信息E=shuju(1,4); %初始点时间窗开始时间L=shuju(1,5); %初始点心时间窗结束时间zuobiao=shuju(:,2:3); %所有点的坐标x和yzuobiao=[zuobiao(:,1),-zuobiao(:,2)];customer=zuobiao(2: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]]dist=Distanse(zuobiao); %根据坐标的欧式距离矩阵% dist=load('matlab.mat');%D导入距离矩阵% dist=struct2cell(dist);% dist=cell2mat(dist);%% 遗传算法参数设置alpha=100000;%违反的容量约束的惩罚函数系数belta=0.4;%违反时间窗约束的惩罚函数系数belta2=1;chesu=100;%车速NIND=1000;%种群大小MAXGEN=50; %迭代次数Pc=0.9; %交叉概率Pm=0.05;%变异概率GGAP=0.9;%代沟(Generation gap)N=cusnum;%% 初始化种群Chrom=init(cusnum,NIND); %构造初始解%% 输出随机解的路线和总距离disp('初始种群中的一个随机值:')[VC,TD,violate_cus]=decode(Chrom(1,:),cusnum,a,b,L,dist,chesu,bl);% disp(['总距离：',num2str(TD)]);disp(['车辆行驶总距离：',num2str(TD)]);disp('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~')%% 优化gen=1;figure;hold on;box onxlim([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);%% 变异SelCh=Mutate(SelCh,Pm);%% 重插入子代的新种群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('-------------------------------------------------------------')% %% 画出最终路线图% ee=[];% ccc=0;% for i=1:cusnum%if i==1% ccc=(ccc+dist(1,bestVC(1)+1)/chesu);%ee(i,1)=ccc;%%else% ccc=ccc+dist((bestVC(i-1)+1),bestVC(i)+1)/chesu;% ee(i,1)=ccc;% end% end% eee=cumsum(ee);draw_Best(bestVC,zuobiao,b,bsv);gsw1w2

如需帮忙

完成代码下载链接