完整版遗传算法求解VRP问题的技术报告

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

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

3、，L，配送中心到各个的运距为到客户要向j个客户送货，每个客户的货物需求量为ijid(i,j?1,2,.,L)nn=0表示未使用第K客户的距离为K台车配送的客户数（台车），再设，用为第j0kkRrrr 表示配 （不包括配送中心）条路径，其中，令表示客户在路径 k 集合中的顺序为表示第k0kkkiki 送中心，若以配送总里程最短为目标函数，则可建立如下数学模型：nKk?)(n?dd?minZ?signkrrkrr0kn1)kik(i?k (1) 1k?1i?nk?qrQkki (2) 1i?nk?d?d?sign(n)?D (3) kk0rrkrrkn1?)kiik(k1?i0?n?L (4) k

4、9 of 1 Page K? Ln?(5) k1k? （6） ,.,n,.,2L,i?1,2rR?r?1,kkkiki （7） 2k?,?k1?R?R2k1k?1n?1?k （8） ?sign)(n?k0其他?上述模型中，式（1）为目标函数，即要求配送里程最短；式（2）保证每条路径上各个客户的货物需求量之和不超过配送车的载重；式（3）保证每条配送路径的长度不超过配送车的最大行驶距离；式（4）表明每条路径上的客户数不超过总客户数；式（5）表明每个客户都得到配送服务；式（6）表示每条路径的客户组成；式（7）限制每个客户仅能由一台配送车送货；式（8）表示当第 k 辆车服务的客户数大于。 01，否则为

5、时，说明该台车参加了配送，则等于1sign(n)的值取二、 研究现状 车辆调度问题在目标和范围方面有很大差别，主要是研究的目标和限定条件不同。在研究目标方面有的是最短路线，有的是最短时间，有的是客户的方便程度等等。在限定条件方面，有配送中心方面的区别，和有单配送中心的，有多配送中心；有配送车辆的数量、种类方面的区别，如车辆数有限、无限、单一车型和多种车型；在业务种类方面，有的是集货任务，有的是送货业务，有的是集送一体化业务，有的是各种业务混合情况。有时间窗的车辆调度问题是最为普通的问题，以成为研究热点。 遗传算法在搜索过程中能够自动获取和积累有关搜索空间的知识，并能利用问题固有的知识来缩小搜索

6、空间，自适应地控制搜索过程，动态有效地降低问题的复杂度，从而求得原问题的真正最优解或满意解，因此我来选用遗传算法来求解VSP问题。 三、 解决方法 遗传算法的流程图如下： 9 of 2 Page 初始化群体个体评价trand&i=rand Family(i,:)=mutate(Family(i,:); End end 保留上一代最短路径% Family=Gt;Family; aa,bb=size(Family); aanif Family=Family(1:n,:); end family=Family; Familyclear end toc Gt RL=fitness1(D,Gt) plo

7、t(time,MinLn);xlabel(times);ylabel(MinLn); （1）适应度函数 function len=fitness1(D,p) N=8; len=0; i=1:(N-1)for len=len+D(p(i),p(i+1); end len=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);9 of 7 Page b=1 if total(1)=0; i=2:N for total(2)=demand(p(i)+total(2); end b

8、=9elseif total(2)=0; i=1:(N-1) for total(1)=demand(p(i)+total(1); end else i=1:(b-1)for total(1)=demand(p(i)+total(1); end i=(b+1):Nfor total(2)=demand(p(i)+total(2); end end total(2)volume|total(1)volumeif len=len+100; end ）交叉操作函数（2 a1,b1=intercross(a1,b1)function L=length(a1); w=0 0;w(1)=unidrnd(L-2); w(2)=L-w(1); w(2)w(1)w(1),w(2)=exchange(w(1),w(2);if else w(1)=w(1); w(2)=w(2); end i=w(1):(w(2)-1) for 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 x1,y1=exchange(x1,y1) function temp=x1; x1=y1;