有时间窗车辆路径问题VRPTW
VRPTW描述：
有时间窗车辆路径问题（vehicle routing problems with time windows，VRPTW）车辆路线问题（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。
在VRPTW中，车辆除了要满足VRP问题的限制之外，还必须要满足需求点的时窗限制，而需求点的时窗限制可以分为两种，一种是硬时窗（Hard Time Window），硬时窗要求车辆必须要在时窗内到达，早到必须等待，而迟到则拒收；另一种是软时窗（Soft Time Window），不一定要在时窗内到达，但是在时窗之外到达必须要处罚，以处罚替代等待与拒收是软时窗与硬时窗最大的不同。
含时窗限制之车辆途程问题（VRPTW）相对于车辆途程问题（VRP），必须额外考虑到运送时间与时间窗口，其主要的原因来自顾客有服务时间的最后期限和最早开始服务时间的限制。故在此限制条件之下，原本VRP问题除了空间方面的路径（Routing）考虑之外，还必须要加上时间上的排程（Scheduling）考虑。同时由于场站也有时间窗的限制，也间接造成路径长度的限制，由此可知VRPTW的总巡行成本不仅包含运送成本，还需要考虑时间成本，以及未在时间窗限制内送达的处罚成本。因此，若要得到一个好的解答，时间和空间（Temporal andSpatial）问题的探讨是非常重要的。
数学模型：
部分程序和结果
% Author: 怡宝2号 博士猿工作室
% Use: 基于遗传算法的求解有时间窗约束的车辆路径优化
% Remark： 本人qq：778961303，如有疑问请咨询
clc
clearall
closeall
%遗传算法的初始化参数
MAXGEN= 500; %最大遗传代数
NIND=20; %初始种群的大小
MAXGEN=100; %遗传代数
PC= 0.6; %交叉概率
PM= 0.1; %变异概率
avefitcost= zeros(MAXGEN,1); %每代的平均成本
bestfitcost= zeros(MAXGEN,1); %每代花销的最小值
%变量初始化
bestpop= zeros(MAXGEN,n-1); %每代最优的染色体
%种群初始化
chrom= initial(NIND,n);
%遗传算法迭代开始
gen=1;
whilegen<=MAXGEN
[fitcost fitness] =FitnessFun(chrom,D,Q,dmax,qmax,unloadt,ET,EL,CT,CL,c0,c1,v,n,NIND);
%求每代的最优值、个体和平均值
[minfitcost index] = min(fitcost);
avefitcost(gen) = mean(fitcost); %平均值
bestfitcost(gen) = minfitcost; %最小值
bestpop(gen,:) = chrom(index(1),:); %每代最优染色体
%选择
chrom=select(chrom,fitness);
selch = [ones(NIND,1) chrom];
%交叉
for i=1:2:NIND
if PC>rand
selch(i:i+1,:)=OrderCrossover(selch(i,:),selch(i+1,:));
end
end
%变异
selch = ExchangeMutation(selch);
for i=1:NIND
temp = selch(i,:);
temp = temp(temp>1);
chrom(i,:) = temp;
end
gen = gen+1;
end
%迭代图
figure
x=1:1:MAXGEN;
plot(x,bestfitcost,'r--')
holdon
%plot(x,avefitcost,'b--');%适应值平均数
title('遗传优化过程')
xlabel('迭代次数')
ylabel('最优适应值')
%%%找出最优的适应值、个体
[minbestfit,minindex]=min(bestfitcost);%取最优适应值的位置、最优适应值
minindex=minindex(1);
minbestpop=bestpop(minindex,:); %取最优个体
disp(['最优成本为：',num2str(minbestfit)]);
disp(['最优染色体：',num2str(minbestpop)]);
route= [1 tempchrom];
p=num2str(route(1));
fori=2:length(route)
p=[p,'->',num2str(route(i))];
end
disp(p);
%计算行驶的路程
s=0;
r=route;
fori=1:size(r,2)-1
s=s+D(r(i),r(i+1));
end
disp(['行驶里程：',num2str(s)]);
%计算用了几辆车
index= find(route==1);
disp(['使用的车辆数为：',num2str(length(index)-1)]);
%画线路
DrawPath(route,xy);
Remark： 本人qq：778961303，如有疑问请咨询
结果：
VRPTW描述：
有时间窗车辆路径问题（vehicle routing problems with time windows，VRPTW）车辆路线问题（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。
在VRPTW中，车辆除了要满足VRP问题的限制之外，还必须要满足需求点的时窗限制，而需求点的时窗限制可以分为两种，一种是硬时窗（Hard Time Window），硬时窗要求车辆必须要在时窗内到达，早到必须等待，而迟到则拒收；另一种是软时窗（Soft Time Window），不一定要在时窗内到达，但是在时窗之外到达必须要处罚，以处罚替代等待与拒收是软时窗与硬时窗最大的不同。
含时窗限制之车辆途程问题（VRPTW）相对于车辆途程问题（VRP），必须额外考虑到运送时间与时间窗口，其主要的原因来自顾客有服务时间的最后期限和最早开始服务时间的限制。故在此限制条件之下，原本VRP问题除了空间方面的路径（Routing）考虑之外，还必须要加上时间上的排程（Scheduling）考虑。同时由于场站也有时间窗的限制，也间接造成路径长度的限制，由此可知VRPTW的总巡行成本不仅包含运送成本，还需要考虑时间成本，以及未在时间窗限制内送达的处罚成本。因此，若要得到一个好的解答，时间和空间（Temporal andSpatial）问题的探讨是非常重要的。
数学模型：
部分程序和结果
% Author: 怡宝2号 博士猿工作室
% Use: 基于遗传算法的求解有时间窗约束的车辆路径优化
% Remark： 本人qq：778961303，如有疑问请咨询
clc
clearall
closeall
%遗传算法的初始化参数
MAXGEN= 500; %最大遗传代数
NIND=20; %初始种群的大小
MAXGEN=100; %遗传代数
PC= 0.6; %交叉概率
PM= 0.1; %变异概率
avefitcost= zeros(MAXGEN,1); %每代的平均成本
bestfitcost= zeros(MAXGEN,1); %每代花销的最小值
%变量初始化
bestpop= zeros(MAXGEN,n-1); %每代最优的染色体
%种群初始化
chrom= initial(NIND,n);
%遗传算法迭代开始
gen=1;
whilegen<=MAXGEN
[fitcost fitness] =FitnessFun(chrom,D,Q,dmax,qmax,unloadt,ET,EL,CT,CL,c0,c1,v,n,NIND);
%求每代的最优值、个体和平均值
[minfitcost index] = min(fitcost);
avefitcost(gen) = mean(fitcost); %平均值
bestfitcost(gen) = minfitcost; %最小值
bestpop(gen,:) = chrom(index(1),:); %每代最优染色体
%选择
chrom=select(chrom,fitness);
selch = [ones(NIND,1) chrom];
%交叉
for i=1:2:NIND
if PC>rand
selch(i:i+1,:)=OrderCrossover(selch(i,:),selch(i+1,:));
end
end
%变异
selch = ExchangeMutation(selch);
for i=1:NIND
temp = selch(i,:);
temp = temp(temp>1);
chrom(i,:) = temp;
end
gen = gen+1;
end
%迭代图
figure
x=1:1:MAXGEN;
plot(x,bestfitcost,'r--')
holdon
%plot(x,avefitcost,'b--');%适应值平均数
title('遗传优化过程')
xlabel('迭代次数')
ylabel('最优适应值')
%%%找出最优的适应值、个体
[minbestfit,minindex]=min(bestfitcost);%取最优适应值的位置、最优适应值
minindex=minindex(1);
minbestpop=bestpop(minindex,:); %取最优个体
disp(['最优成本为：',num2str(minbestfit)]);
disp(['最优染色体：',num2str(minbestpop)]);
route= [1 tempchrom];
p=num2str(route(1));
fori=2:length(route)
p=[p,'->',num2str(route(i))];
end
disp(p);
%计算行驶的路程
s=0;
r=route;
fori=1:size(r,2)-1
s=s+D(r(i),r(i+1));
end
disp(['行驶里程：',num2str(s)]);
%计算用了几辆车
index= find(route==1);
disp(['使用的车辆数为：',num2str(length(index)-1)]);
%画线路
DrawPath(route,xy);
Remark： 本人qq：778961303，如有疑问请咨询
结果：
