【路径规划】基于改进的智能水滴算法求解送取货且带时间窗的车辆路径与调度优化问题matlab代码

1 简介

有时间窗的车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW)因为其有重要的现实意义而备受关注.其时间窗即为客户接受服务的时间范围,该问题是运筹学和组合优化领域中的著名NP问题,是解决物流配送效率的关键,传统寻优方法效率低,耗时长,找不到满意解,往往导致物流成本过高.为了提高寻优效率,降低物流运送成本,对基本遗传算法改进求解VRPTW问题.首先建立数学模型,然后基于变邻域搜索算法(VNS)生成水滴算法初始解,最后利用混合水滴算法在初始种群中找到最优解.计算结果表明,改进遗传算法可以更好求解车辆路径问题,有效降低物流成本.

2 部分代码

clear all; clc; format short g; global D; global q; global q1; global ss; global E; global L; global ELL; % test=xlsread('test.xlsx',1); % % position=test(:,2:3); % data=[ % 100 100 0 0 0 40 % 60 100 10 0.2 0 3 % 20 110 15 0.3 0 4 % 160 150 21 0.3 1 6 % 160 110 16 0.4 0 4 % 30 20 25 0.3 1 4 % 100 60 22 0.2 0 6 % 100 170 15 0.1 0 5 % 30 10 12 0.4 0 6 % 60 50 15 0.3 1 7 % 160 160 20 0.2 0 6 % 50 140 23 0.3 0 6]; position=[18.70 15.29 16.47 8.45 20.07 10.14 19.39 13.37 25.27 14.24 22.00 10.04 25.47 17.02 15.79 15.10 16.60 12.38 14.05 18.12 17.53 17.38 23.52 13.45 19.41 18.13 22.11 12.51 11.25 11.04 14.17 9.76 24.00 19.89 12.21 14.50]; % 配送中心及各个需求点之间的距离矩阵D D=squareform(pdist(position(:,1:2),'euclidean')); % 车辆的单位行驶成本: h % 动用每辆车的固定成本：R. % 车辆的行驶速度v; % 车辆的最大装载量 Qmax。 h=1;R=10;v=1;Qmax=200;epsilon=0.001; R0=2;R1=0.8; % 车辆在配送中心及各个需求点之间行驶的时间矩阵 T T=D/v; % 最大迭代次数 Iter=30; % 水滴个数N N=size(position,1); % 速度更新参数： av=1;bv=0.01;cv=1; % 泥土量更新参数： as=1;bs=0.01;cs=1; % 局部泥土更新权系数 alpha=0.9; % 全局泥土更新权系数 beta=0.9; % 任意两点间的初始泥土量 Initsoil Initsoil=1000; % 初始泥土量矩阵W ??? W=ones(N)*1000; % 每个水滴的初始速度InitVel； % InitVel=100; InitVel=randperm(100,1); % 全局最优目标函数值 TotalZ=1000000; % 全局最优路径 TotalRoute=[]; % 主程序 t=0; WaterDrop(1,N)=struct('SW',[],... % 水滴对应的初始泥土量矩阵 'Source',[],... % 水滴的出发点为1; 即配送中心 'Target',[],... % 'VisitNode',[],... % 已访问过的点序列 (访问路径) 'UnvisitNode',[],... % 未访问过的点的集合 'Vel',[],... % 水滴的初始速度 'Soil',[],... % 水滴携带的初始泥土量 'Q',[],... % 水滴出发时的装载量 'S',[],... % 水滴到达source(k)点的时刻 'ZZ',[],... %水滴对应的目标函数初始值 'FK',[]); % 从source(k)出发可以去的下一个需求点的集合 FV % q=test(:,4); % 每个需求点的需求量 % q1=TestData(:,5); q=[0 6 5 11 6 3 8 5 6 4 5 7 6 10 9 4 7 8 ]'; % q1=[0 3.6 24.63.62.44.83 3.6 2.4 34.23.64 5.4 2.6 2.4 3]'; % ss=test(:,7); % 每个需求点的服务时间 ss=[0 1.8 1.0 2.3 1.8 1.2 2.4 1.5 1.8 1.2 1.5 2.1 1.8 2.0 2.7 1.3 1.2 1.5]'; E=[0 5.0 4 1 2.0 5 2 1 3 1 2 2.0 2 3 2 3 2 1]'; L=[40 20 15 20 20 15 18 24 27 20 16 20 10 25 28 24.0 20 23]'; % % E=test(:,5); % 每个需求点的时间窗下限 % L=test(:,6); % 每个需求点的时间窗上限 ELL=L-E; % EP=test(:,8); % LP=test(:,9); I=1:N; while t < Iter clc fprintf('第%d次进化\n',t+1) ; % 设置初始动态变量： % 本次迭代的最优目标函数值 Z=1000000; % 本次迭代的最优路径 Route=[]; for k=1:N WaterDrop(k).SW=W; WaterDrop(k).Source=1; WaterDrop(k).VisitNode=[1]; WaterDrop(k).UnvisitNode=I; WaterDrop(k).Vel= InitVel; % 水滴携带的初始泥土量 WaterDrop(k).Soil=0; % 水滴出发时的装载量 WaterDrop(k).Q(WaterDrop(k).Source)=0; % 水滴到达source(k)点的时刻； WaterDrop(k).S(WaterDrop(k).Source)=0; % 第k个水滴对应的目标函数初始值 WaterDrop(k).ZZ=0; end for k=1:N while WaterDrop(k).Source~=1 || ~isequal(WaterDrop(k).UnvisitNode,[1]) WaterDrop(k).FK=[]; if WaterDrop(k).Source==1 alt=2; else alt=1; end for i=alt:length(WaterDrop(k).UnvisitNode) WaterDrop(k).Q(WaterDrop(k).UnvisitNode(i))=WaterDrop(k).Q(WaterDrop(k).Source)+q(WaterDrop(k).UnvisitNode(i)); % 判断i点的载重量是否小于车辆最大载重且到达i点的时间是否在i点所要求的时间窗内 if WaterDrop(k).Q(WaterDrop(k).UnvisitNode(i))<Qmax; WaterDrop(k).FK=[WaterDrop(k).FK,WaterDrop(k).UnvisitNode(i)]; end end % for i=alt:N % if ismember(i,WaterDrop(k).UnvisitNode) % % if sum(ismember(WaterDrop(k).UnvisitNode,i)) % WaterDrop(k).Q(i)=WaterDrop(k).Q(WaterDrop(k).Source)+q(i); % WaterDrop(k).S(i)=WaterDrop(k).S(WaterDrop(k).Source)+ss(WaterDrop(k).Source)+T(WaterDrop(k).Source,i); % % 判断i点的载重量是否小于车辆最大载重且到达i点的时间是否在i点所要求的时间窗内 % if WaterDrop(k).Q(i)<Qmax && WaterDrop(k).S(i)>=E(i) && WaterDrop(k).S(i)<=L(i) % WaterDrop(k).FK=[WaterDrop(k).FK,i]; % end % end % end if isempty(WaterDrop(k).FK) WaterDrop(k).Target=1; else % 计算去下一个可以服务的需求点的概率 % 判断从source(k)到下一个可以服务的需求点的路径上泥土量的最小值是否小于0 Minsoil=0; for u=1:length(WaterDrop(k).FK) if WaterDrop(k).SW(WaterDrop(k).Source,WaterDrop(k).FK(u))<Minsoil Minsoil=WaterDrop(k).SW(WaterDrop(k).Source,WaterDrop(k).FK(u)); end end % 求下一个可以服务需求点对应的函数f之和（可以增加改进，调整节点选择概率） SumF=0; for u=1:length(WaterDrop(k).FK) end % 对本次循环得到的最优解对应的路径Route上的泥土量进行更新 M=size(Route,2); % 路径以外的边上泥土量不变。 for i=1:M-1 W(Route(i),Route(i+1))=(1+beta)* W(Route(i),Route(i+1))-beta*Soil/(M-1); end if Z<TotalZ TotalZ=Z; TotalRoute=Route; end [LL,RR,Z1]=VNS(Route); if Z1<TotalZ TotalZ=Z1; TotalRoute=RR; end bestZ(t+1)=TotalZ; %更新迭代次数 t=t+1; end TotalZ TotalRoute LL DrawPath(TotalRoute,position); %迭代图 figure x=1:1:Iter; y=bestZ; plot(x,y,'r--') %plot(x,y); hold on %plot(x,y1,'r--');%适应值平均数 title('优化过程') xlabel('迭代次数') ylabel('最优适应值') axis([0,Iter,500,1200])

3 仿真结果

4 参考文献

[1]张露. "基于改进遗传算法求解带时间窗车辆路径规划问题." 中国物流与采购 14(2020):4.

[2]马龙等. "多目标多时间窗车辆路径问题的鸽群-水滴算法." 计算机工程与应用 57.2(2021):14.

部分理论引用网络文献，若有侵权联系博主删除。