基于PSO算法的带时间窗的车辆路径问题的仿真

107 阅读 0 评论 71 点赞

我是靠谱客的博主开朗哑铃，这篇文章主要介绍基于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);
end

v0=zeros(N,NUM);
for i=1:N       %在VRP中粒子的速度代表交换序
      v0(i,:)=round(rand(1,NUM)*NUM);
end

distance_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);
end

distance_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;
    end
end

for i=1:N  %每个粒子路径的总距离
   EachPathDis(i)=PathDistance(x0(i,:),distance_two,distance_center);
end

IBest=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,:); %全局最优路径
end

pi_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);
end

IsChange=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;
end
if INUM>=20
    IsStop=1;
end

BestFitness(Iteration)=GBestFitness;
end

subplot(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;

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
107
108
109
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);
end

v0=zeros(N,NUM);
for i=1:N       %在VRP中粒子的速度代表交换序
      v0(i,:)=round(rand(1,NUM)*NUM);
end

distance_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);
end

distance_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;
    end
end


for i=1:N  %每个粒子路径的总距离
   EachPathDis(i)=PathDistance(x0(i,:),distance_two,distance_center);
end

IBest=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,:); %全局最优路径
end

pi_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);
end

IsChange=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;
end
if INUM>=20
    IsStop=1;
end

     BestFitness(Iteration)=GBestFitness;
end

subplot(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;