基于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; tic N=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-1for j=i+1:NUMdis=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;end endfor 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:NGBest(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; elseOldpgFitness=GBestFitness; %不相等时更新适应度值，并记录清零INUM=0; end if INUM>=20IsStop=1; endBestFitness(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('收敛曲线');GBestFitness g1 toc;

C01

总结

以上是生活随笔为你收集整理的基于PSO算法的带时间窗的车辆路径问题的仿真的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。