洒水车问题（单双向）
我用#CSDN#这个app发现了有技术含量的博客，小伙伴们求同去《洒水车问题(路线有单向有双向)》, 一起来围观吧 https://blog.csdn.net/weixin_30725467/article/details/95586790?utm_source=app&app_version=4.20.0&code=app_1562916241&uLinkId=usr1mkqgl919blen
想要这一题完整的解题过程跟MATLAB的代码和结果，越详细越好。
可以参考：
https://blog.csdn.net/weixin_33851180/article/details/112404026
看这篇论文分析：
https://max.book118.com/html/2018/0126/150695861.shtm
太难了。 个人感觉使用python sympy 一下就搞定了
车辆路径规划问题(Vehicle Routing Problem，VRP)是运筹学里重要的研究问题之一。VRP关注有一个供货商与K个销售点的路径规划的情况，可以简述为：对一系列发货点和收货点，组织调用一定的车辆，安排适当的行车路线，使车辆有序地通过它们，在满足指定的约束条件下（例如：货物的需求量与发货量，交发货时间，车辆容量限制，行驶里程限制，行驶时间限制等），力争实现一定的目标（如车辆空驶总里程最短，运输总费用最低，车辆按一定时间到达，使用的车辆数最小等）。
clear
clc
close all
dmax=40; %单车的最大行驶距离
qmax=30; %单车的最大货物携带量
c0=10; %单车的出发成本
c1=1; %单车的行驶成本
X=[18.70,15.29
16.47,8.45
20.07,10.14
19.39,13.37
25.27,14.24
22.00,10.04
25.47,17.02
15.79,15.10
16.60,12.38
14.05,18.12
17.53,17.38
23.52,13.45
19.41,18.13
22.11,12.51
11.25,11.04
14.17,9.76
24.00,19.89
12.21,14.50];
Q=[0 3.0 2.5 5.5 3.0 1.5 4.0 2.5 3.0 2.0 2.5 3.5 3.0 5.0 4.5 2.0 3.5 4.0];
NIND=100; %种群大小
MAXGEN=200;
Pc=0.9; %交叉概率
Pm=0.05; %变异概率
GGAP=0.9; %代沟
D=Distance(X); %生成距离矩阵
N=size(D,1); %客户点数
K=10; %初始的车辆数
%生成初始种群
Chrom=InitPop(NIND,N,K);
%优化
gen=1;
figure(1);
hold on;
box on;
xlim([0,MAXGEN])
title('优化过程')
xlabel('代数')
ylabel('最优值')
ObjV = PathCost(Chrom,Q,D,dmax,qmax,c1,c0,K); %计算总花费
[preObjV,BestIndex] = min(ObjV); %找出最小的花费
BestChrom = Chrom(BestIndex,:);
while gen<MAXGEN
%计算适应度
ObjV=PathCost(Chrom,Q,D,dmax,qmax,c1,c0,K);
line([gen-1,gen],[preObjV,min(ObjV)]);pause(0.001)
[preObjV,BestIndex]=min(ObjV);
BestObjV(gen)=preObjV;
AveObjV(gen)=sum(ObjV)/NIND;
BestChrom(gen,:) = Chrom(BestIndex,:);
FitnV = Fitness(ObjV);
%选择
SelCh1 = Select(Chrom,FitnV,GGAP);
%交叉
SelCh2 = Recombin(SelCh1,Pc);
%变异
SelCh3 = Mutate(SelCh2,Pm);
%逆转操作
SelCh4 = Reverse(SelCh3,D,Q,dmax,qmax,c1,c0,K);
%重新插入新的种群
Chrom =Reins(Chrom,SelCh4,ObjV);
gen = gen+1;
end
%画出最优解的路线图
ObjV=PathCost(Chrom,Q,D,dmax,qmax,c1,c0,K);
[minObjV,minInd]=min(ObjV);
DrawPath(Chrom(minInd(1),:),X);
%输出最优解
disp('最优服务顺序:')
p=OutputPath(Chrom(minInd(1),:));
disp(['总花费：',num2str(minObjV)]);
s=0;
R=Chrom(minInd(1),:);
for i=1:size(R,2)-1
s=s+D(R(i),R(i+1));
end
disp(['总里程：',num2str(s)]);
function NewChrIx=Sus(FitnV,Nsel)
%%随机遍历抽样
%输入
%FitnV 适应度值，列向量
%Nsel 被选择个体的数目
%输出
%NewChrIx 被选择个体的索引号
[Nind,ans]=size(FitnV);
cumfit = cumsum(FitnV);
trials = cumfit(Nind)/Nsel*(rand+(0:Nsel-1)');
Mf=cumfit(:,ones(1,Nsel));
Mt=trials(:,ones(1,Nind))';
[NewChrIx,ans]=find(Mt<Mf&[zeros(1,Nsel);Mf(1:Nind-1,:)]<=Mt);
[ans,shut]=sort(rand(Nsel,1));
NewChrIx=NewChrIx(shut);
function varargout = dsxy2figxy(varargin)
if length(varargin{1}) == 1 && ishandle(varargin{1}) ...
&& strcmp(get(varargin{1},'type'),'axes')
hAx = varargin{1};
varargin = varargin(2:end);
else
hAx = gca;
end;
if length(varargin) == 1
pos = varargin{1};
else
[x,y] = deal(varargin{:});
end
axun = get(hAx,'Units');
set(hAx,'Units','normalized');
axpos = get(hAx,'Position');
axlim = axis(hAx);
axwidth = diff(axlim(1:2));
axheight = diff(axlim(3:4));
if exist('x','var')
varargout{1} = (x - axlim(1)) * axpos(3) / axwidth + axpos(1);
varargout{2} = (y - axlim(3)) * axpos(4) / axheight + axpos(2);
else
pos(1) = (pos(1) - axlim(1)) / axwidth * axpos(3) + axpos(1);
pos(2) = (pos(2) - axlim(3)) / axheight * axpos(4) + axpos(2);
pos(3) = pos(3) * axpos(3) / axwidth;
pos(4) = pos(4) * axpos(4 )/ axheight;
varargout{1} = pos;
end
set(hAx,'Units',axun)
function DrawPath(Chrom,X)
%%画路线图函数
%输入
%Chrom 待画路线
%X 各服务点的坐标位置
R=Chrom;
figure;
hold on
plot(X(:,1),X(:,2),'o','color',[0.5,0.5,0.5])
plot(X(Chrom(1,1),1),X(Chrom(1,1),2),'rv','MarkerSize',20)
for i=1:size(X,1)
text(X(i,1)+0.05,X(i,2)+0.05,num2str(i),'color',[1,0,0]);
end
A=X(R,:);
row=size(A,1);
for i=2:row
[arrowx,arrowy]=dsxy2figxy(gca,A(i-1:i,1),A(i-1:i,2));
annotation('textarrow',arrowx,arrowy,'HeadWidth',8,'color',[0,0,1]);
end
hold off
xlabel('横坐标')
ylabel('纵坐标')
title('轨迹图')
box on