[Matlab][遗传算法][VRPTW]带时间窗口的车辆路径规划问题

VRPTW问题简介

由于VRP问题的持续发展，考虑需求点对于车辆到达的时间有所要求之下，在车辆途程问题之中加入时窗的限制，便成为有时间窗车辆路径问题（VRP with Time Windows, VRPTW）。有时间窗车辆路径问题（VRPTW）是在VRP上加上了客户的被访问的时间窗约束。在VRPTW问题中，除了行驶成本之外, 成本函数还要包括由于早到某个客户而引起的等待时间和客户需要的服务时间。
在VRPTW中，车辆除了要满足VRP问题的限制之外，还必须要满足需求点的时窗限制，而需求点的时窗限制可以分为两种，一种是硬时窗（Hard Time Window），硬时窗要求车辆必须要在时窗内到达，早到必须等待，而迟到则拒收；另一种是软时窗（Soft Time Window），不一定要在时窗内到达，但是在时窗之外到达必须要处罚，以处罚替代等待与拒收是软时窗与硬时窗最大的不同。

VRPTW问题模拟结果

路径结果

VRPTW问题遗传算法代码

运行环境：Matlab2016a及以上版本

clear;clc;
close all;
format long;global strTtile;%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% VRPTW参数
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
global site X capacity demand siteStart siteFinish start finish service velocity;
capacity = 8; %车辆装载量
velocity = 55/60; %km/mindemand = []; %需求
start = []; %开始时间
finish = []; %结束时间
service = []; %服务时间%site = data(1,:);
site = [122.275563,43.607704];
siteStart = 360*velocity;
siteFinish = 1080*velocity;
% X = data(2:50,:);
X = [122.27678,43.718268
%     122.57678,44.118268
%     122.787946,43.135897123.323948,44.132521122.360879,42.955817121.781823,42.743228120.785148,42.40258121.321807,43.59698];
% demand = demand(2:50,:);
demand = [3
%     3
%     2.54.53.54.23.24.6];
timeWindow = [13 15
%     5	12
%     8	1612	187	178	168	168	16]*60;
start = timeWindow(:,1)*velocity;
finish = timeWindow(:,2)*velocity;
service = [0.4
%     0.3
%     0.20.10.60.30.10.3]*60*velocity;%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% 遗传算法优化
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
NIND=10;       %种群大小
MAXGEN=50;   %代数
Pc=0.9;         %交叉概率
Pm=0.1;        %变异概率
GGAP=0.9;      %代沟(Generation gap)
D=Distanse(X);  %生成距离矩阵
siteD=SiteDistance(site,X); %货仓到各个节点的距离
N=size(D,1);    %(34*34)
%% 初始化种群
Chrom=InitPop(NIND,N);
%% 在二维图上画出所有坐标点
% figure
% plot(X(:,1),X(:,2),'o');
%% 画出随机解的路线图
% DrawPath(Chrom(1,:),X)
pause(0.0001)
%% 输出随机解的路线和总距离
disp('初始种群中的一个随机值:')
OutputPath(siteD,D,Chrom(1,:));
Rlength=PathLengthForDemo(siteD,D,Chrom(1,:),false);
disp(['总距离：',num2str(Rlength)]);
disp('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~')
%% 未优化前路径
[len,result] = PathLengthForDemo(siteD,D,Chrom(1,:),true);
strTtile = '未优化前路径';
DrawPath(Chrom(1,:),site,X,result{1})
%% 优化
tic
gen=0;
figure(100);
hold on;box on
xlim([0,MAXGEN])
title('遗传算法GA 优化过程')
xlabel('代数')
ylabel('最优值')
ObjV=PathLengthForDemo(siteD,D,Chrom,false);  %计算路线长度
preObjV=min(ObjV);
while gen<MAXGEN%% 计算适应度ObjV=PathLengthForDemo(siteD,D,Chrom,false);  %计算路线长度fprintf('%d   %1.10f\n',gen,min(ObjV))figure(100);line([gen-1,gen],[preObjV,min(ObjV)]);pause(0.0001)preObjV=min(ObjV);FitnV=Fitness(ObjV);%% 选择SelCh=Select(Chrom,FitnV,GGAP);%% 交叉操作SelCh=Recombin(SelCh,Pc);%% 变异SelCh=Mutate(SelCh,Pm);%% 逆转操作SelCh=Reverse(SelCh,siteD,D);%% 重插入子代的新种群Chrom=Reins(Chrom,SelCh,ObjV);%% 更新迭代次数gen=gen+1 ;
end
grid on;
%% 画出最优解的路线图
[ObjV,segmentResult]=PathLengthForDemo(siteD,D,Chrom,false);  %计算路线长度
[minObjV,minInd]=min(ObjV);
strTtile = '[VRPTW]遗传算法优化后路径';
DrawPath(Chrom(minInd(1),:),site,X,segmentResult{minInd})
%% 输出最优解的路线和总距离
disp('最优解:')
p=OutputPath(siteD,D,Chrom(minInd(1),:));
disp(['总距离：',num2str(ObjV(minInd(1)))]);
disp('-------------------------------------------------------------')PathLengthForDemo(siteD,D,Chrom(minInd(1),:),true)toc

完整代码联系作者

QQ 3538518672
微信 ssttoonn123