## 一、VRP简介

1 遗传算法基本原理

2 物流多配送中心的运输问题描述与数学建模

xi, j=0, 1决策变量, 其描述意义如表1所示。

3 基于遗传算法的物流多配送中心的运输调度

3.2 约束的处理

3.3 适应度转换

#### 3.4 遗传算子

①部分匹配交叉

②顺序交叉

3.5 算法步骤

Step1:设置遗传算法的参数, 如主要有交叉率Pc, 变异率Pm和种群规模TotalPop, 算法进行代数Generation;

Step2:gen=0;使用自然数编码方式, 随机产生个体数为TotalPop的初始种群;

Step3:解码工作, 把染色体译成运输成本, 这里的运输成本为总运输费用+总惩罚值, 并计算各染色体的适应值;

Step4:gen=gen+1;如gen>Generation, 算法结束, 否则继续;

Step5:进行交叉和变异工作, 交叉算子采用部分匹配与顺序交叉, 而变异则采用倒位变异和交换变异;

Step6:把第 (gen-1) 代和第gen代的染色体合并, 解码计算它们各自的适应值;并按适应值由大到小的顺序重新排列染色体;

Step7:根据适应值由大到小的顺序, 从合并的这些数目为2*TotalPop个染色体中选取前TotalPop个染色体作为下一代的父代, 转Step4;

## 二、部分源代码

```clear;
clc
%W=80; %每辆车的载重量
%Citynum=50; %客户数量
%Stornum=4;%仓库个数
%C     %%第二三列 客户坐标，第四列 客户需求   51,52,53,54为四个仓库
w=[];%存储每代的最短总路径
G=100;%种群大小
v1=60;
v2=300;
[dislist,Clist]=vrp(C);%dislist为距离矩阵 ，Clist为点坐标矩阵及客户需
L=[];%存每个种群的回路长度
for i=1:G
Parent(i,:)=randperm(Citynum);%随机产生路径
L(i,1)=curlist(Citynum,Clist(:,4),W,Parent(i,:),Stornum,dislist);
end
Pc=0.8;%交叉比率
Pm=0.3;%变异比率
species=Parent;%种群
children=[];%子代
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
disp('正在运行，时间比较长，请稍等.........')
g=50;
for generation=1:g
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
tic
fprintf('

Parent=species;%子代变成父代
children=[];%子代
Lp=L;
%选择交叉父代
[n m]=size(Parent);
%交叉，代处理
for i=1:n
for j=i:n
if rand<Pc
crossover
end
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
[n m]=size(Parent);
for i=1:n
if rand<Pm
parent=Parent(i,:);%变异个体
X=floor(rand*Citynum)+1;
Y=floor(rand*Citynum)+1;
Z=parent(X);
parent(X)=parent(Y);
parent(Y)=Z;                          %基因交换变异
children=[children;parent];
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%计算子代适应值(即路径长度) (这块用时比较长)
[m n]=size(children);
Lc=zeros(m,1);%子代适应值
for i=1:m
Lc(i,1)=curlist(Citynum,Clist(:,4),W,children(i,:),Stornum,dislist);
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%淘汰子代  剩余前G个最优解
[m n]=size(children);
if(m>G)
[m n]=sort(Lc);
children=children(n(1:G),:);
Lc=Lc(n(1:G));
end
%淘汰种群
species=[children;Parent];
L=[Lc;Lp];
[m n]=sort(L);
species=species(n(1:G),:);  %更新世代
L=L(n(1:G));
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%加入Opt优化
%分配仓库进行opt
temp=initialStor(Citynum,Clist(:,4),W,species(1,:),Stornum,dislist);%存储分配仓库后的结果【52 14 5 52 53 6 9 8 53......】
Rbest=temp;
L_best=L(1);
[m n]=size(temp);
start=1;
car=[];%存放opt优化后的结果
i=2;
while (i<n+1)
if (temp(i)>Citynum)
cur=[];
cur=Opt(i-start,[1:i-start,1:i-start],dislist,temp(start:i-1),Citynum);
car=[car,[cur,cur(1)]];
start=i+1;
i=i+2;
else
i=i+1;
end
end
L1=CalDist(dislist,car,Citynum);%计算进行优化后的回路长度
if( L1<L(1))
fprintf('Opt优化有效! %f --> %f',L(1),L1);
Rbest=car;
car(find(car>Citynum))=[];%去掉编码中的仓库，再加入父代
species=[species;car];
L=[L;L1];
L_best=L1;
end
L_best
w=[w,L_best];
toc
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
end```

## 四、matlab版本及参考文献

1 matlab版本

2014a

2 参考文献

[1] 包子阳,余继周,杨杉.智能优化算法及其MATLAB实例（第2版）[M].电子工业出版社，2016.

[2]张岩,吴水根.MATLAB优化算法源代码[M].清华大学出版社，2017.

[3]张拥华.基于遗传算法的多配送中心运输调度研究[J].湖南工业职业技术学院学报. 2009,9(03)

3 备注