2022年遗传算法求解VRP问题的技术报告 .pdf

《2022年遗传算法求解VRP问题的技术报告 .pdf》由会员分享，可在线阅读，更多相关《2022年遗传算法求解VRP问题的技术报告 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Page 1 of 8 遗传算法求解 VRP 问题的技术报告摘要： 本文通过遗传算法解决基本的无时限车辆调度问题。采用车辆和客户对应排列编码的遗传算法，通过种群初始化，选择，交叉，变异等操作最终得到车辆配送的最短路径。通过MA TLAB 仿真结果可知，通过遗传算法配送的路径为61.5000km,比随机配送路径67km 缩短了 5.5km。此结果表明遗传算法可以有效的求解 VRP 问题。一、问题描述1.问题描述车辆调度问题（Vehicle Scheduling/Routing Problem,VSP/VRP ）的一般定义为1 ：对一系列送货点和/或收货点，组织适当的行车路线，使车辆有序地通过它们

2、，在满足一定的约束条件（如货物需求量、发送量，送发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用极小、时间尽量少、使用车辆数尽量少等）。问题描述如下2：有一个或几个配送中心),.,1(niDi，每个配送中心有K种不同类型的车型，每种车型有n辆车。 有一批配送业务),.,1(niRi，已知每个配送业务需求量),.,1(niqi和位置或要求在一定的时间范围内完成，求在满足不超过配送车辆载重等的约束条件下，安排配送车辆在合适的时间、最优路线使用成本最小。2.数学模型设配送中心有K 台车，每台车的载重量为),.,2, 1(KkQk，其一次配送的最大行驶距离为kD，

3、需要向L个客户送货，每个客户的货物需求量为),.,2, 1(Liqi，客户i到 j 的运距为ijd，配送中心到各个客户的距离为),.,2 , 1,(0Ljidj，再设kn为第 K 台车配送的客户数（kn=0表示未使用第K 台车），用集合kR表示第 k 条路径，其中kir表示客户kir在路径k 中的顺序为（不包括配送中心） ，令0kr表示配送中心，若以配送总里程最短为目标函数，则可建立如下数学模型：KkkrkrnirrnsignddZkknkkiik101)(min)1(1) knikiQqrk1(2) kkrkrnirrDnsignddkknkkiik)(01)1(3)Lnk0(4)名师资料总

4、结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - Page 2 of 8 LnKkk1(5),.,2, 1,.,2, 1kkikikniLrrR（6）21,21kkRRkk（7）其他01n1)(kknsign（8）上述模型中，式（1）为目标函数，即要求配送里程最短；式（2）保证每条路径上各个客户的货物需求量之和不超过配送车的载重；式（3）保证每条配送路径的长度不超过配送车的最大行驶距离；式（4）表明每条路径上的客户数不超过总客户数；式（5）

5、表明每个客户都得到配送服务；式（6）表示每条路径的客户组成；式（7）限制每个客户仅能由一台配送车送货；式（8）表示当第 k 辆车服务的客户数大于等于 1 时，说明该台车参加了配送，则sign(n)的值取 1，否则为 0。二、研究现状车辆调度问题在目标和范围方面有很大差别，主要是研究的目标和限定条件不同。在研究目标方面有的是最短路线，有的是最短时间， 有的是客户的方便程度等等。在限定条件方面，有配送中心方面的区别，和有单配送中心的，有多配送中心；有配送车辆的数量、种类方面的区别，如车辆数有限、无限、单一车型和多种车型；在业务种类方面，有的是集货任务，有的是送货业务，有的是集送一体化业务，有的是各

6、种业务混合情况。有时间窗的车辆调度问题是最为普通的问题，以成为研究热点。遗传算法在搜索过程中能够自动获取和积累有关搜索空间的知识，并能利用问题固有的知识来缩小搜索空间， 自适应地控制搜索过程，动态有效地降低问题的复杂度，从而求得原问题的真正最优解或满意解，因此我来选用遗传算法来求解VSP 问题。三、解决方法遗传算法的流程图如下：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - Page 3 of 8 初始化群体个体评价trand&

7、i=rand %变异条件Family(i,:)=mutate(Family(i,:);EndendFamily=Gt;Family; %保留上一代最短路径aa,bb=size(Family);if aan名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - Page 7 of 8 Family=Family(1:n,:);endfamily=Family;clear FamilyendtocGtRL=fitness1(D,Gt)plo

8、t(time,MinLn);xlabel( times);ylabel( MinLn ); （1）适应度函数function len=fitness1(D,p) N=8;len=0;for i=1:(N-1)len=len+D(p(i),p(i+1);endlen=D(N,p(1)+len+D(p(N),N);b=0;total=0 0;volume=8;demand=1 2 1 2 1 4 2 2 0;b=find(p=8);ifb=1total(1)=0;for i=2:Ntotal(2)=demand(p(i)+total(2);endelseif b=9total(2)=0;for i

9、=1:(N-1)total(1)=demand(p(i)+total(1);endelsefor i=1:(b-1)total(1)=demand(p(i)+total(1);endfor i=(b+1):Ntotal(2)=demand(p(i)+total(2);endendif total(2)volume|total(1)volumelen=len+100;end（2）交叉操作函数function a1,b1=intercross(a1,b1)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - -

10、- - - 第 7 页，共 8 页 - - - - - - - - - Page 8 of 8 L=length(a1);w=0 0;w(1)=unidrnd(L-2); w(2)=L-w(1);if w(2)w(1)w(1),w(2)=exchange(w(1),w(2);elsew(1)=w(1);w(2)=w(2);endfor i=w(1):(w(2)-1) xx=find(a1=b1(i+1);yy=find(b1=a1(i+1);a1(i+1),b1(i+1)=exchange(a1(i+1),b1(i+1);a1(xx),b1(yy)=exchange(a1(xx),b1(yy); end（3）对调操作函数function x1,y1=exchange(x1,y1) temp=x1;x1=y1;y1=temp;（4）变异函数function c=mutate(c)L1=length(c);rray=randperm(L1);c(rray(1),c(rray(2)=exchange(c(rray(1),c(rray(2);名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -