【VRP问题】基于模拟退火算法改进狼群算法求解带时间窗的车辆路径VRPTW问题附matlab代码

1 简介针对城市物流配送和交通运输中广泛存在的带时间窗车辆路径问题,为寻求最佳路径规划,应用惩罚函数,构建了以总运输成本最小为目标的数学模型.在车辆路径优化求解方面,根据问题具体特征设计了1种二维编码方式,并采用近邻初始化方式构建初始解从而提升寻优速率;随后,结合狼群算法觅食行为中的游走、召唤及围攻3种行为,重新定义其智能行为,设计了一种求解带时间窗车辆路径问题的狼群算法.由于原始狼群算法的召唤行为引入距离判定因子来增大种群搜索空间,但也增加了算法复杂性且易陷入局部最优,故本研究舍弃了距离判定因子,采用猛狼1次奔袭便进入围攻状态来降低算法复杂度,并在算法中进一步增强了种群间信息交互.最后,应用该狼群算法求解多个测试算例.结果表明:基于模拟退火赛算法优化狼群算法在求解带时间窗的车辆路径问题时是可行的、有效的。带时 间 窗 的 车 辆 路 径 问 题 ( vehicle routingproblem with time windowsVRPTW) 是在基本车辆路径问题 ( vehicle routing problemVRP) 的基础上 增加了客户接受配送服务的时间窗要求较 VRP 更 贴近实际配送情况。与 VRP 类似VRPTW 亦属于NP 难问题。由于问题规模较大时传统精确算法难以求出 VRPTW 的最优解因此国内外很多学者利用智能启发式算法来寻找该问题的满意解。常见的 求解 VRPTW 的智能优化算法包括: 蚁群算法、 遗传算法、粒子群算法、禁忌搜索算法 等。但是由于遗传算法与禁忌搜索算法的早 熟易收敛问题蚁群算法和粒子群算法的易陷入局 部最优缺陷故目前仍未找到求解性能具有明显优势的 VRPTW 求解算法。因此对 VRPTW 求解方法的研究仍属于运筹学、物流配送和交通运输工程等领域的研究重点和热点。 狼群算法 ( Wolf Pack AlgorithmWPA) 作为 一种新型智能启发式算法是对自然界中狼群分工 协作捕食行为的智能模拟是一种基于种群的随机 寻优算法。目前该算法已被成功应用于 TSP 问题、0 1 高维背包问题和多维连续优化等多种问题的求 解并取得了良好的效果。但是截至目前为止 尚未有文献将狼群算法应用于 VRPTW 的求解。 基于求解 TSP 的离散狼群算法结合带时间窗的车辆路径问题的具体特征提出了求解 VRPTW的狼群算法并与其他智能算法如蚁群算法、遗 传算 法 等 比 较不 仅 验 证 了 本 算 法 在 求 解VRPTW 问题上的有效性而且拓宽了狼群算法的应 用领域。2 部分代码clc;clearLocation[];Location(:,1)xlsread(Data.xlsx,sheet13,b2:b23);Location(:,2)xlsread(Data.xlsx,sheet13,c2:c23);TWxlsread(Data.xlsx,sheet13,e2:f23);qxlsread(Data.xlsx,sheet13,d2:d23);workTxlsread(Data.xlsx,sheet13,g2:g23);n1:size(Location,1)-1;Q10;PAIXU12;v_min35;v_mid40;v_max50;Ship300;Fuel_Cost3;Labor20;Dzeros(length(n)1);for i1:length(n)1for ji:length(n)1D(i,j)6371.004*acos(sind(90-Location(i,1))*sind(90-Location(j,1))*cosd(Location(i,2)-Location(j,2))cosd(90-Location(i,1))*cosd(90-Location(j,1)));endendDDD;TD/v_max;yuanbaocell(70,13);TIMEzeros(1,70);% for cunchu1:70popsize100;numWolf1;all_chromosome_cellcell(100,12);while numWolfpopsizen_nn;vehicle1;chromosome_cellcell(length(n),4);chromosome_cell{vehicle,1}0;chromosome_cell{vehicle,2}0;chromosome_cell{vehicle,3}0;chromosome_cell{vehicle,4}0;ArrivalWait_timezeros(2,1);chromosome_cell{vehicle,5}ArrivalWait_time;while ~isempty(n_n)Rrandi(length(n_n));customern_n(R);i1;while ivehicleif chromosome_cell{i,2}q(customer1)Qii1;if ivehiclevehiclevehicle1;chromosome_cell{vehicle,1}0;chromosome_cell{vehicle,2}0;chromosome_cell{vehicle,3}0;chromosome_cell{vehicle,4}0;chromosome_cell{vehicle,5}ArrivalWait_time;endelseif sum(chromosome_cell{i,5}(:,end))workT(chromosome_cell{i,1}(end)1)T(chromosome_cell{i,1}(end)1,customer1)TW(customer1,2)ii1;if ivehiclevehiclevehicle1;chromosome_cell{vehicle,1}0;chromosome_cell{vehicle,2}0;chromosome_cell{vehicle,3}0;chromosome_cell{vehicle,4}0;chromosome_cell{vehicle,5}ArrivalWait_time;endelseif sum(chromosome_cell{i,5}(:,end))workT(chromosome_cell{i,1}(end)1)T(chromosome_cell{i,1}(end)1,customer1)TW(customer1,1)chromosome_cell{i,5}(1,end1)sum(chromosome_cell{i,5}(:,end))workT(chromosome_cell{i,1}(end)1)T(chromosome_cell{i,1}(end)1,customer1);chromosome_cell{i,5}(2,end)TW(customer1,1)-chromosome_cell{i,5}(1,end);elsechromosome_cell{i,5}(1,end1)sum(chromosome_cell{i,5}(:,end))workT(chromosome_cell{i,1}(end)1)T(chromosome_cell{i,1}(end)1,customer1);chromosome_cell{i,5}(2,end)0;endchromosome_cell{i,1}(end1)customer;chromosome_cell{i,2}chromosome_cell{i,2}q(customer1);chromosome_cell{i,4}chromosome_cell{i,4}D(chromosome_cell{i,1}(end-1)1,chromosome_cell{i,1}(end)1);n_n(R)[];break;endendendTotal_fuelzeros(1,vehicle);for k1:vehicleSingle_fuel0;chromosome_cell{k,4}chromosome_cell{k,4}D(chromosome_cell{k,1}(end)1,1);chromosome_cell{k,3}sum(chromosome_cell{k,5}(:,end))workT(chromosome_cell{k,1}(end)1)T(chromosome_cell{k,1}(end)1,1);Singleton_genechromosome_cell{k,1};Singleton_weight0;for OIL1:numel(Singleton_gene)-1Singleton_weightSingleton_weightq(Singleton_gene(OIL)1);Q_Z(0.80.2*(Singleton_weight/Q))*0.174*450*((22/27)^3)*(D(Singleton_gene(OIL)1,Singleton_gene(OIL1)1)/22);Q_F0.174*450*((22/27)^3)*0.4*workT(Singleton_gene(OIL)1);Single_fuelSingle_fuelQ_ZQ_F;endSingle_fuelSingle_fuel(0.80.2*((Singleton_weightq(Singleton_gene(end)1))/Q))*0.174*450*((22/27)^3)*(D(Singleton_gene(end)1,1)/22)0.174*450*((22/27)^3)*0.4*workT(Singleton_gene(end)1);Total_fuel(k)Single_fuel;endall_chromosome_cell{numWolf,1}[chromosome_cell{:,1}];all_chromosome_cell{numWolf,1}(end1)0;all_chromosome_cell{numWolf,2}[chromosome_cell{:,2}];all_chromosome_cell{numWolf,3}[chromosome_cell{:,4}];all_chromosome_cell{numWolf,4}[chromosome_cell{:,5}];all_chromosome_cell{numWolf,5}[chromosome_cell{:,3}];all_chromosome_cell{numWolf,6}sum(cell2mat(chromosome_cell(:,4)));all_chromosome_cell{numWolf,7}vehicle;all_chromosome_cell{numWolf,10}Total_fuel;all_chromosome_cell{numWolf,11}sum(Total_fuel);all_chromosome_cell{numWolf,12}all_chromosome_cell{numWolf,7}*Shipsum(all_chromosome_cell{numWolf,5})*Laborall_chromosome_cell{numWolf,11}*Fuel_Cost;numWolfnumWolf1;endfor i1:popsizeSuDuzeros(1,length(all_chromosome_cell{i,1})-1);SuDu(:)v_max;all_chromosome_cell{i,8}SuDu;endall_chromosome_cellsortrows(all_chromosome_cell,12);BESTall_chromosome_cell(1,:);TanWolfall_chromosome_cell(1:popsize/2,:);D_GLrepmat(1/8,1,8);D_LPcumsum(D_GL);R_GLrepmat(0.2,1,5);R_LPcumsum(R_GL);DestroyWeight_matrix[zeros(2,8);D_GL];InsertWeight_matrix[zeros(2,5);R_GL];temperature500;beta0.98;nnum1;tab1;while temperature0.01TanWolf_CopyTanWolf;first_i1;TanWolf_Son{};SIMP{};SDEG{};while first_ilength(TanWolf)arandperm(size(TanWolf_Copy,1),1);TanWolf_RandTanWolf_Copy(a,:);TanWolf_Copy(a,:)[];second_i1;h3;while second_ih[c,b,Insert,TWolf_One,DestroyWeight_matrix,InsertWeight_matrix,POHUA,CHARU]ALNS_VRPTW_main(DestroyWeight_matrix,InsertWeight_matrix,TanWolf_Rand,n,D_LP,R_LP,Q,q,T,TW,workT,D,v_max);TWolf_One{12}TWolf_One{7}*Shipsum(TWolf_One{5})*LaborTWolf_One{11}*Fuel_Cost;%TanWolf_Son(h*(first_i-1)second_i,:)TWolf_One;second_isecond_i1;if TWolf_One{12}TanWolf_Rand{12}SIMP(size(SIMP,1)1,:) TWolf_One;if TWolf_One{12} BEST{12}tab0;Bubian1;BEST TWolf_One;DestroyWeight_matrix(2,POHUA)DestroyWeight_matrix(2,POHUA)6;%加分6InsertWeight_matrix(2,CHARU)InsertWeight_matrix(2,CHARU)6;elseDestroyWeight_matrix(2,POHUA)DestroyWeight_matrix(2,POHUA)1;%加分3InsertWeight_matrix(2,CHARU)InsertWeight_matrix(2,CHARU)1;endelse %模拟退火判断Num_randrand();if Num_rand exp(-(TWolf_One{12}-TanWolf_Rand{12})/temperature)TanWolf_Son(size(TanWolf_Son,1)1,:)TWolf_One;DestroyWeight_matrix(2,POHUA)DestroyWeight_matrix(2,POHUA)2;%加分3InsertWeight_matrix(2,CHARU)InsertWeight_matrix(2,CHARU)2;endendend%TanWolf_Copy(first_i,:) TWolf_One;%%%%%%if size(SIMP,1)~0SIMPsortrows(SIMP,12);TanWolf(first_i,:)SIMP(1,:);SIMP{};endif size(TanWolf_Son,1)3 size(TanWolf_Son,1)0SDEG[SDEG;TanWolf_Son];endfirst_ifirst_i1;TanWolf_Son{};nnumnnum1;if rem(nnum,500)0[DestroyWeight_matrix,D_LP]DestroyWeight_update(DestroyWeight_matrix);[InsertWeight_matrix,R_LP] InsertWeight_update( InsertWeight_matrix);endendtabtab1;if tab500breakendTanWolf_Son_H[TanWolf;SDEG];TanWolf_Son_Hsortrows(TanWolf_Son_H,12);if size(TanWolf_Son_H,1)120TanWolfTanWolf_Son_H(1:100,:);endtemperaturetemperature*0.98;endRBEST{1,1};%最优路径figure(3)sz100;% scatter(Location(:,1),Location(:,2),50);%客户位置hold on[n,nn] size(D);%节点个数for i2:nplot(Location(i,1),Location(i,2),ro,MarkerSize,5,MarkerEdgeColor,k,MarkerFaceColor,b);text(Location(i,1)-0.001,Location(i,2)0.005,[num2str(i-1)],Fontsize,10);hold onendhold onplot(Location(1,1),Location(1,2),p,MarkerSize,30,MarkerEdgeColor,k,MarkerFaceColor,y);hold on%发货中心ss0;costzeros(k,1);for j1:length(R)-1if R(j)0ssss1;endswitch sscase 1line([Location(R(j)1,1),Location(R(j1)1,1)],[Location(R(j)1,2),Location(R(j1)1,2)]);hold on%%画出车辆1的路程cost(ss,1) cost(ss,1) D(R(j)1,R(j1)1);%计算车辆1的路程case 2line([Location(R(j)1,1),Location(R(j1)1,1)],[Location(R(j)1,2),Location(R(j1)1,2)],Color,r);hold on%%画出车辆2的路程cost(ss,1) cost(ss,1) D(R(j)1,R(j1)1);%计算车辆2的路程case 3line([Location(R(j)1,1),Location(R(j1)1,1)],[Location(R(j)1,2),Location(R(j1)1,2)],Color,g);hold on %%画出车辆3的路程cost(ss,1) cost(ss,1) D(R(j)1,R(j1)1);%计算车辆3的路程case 4line([Location(R(j)1,1),Location(R(j1)1,1)],[Location(R(j)1,2),Location(R(j1)1,2)],Color,k);hold on %%画出车辆3的路程cost(ss,1) cost(ss,1) D(R(j)1,R(j1)1);%计算车辆3的路程case 5line([Location(R(j)1,1),Location(R(j1)1,1)],[Location(R(j)1,2),Location(R(j1)1,2)],Color,y);hold on %%画出车辆3的路程cost(ss,1) cost(ss,1) D(R(j)1,R(j1)1);%计算车辆3的路程case 6line([Location(R(j)1,1),Location(R(j1)1,1)],[Location(R(j)1,2),Location(R(j1)1,2)],Color,m);hold on %%画出车辆3的路程cost(ss,1) cost(ss,1) D(R(j)1,R(j1)1);%计算车辆3的路程case 7line([Location(R(j)1,1),Location(R(j1)1,1)],[Location(R(j)1,2),Location(R(j1)1,2)],Color,[1 0.6 0.3]);hold on %%画出车辆3的路程cost(ss,1) cost(ss,1) D(R(j)1,R(j1)1);%计算车辆3的路程case 8line([Location(R(j)1,1),Location(R(j1)1,1)],[Location(R(j)1,2),Location(R(j1)1,2)],Color,[0.5 0.5 0.5]);hold on %%画出车辆3的路程cost(ss,1) cost(ss,1) D(R(j)1,R(j1)1);%计算车辆3的路程case 9line([Location(R(j)1,1),Location(R(j1)1,1)],[Location(R(j)1,2),Location(R(j1)1,2)],Color,[0.6 0.4 0.7]);hold on %%画出车辆3的路程cost(ss,1) cost(ss,1) D(R(j)1,R(j1)1);%计算车辆3的路程case 10line([Location(R(j)1,1),Location(R(j1)1,1)],[Location(R(j)1,2),Location(R(j1)1,2)],Color,[0.8 0.4 0.7]);hold on %%画出车辆3的路程cost(ss,1) cost(ss,1) D(R(j)1,R(j1)1);%计算车辆3的路程case 11line([Location(R(j)1,1),Location(R(j1)1,1)],[Location(R(j)1,2),Location(R(j1)1,2)],Color,[0.6 0.6 0.7]);hold on %%画出车辆3的路程cost(ss,1) cost(ss,1) D(R(j)1,R(j1)1);%计算车辆3的路程case 12line([Location(R(j)1,1),Location(R(j1)1,1)],[Location(R(j)1,2),Location(R(j1)1,2)],Color,[0.6 0.4 0.7]);hold on %%画出车辆3的路程cost(ss,1) cost(ss,1) D(R(j)1,R(j1)1);%计算车辆3的路程otherwiseline([Location(R(j)1,1),Location(R(j1)1,1)],[Location(R(j)1,2),Location(R(j1)1,2)],Color,c);hold on %%画出车辆4的路程cost(ss,1) cost(ss,1) D(R(j)1,R(j1)1);%计算车辆4的路程endendminvalue1sum(cost);xlabel(横坐标);ylabel(纵坐标)3 仿真结果4 参考文献[1]叶勇, and 张惠珍. 求解带时间窗车辆路径问题的狼群算法. 公路交通科技 34.10(2017):8.博主简介擅长智能优化算法、神经网络预测、信号处理、元胞自动机、图像处理、路径规划、无人机等多种领域的Matlab仿真相关matlab代码问题可私信交流。部分理论引用网络文献若有侵权联系博主删除。