一、VRP个人资料1 VRP基本原理
车辆路径规划问题(Vehicle Routing Problem，VRP )是运筹学中的重要研究问题之一。 VRP关注有一个供应商和k个经销商路径规划的情况，现简述如下。 对于一系列收货方和收货方，组织调用一定的车辆，安排适当的行驶路线，使车辆有序通过它们，满足指定的限制条件(例如货物需求量和出货量、交货时间、车辆容量限制、行驶距离限制、行驶时间限制等)
VRP的图例如下。2 问题属性与常见问题
车辆路径问题的特性比较复杂，总的来说包括四个方面的属性。
)1)地址特性包括端口数、需求类型、工作要求。
)2)车辆特性包括车辆数量、载重量限制、可搬运品种限制、运行路线限制、工作时间限制。
)3)问题的其他特性。
)4)目标函数可能是总成本的极小化，或最大工作成本的极小化，或定时工作的最大化。
3 常见问题有以下几类：
)1)旅行者问题
(2)带容量约束的车辆路线问题(CVRP ) )。
该模型难以推广到VRP的其他场景，不知道具体车辆的执行路径，因此正在继续改进模型。
)3)带时间窗的车辆路线问题
由于VRP问题的持续发展，考虑到需求点对车辆到达时间的要求，将时间窗限制纳入车辆途程问题将是时间窗车辆路径问题VRP with Time Windows，VRPTW。 带时间窗的车辆路径问题(VRPTW )是VRP加上客户到访的时间窗的限制。 在VRPTW问题中，成本函数除了行驶成本外，还包括提前到达一个客户所需的等待时间和客户所需的服务时间。 在VRPTW中，车辆除了VRP问题的限制外，还必须满足需求点的时间窗限制，但需求点的时间窗限制分为两部分。 一种是硬时间窗(Hard Time Window )，硬时间窗要求车辆必须在时间窗内到达，必须早到，必须等待，迟到的拒绝。 另一个是“软窗口”(Soft Time Window )，不一定要在时间窗口内到达，但要在时间窗口外到达，则需要罚款。 等待代替惩罚和拒绝是软窗口和硬窗口的最大区别。
型号2 (请参见2017 ageneralizedformulationforvehicleroutingproblems ) :
该模型是二维决策变量
)4)收集和分发问题
)5)多端口车辆路线问题
参考(2005 lim，多端口车辆路径问题的遗传算法_zzdgtx，1996 renaud ) ) ) ) ) ) ) ) 652
因为车辆是同质的，所以这里的建模没有在变量中加入车辆的维度。
(六)优先约束车辆路线问题
(七)兼容性约束车辆路线问题
(8)随机需求车辆路线问题
4 解决方案
)1)数学解析法
)2)人机交互法
)3)先分组后布线的方法
(4)先确定渠道再分组的方法
)5)节约或插入法
)6)改进或更换法
(7)数学规划近似法
(8)启发式教学
5 VRP与VRPTW对比
二、遗传算法概述http://www.Sina.com/http://www.Sina.com /
2.1遗传算法的生物学基础http://www.Sina.com/http://www.Sina.com/http://www.Sina.com/http://www.Sina
三、部分源代码clearclcclose alldmax=40； %自行车最大行驶距离qmax=30； %自行车最大货物携带量c0=10； %自行车出发成本c1=1； %自行车行驶成本x=[18.70、15.2916.47、8.4520.07、10.1419.39、13.3725.27、14.2422.00、10.0425.47、113.3725
4.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));enddisp(['总里程：',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{:});endaxun = get(hAx,'Units');set(hAx,'Units','normalized'); axpos = get(hAx,'Position');axdpw = axis(hAx);axwidth = diff(axdpw(1:2));axheight = diff(axdpw(3:4));if exist('x','var') varargout{1} = (x - axdpw(1)) * axpos(3) / axwidth + axpos(1); varargout{2} = (y - axdpw(3)) * axpos(4) / axheight + axpos(2);else pos(1) = (pos(1) - axdpw(1)) / axwidth * axpos(3) + axpos(1); pos(2) = (pos(2) - axdpw(3)) / axheight * axpos(4) + axpos(2); pos(3) = pos(3) * axpos(3) / axwidth; pos(4) = pos(4) * axpos(4 )/ axheight; varargout{1} = pos;endset(hAx,'Units',axun)function DrawPath(Chrom,X)%%画路线图函数%输入%Chrom 待画路线%X 各服务点的坐标位置R=Chrom;figure;hold onplot(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]);endA=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]);endhold offxlabel('横坐标')ylabel('纵坐标')title('轨迹图')box on 四、运行结果
1 matlab版本
2014a
2 参考文献
[1] 包子阳,热情的钢铁侠,灵巧的高跟鞋.智能优化算法及其MATLAB实例（第2版）[M].电子工业出版社，2016.
[2]yjddbz,无奈的魔镜.MATLAB优化算法源代码[M].清华大学出版社，2017.