【路径规划】基于遗传算法求解带时间窗车辆路径规划问题VRPTWmatlab源码1 简介有时间窗的车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW)因为其有重要的现实意义而备受关注.其时间窗即为客户接受服务的时间范围,该问题是运筹学和组合优化领域中的著名NP问题,是解决物流配送效率的关键,传统寻优方法效率低,耗时长,找不到满意解,往往导致物流成本过高.为了提高寻优效率,降低物流运送成本,基本遗传算法求解VRPTW问题.首先建立数学模型,然后基于大规模邻域搜索算法(LNS)生成遗传算法初始解,最后利用遗传算法在初始种群中找到最优解.计算结果表明,遗传算法可以更好求解车辆路径问题,有效降低物流成本.2 部分代码% % clear clc close all tic %% 用importdata这个函数来读取文件 % filename.\evrptw_instances\c101_21.txt; c101importdata(data.txt); cap200; %车辆最大装载量 %% 提取数据信息 Ec101(1,5); %配送中心时间窗开始时间 Lc101(1,6); %配送中心时间窗结束时间 vertexsc101(:,2:3); %所有点的坐标x和y customervertexs(2:end,:); %顾客坐标 cusnumsize(customer,1); %顾客数 v_num6; %车辆最多使用数目 demandsc101(2:end,4); %需求量 ac101(2:end,5); %顾客时间窗开始时间[a[i],b[i]] bc101(2:end,6); %顾客时间窗结束时间[a[i],b[i]] sc101(2:end,7); %客户点的服务时间 hpdist(vertexs); distsquareform(h); %距离矩阵满足三角关系暂用距离表示花费c[i][j]dist[i][j] %% 遗传算法参数设置 alpha10; %违反的容量约束的惩罚函数系数 belta100; %违反时间窗约束的惩罚函数系数 NIND100; %种群大小 MAXGEN100; %迭代次数 Pc0.9; %交叉概率 Pm0.05; %变异概率 GGAP0.9; %代沟(Generation gap) Ncusnumv_num-1; %染色体长度顾客数目车辆最多使用数目-1 %% 初始化种群 init_vcinit(cusnum,a,demands,cap); %构造初始解 ChromInitPopCW(NIND,N,cusnum,init_vc); %% 输出随机解的路线和总距离 disp(初始种群中的一个随机值:) [VC,NV,TD,violate_num,violate_cus]decode(Chrom(1,:),cusnum,cap,demands,a,b,L,s,dist); % disp([总距离,num2str(TD)]); disp([车辆使用数目,num2str(NV),车辆行驶总距离,num2str(TD),违反约束路径数目,num2str(violate_num),违反约束顾客数目,num2str(violate_cus)]); disp(~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~) %% 优化 gen1; gcffigure(1); hold on;box on xlim([0,MAXGEN]) title(优化过程) xlabel(代数) ylabel(最优值) img gcf; %获取当前画图的句柄 print(img, -dpng, -r600, ./img.png) %即可得到对应格式和期望dpi的图像 ObjVcalObj(Chrom,cusnum,cap,demands,a,b,L,s,dist,alpha,belta); %计算种群目标函数值 preObjVmin(ObjV); while genMAXGEN %% 计算适应度 ObjVcalObj(Chrom,cusnum,cap,demands,a,b,L,s,dist,alpha,belta); %计算种群目标函数值 line([gen-1,gen],[preObjV,min(ObjV)]);pause(0.0001) preObjVmin(ObjV); FitnVFitness(ObjV); %% 选择 SelChSelect(Chrom,FitnV,GGAP); %% OX交叉操作 SelChRecombin(SelCh,Pc); %% 变异 SelChMutate(SelCh,Pm); %% 局部搜索操作 SelChLocalSearch(SelCh,cusnum,cap,demands,a,b,L,s,dist,alpha,belta); %% 重插入子代的新种群 ChromReins(Chrom,SelCh,ObjV); %% 删除种群中重复个体并补齐删除的个体 Chromdeal_Repeat(Chrom); %% 打印当前最优解 ObjVcalObj(Chrom,cusnum,cap,demands,a,b,L,s,dist,alpha,belta); %计算种群目标函数值 [minObjV,minInd]min(ObjV); disp([第,num2str(gen),代最优解:]) [bestVC,bestNV,bestTD,best_vionum,best_viocus]decode(Chrom(minInd(1),:),cusnum,cap,demands,a,b,L,s,dist); disp([车辆使用数目,num2str(bestNV),车辆行驶总距离,num2str(bestTD),违反约束路径数目,num2str(best_vionum),违反约束顾客数目,num2str(best_viocus)]); fprintf(\n) %% 更新迭代次数 gengen1 ; end %% 画出最优解的路线图 ObjVcalObj(Chrom,cusnum,cap,demands,a,b,L,s,dist,alpha,belta); %计算种群目标函数值 [minObjV,minInd]min(ObjV); %% 输出最优解的路线和总距离 disp(最优解:) bestChromChrom(minInd(1),:); [bestVC,bestNV,bestTD,best_vionum,best_viocus]decode(bestChrom,cusnum,cap,demands,a,b,L,s,dist); disp([车辆使用数目,num2str(bestNV),车辆行驶总距离,num2str(bestTD),违反约束路径数目,num2str(best_vionum),违反约束顾客数目,num2str(best_viocus)]); disp(-------------------------------------------------------------) %% 判断最优解是否满足时间窗约束和载重量约束0表示违反约束1表示满足全部约束 flagJudge(bestVC,cap,demands,a,b,L,s,dist); %% 检查最优解中是否存在元素丢失的情况丢失元素如果没有则为空 DELJudge_Del(bestVC); %% 画出最终路线图 draw_Best(bestVC,vertexs); img gcf; %获取当前画图的句柄 print(img, -dpng, -r600, ./img2.png) %即可得到对应格式和期望dpi的图像 save c101.mat toc3 仿真结果4 参考文献[1]张露. (2020). 基于改进遗传算法求解带时间窗车辆路径规划问题. 中国物流与采购(14).博主简介擅长智能优化算法、神经网络预测、信号处理、元胞自动机、图像处理、路径规划、无人机等多种领域的Matlab仿真相关matlab代码问题可私信交流。部分理论引用网络文献若有侵权联系博主删除。