在编程求解VRP问题之前首先要深刻理解TSP问题的编程思想，一般学会TSP的编程即可以进行VRP编程，好，在这里简单的说一下，如何由TSP问题转化到VRP问题。
首先VRP问题是指带有配送中心的配送路径规划，其TSP问题(旅行商)应用到配送路径规划问题中，二者唯一的区别就是VRP有配送中心，而TSP没有配送中心，即TSP在配送过程中，车辆不需要回到配送中心。说到这里，我们就要问一个问题，在VRP问题中，什么情况下，车辆需要回到配送中心？那么一般VRP问题是由汽车的配送量来决定的，假设有6座城市，各个城市的需求量为50，60，70，80，90，100，用汽车由配送中心到各个城市配送货物，汽车的装载量为200，很明显，汽车不可能一趟把所有城市的货物(总需求量为：450)都送完，所以要送多次，送完一次回一次配送中心，再拉货去配送，这就构成了VRP问题。
那么如何从TSP转化为VRP问题呢，下面就用这个简单的例子来说明一下。
有6座城市编号为1，2，3，4，5，6各个城市的货物需求量为50，60，70，80，90，100，一般我们把配送中心的编号为0，首先假设汽车装载量特别大，假设为1000，此时汽车可以把所有城市的货物需求量一次性配送完成，这时配送路径0-1-2-3-4-5-6-0即为一个可行路径，这个时候改问题就为TSP问题。
如果汽车的装配量为200，那对于路径1-2-3-4-5-6，汽车从配送中心0出发，给1送50货物，给2送60货物，给3送70货物，此时汽车已经装载了180的货物.如果还要给4送，则需要装载180+80=260的货物，汽车超载拉不了，所以汽车在给城市3送完货物后，要回配送中心，此时路径应该为0-1-2-3-0。之后汽车从配送中心出发，去给4送80，给5送90，此时汽车装载170货物，不能装载城市10的货物了，所以有需要回配送中心，这时路径变成了0-1-2-3-0-4-5-0，继续进行路径变成了0-1-2-3-0-4-5-0-6-0.
至此完成了TSP路径转换成VRP路径。
如果上面的内容你明白了，你就会发现你只要根据TSP的方法进行编程，然后在计算适应度的时候，按照上面说的把TSP路径转换为VRP路径然后再计算路径的长度，就OK啦。
明白了吗？如果不明白的话再好好读读上面说的就可以了，给大家演示一下！
假设汽车的载重量很大时，其实就是一个TSP问题
当载重量有限时，结果如图
看到效果对比了，源程序代码如下
%%%% 程序解释：
%%%% VRP其实是对TSP的改进。TSP是对一系列城市的遍历求距离最短，而VRP其实也是
%%%% 对一系列城市的遍历，只是在遍历过程中车辆需要回到配送中心。因此在计算行
%%%% 车距离时，需要计算回配送中心的距离。其中，什么时候回计算中心需要根据车
%%%% 的载重量和车的最大行程来决定。
%%%% 本程序根据TSP进行改编，具体改编如下：根据TSP方法生成路径、并进行选择、
%%%% 交叉、变异、重插等遗传操作，但在计算适应度的时候发生变化，即汽车的总距
%%%% 离不再是各个城市首尾相连的距离，而是在路径中插入配送中心的VRP路径距离。
%%%% designed by 圆
%%%% 特别注意！汽车最大行驶距离应大于 2*距离矩阵的最大值，即可以保证汽车从
%%%% 配送中心到城市能够再返回。否则程序运行出错！！！
%%%% 提示：增加种群数量，可以增加初始解的可能性，更容易得到最优解！
clear
clc
close all
%% QQ 530807088 一个有心的人在用心做事
position =[81.5,87,75,80,89,77,76,87,73,77,73,91,92,88,73
41.5,41,53,38,41,58,45,53,38,38,31,47,44,36,58]';
demand=[0,1,2,3,2,3,3,2,3,4,3,4,3,4,2];
CarLoad=10;% 汽车最大载重量
CarLength=3000;% 汽车最大行驶距离
CityNum=14;% 城市数量
NP=30;% 种群大小
maxgen=500;% 最大进化代数
Pc=0.9;% 交叉概率
Pm=0.1;% 变异概率
Gap=0.9;% 代沟(Generation gap)
%% 计算各城市之间的距离
D=zeros(CityNum+1);
for i=1:CityNum+1
for j=i+1:CityNum+1
D(i,j)=((position(i,1)-position(j,1))^2+(position(i,2)-position(j,2))^2)^0.5;
D(j,i)=D(i,j);
end
end
%% 初始化种群
X=InitPop(NP,CityNum);
RandermPath=X(1,:);% 记录一个随机路径
%% 遗传进化
gen=1;
figure;
hold on;
box on
xlim([0,maxgen])
title('遗传算法求解VRP路径优化过程')
xlabel('迭代次数')
ylabel('最优值')
RouteLength=Fitness(X,D,demand,CarLoad,CarLength);% 计算路线长度
BestLength=min(RouteLength);
while gen
% 计算路线长度
RouteLength=Fitness(X,D,demand,CarLoad,CarLength);% 计算路线长度
line([gen-1,gen],[BestLength,min(RouteLength)]);
pause(0.01)
% 记录各代最优值
BestLength=min(RouteLength);
FG(gen)=BestLength;% 各代最短路径
% 计算适应度
fit=1./(RouteLength+1);%
将求最小路径转为最大值fit
% 选择
XSel=Select(X,fit,Gap);
% 交叉操作
XSel=Recombin(XSel,Pc);
% 变异
XSel=Mutate(XSel,Pm);
% 逆转操作
XSel=Reverse(XSel,D,demand,CarLoad,CarLength);
% 重插入子代的新种群
X=Reins(X,XSel,fit);
% 更新迭代次数
gen=gen+1 ;
end
%% 画出最优解的路线图
RouteLength=Fitness(X,D,demand,CarLoad,CarLength);% 计算路线长度
[minLength,minInd]=min(RouteLength);
%% 输出最优解的路线和总距离
disp('最优配送路径:')
BestRoute=OutputPath(X(minInd(1),:),D,demand,CarLoad,CarLength);
disp(['配送车辆总行驶路程：',num2str(RouteLength(minInd(1)))]);
%% 绘制实际路线，如果没有各点坐标时，可以不用绘制
figure
for i=1:length(BestRoute)-1
plot(position(BestRoute(i:i+1)+1,1),position(BestRoute(i:i+1)+1,2),'ro-','MarkerFaceColor','b')
hold on
end
plot(position(1,1),position(1,2),'bp','MarkerFaceColor','r','MarkerSize',15)
title('VRP配送路线图')
xlabel('坐标X')
ylabel('坐标Y')
需要程序的联系我哈~~
如果觉得《matlab 物流 算法 遗传算法求物流配送路径VRP问题MATLAB源码》对你有帮助，请点赞、收藏，并留下你的观点哦！
