基于PSO算法的时间窗车辆路径优化仿真

1.仿真预览

2.理论分析

带时间窗的车辆路径选择问题模型描述： 有一个中心仓库，拥有车辆K辆， 容量都为q，现有L个发货点运输任务需要完成，以1，2，…，L表示，第i个发货点的货运量为gi，max(g)i≤ max(qi)，完成发货点i任务需要的时间（装货或卸货）表示Ti，且任务i必须再时间窗口[ETi，LTi]完成，其中ETi为任务i的允许最早开始的时间，LTi为任务i允许最迟开始的时间，如果车辆到达发货点i的时间早于开始时间，则车辆需要在i处等待；如果车辆到达时间晚于LTi，任务i将被延迟进行。VRPTW模型路径优化的数学模型如下：

数学模型的具体解释：

式（1）确保总成本z最小；式（2）确保每条路径上的各发货点的总需求量不超过此条路径配送车的容量；式（3）表示每个任务点的需求仅由一辆车来完成；式（4）（5）保证每个发货点都能得到车辆的配送服务。

3.部分核心代码

登录后复制

clc;clear;close all;ticN=600;   %粒子群个数NUM=30;   
%用户个数OldpgFitness=0;    %老的适应值Iteration=0;       
%迭代次数的计数，当适应值不再改变时，迭代就停止，而不是到最大迭代次数结束MI=100;     
%最大迭代次数IsStop=0; INUM=0;     %当适应值不变的时候，INUM+1计数，到20时就结束迭代c1=0.1;c2=5;w=0.96;
load 'node.txt';xy=node(2:NUM+1,2:3);x0=ones(N,NUM); for i=1:N   
%随机给每个粒子分配路径      x0(i,:)=randperm(NUM);endv0=zeros(N,NUM);for i=1:N       
%在VRP中粒子的速度代表交换序      v0(i,:)=round(rand(1,NUM)*NUM);enddistance_center=zeros(1,NUM);
%每个粒子离配送中心的距离for i=1:NUM        
distance_center(i)=sqrt((node(i+1,2)-node(1,2))^2+(node(i+1,3)-node(1,3))^2);
enddistance_two=zeros(NUM,NUM); %每两个用户之间的距离for i=1:NUM-1    for j=i+1:NUM        
dis=sqrt((xy(i,1)-xy(j,1))^2+(xy(i,2)-xy(j,2))^2);        distance_two(i,j)=dis;        
distance_two(j,i)=dis;    endendfor i=1:N  %每个粒子路径的总距离   EachPathDis(i)=PathDistance(x0(i,:),
distance_two,distance_center);endIBest=x0;   %粒子个体的历史最优路径IBestFitness=EachPathDis;
%粒子个体的历史最优适应值[GBestFitness,index]=min(EachPathDis);  %粒子全局最优路径g1=GBestFitness;    
%粒子全局最优适应值figure;subplot(2,2,1);PathPlot(node,NUM,index,IBest);title('随机解');
while(IsStop==0)&&(Iteration<MI) Iteration=Iteration+1; %g2(Iteration)=GBestFitness;  
for i=1:N      GBest(i,:)=x0(index,:); %全局最优路径endpi_x=GenerateChangeNums(x0,IBest); 
%（Pi-Xi）就是使xi向个体最优解靠近，而非远离，这也是一个交换用户序号的过程，得到交换的序pi_x=HoldByOdds(pi_x,c1);      
%这是c1*（Pi-Xi）的过程，以c1保留交换序pg_x=GenerateChangeNums(x0,GBest);  %（Pg-Xi）就是使Xi向全局最优解靠近，
得到路径中要交换的用户序号pg_x=HoldByOdds(pg_x,c2);  %这是c2*（Pg-Xi）的过程，以c2保留交换序v0=HoldByOdds(v0,w); 
 %这是w*Vi的过程，以概率w得到交换序x0=PathExchange(x0,v0);   %通过交换序来改变每个粒子的路径，
 也就是优化的过程x0=PathExchange(x0,pi_x);x0=PathExchange(x0,pg_x);for i=1:N  %计算每条路径的距离      
 EachPathDis(i)=PathDistance(x0(i,:),distance_two,distance_center);endIsChange=EachPathDis<IBestFitness;   
 %更新后的距离优于更新前的，记录序号IBest(find(IsChange),:)=x0(find(IsChange),:); 
 %更新个体最佳路径IBestFitness=IBestFitness.*(~IsChange)+EachPathDis.*IsChange;  
 %更新个体最佳路径距离[GBestFitness,index]=min(EachPathDis);   
 %更新全局最佳路径,记录相应的序号if GBestFitness==OldpgFitness %比较更新前和更新后的适应度值;      
 INUM=INUM+1;else      OldpgFitness=GBestFitness;  %不相等时更新适应度值，并记录清零      
 INUM=0;endif INUM>=20    IsStop=1;end     
 BestFitness(Iteration)=GBestFitness;endsubplot(2,2,2);PathPlot(node,NUM,index,IBest);
 title('最佳路径');axis([0,60,0,80]);subplot(2,2,3);plot((1:Iteration),BestFitness(1:Iteration));
 grid on;title('收敛曲线');GBestFitnessg1toc;1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21
 .22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.51.52.53.
 54.55.56.57.58.59.60.61.62.63.64.65.66.67.68.69.70.71.72.73.74.75.76.77.78.79.80.81.82.83.84.85.
 86.87.88.89.90.91.92.93.94.95.96.97.98.99.100.101.102.103.104.105.106.

免责声明：本文系网络转载或改编，未找到原创作者，版权归原作者所有。如涉及版权，请联系删