遗传算法求解VRP问题的技术报告.doc
《遗传算法求解VRP问题的技术报告.doc》由会员分享，可在线阅读，更多相关《遗传算法求解VRP问题的技术报告.doc（8页珍藏版）》请在冰点文库上搜索。
遗传算法求解VRP问题的技术报告
摘要：
本文通过遗传算法解决基本的无时限车辆调度问题。
采用车辆和客户对应排列编码的遗传算法，通过种群初始化，选择，交叉，变异等操作最终得到车辆配送的最短路径。
通过MATLAB仿真结果可知，通过遗传算法配送的路径为61.5000km,比随机配送路径67km缩短了5.5km。
此结果表明遗传算法可以有效的求解VRP问题。
一、问题描述
1.问题描述
车辆调度问题（VehicleScheduling/RoutingProblem,VSP/VRP）的一般定义为[1]：
对一系列送货点和/或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量，送发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用极小、时间尽量少、使用车辆数尽量少等）。
问题描述如下[2]：
有一个或几个配送中心，每个配送中心有种不同类型的车型，每种车型有辆车。
有一批配送业务，已知每个配送业务需求量和位置或要求在一定的时间范围内完成，求在满足不超过配送车辆载重等的约束条件下，安排配送车辆在合适的时间、最优路线使用成本最小。
2.数学模型
设配送中心有K台车，每台车的载重量为，其一次配送的最大行驶距离为，需要向个客户送货，每个客户的货物需求量为，客户到j的运距为，配送中心到各个客户的距离为，再设为第K台车配送的客户数（=0表示未使用第K台车），用集合表示第k条路径，其中表示客户在路径k中的顺序为（不包括配送中心），令表示配送中心，若以配送总里程最短为目标函数，则可建立如下数学模型：
（1）
（2）
（3）
（4）
（5）
（6）
（7）
（8）
上述模型中，式
（1）为目标函数，即要求配送里程最短；式
（2）保证每条路径上各个客户的货物需求量之和不超过配送车的载重；式（3）保证每条配送路径的长度不超过配送车的最大行驶距离；式（4）表明每条路径上的客户数不超过总客户数；式（5）表明每个客户都得到配送服务；式（6）表示每条路径的客户组成；式（7）限制每个客户仅能由一台配送车送货；式（8）表示当第k辆车服务的客户数大于等于1时，说明该台车参加了配送，则sign（n）的值取1，否则为0。
二、研究现状
车辆调度问题在目标和范围方面有很大差别，主要是研究的目标和限定条件不同。
在研究目标方面有的是最短路线，有的是最短时间，有的是客户的方便程度等等。
在限定条件方面，有配送中心方面的区别，和有单配送中心的，有多配送中心；有配送车辆的数量、种类方面的区别，如车辆数有限、无限、单一车型和多种车型；在业务种类方面，有的是集货任务，有的是送货业务，有的是集送一体化业务，有的是各种业务混合情况。
有时间窗的车辆调度问题是最为普通的问题，以成为研究热点。
遗传算法在搜索过程中能够自动获取和积累有关搜索空间的知识，并能利用问题固有的知识来缩小搜索空间，自适应地控制搜索过程，动态有效地降低问题的复杂度，从而求得原问题的真正最优解或满意解，因此我来选用遗传算法来求解VSP问题。
三、解决方法
遗传算法的流程图如下：
基于车辆和客户对应排列编码的遗传算法的基本步骤：
（1） 编码：
采用车辆和客户对应排列的编码方法，其基本思路是：
用车辆数间的任意自然数（可重复）的排列表示车辆排列，用客户数间的互不重复的自然数排列表示客户排列，两者相对应，构成一个解，并对应一个配送路径方案。
例如：
对于一个用3台车向9个客户送货的车辆调度优化问题，设某解为（122131223）（456712398），即车辆排列为122131223，客户排列为456712398，两个排列相对应。
（2）适应度函数：
直接采用公式
（1）作为适应度评估函数。
对不可行路径进行权重惩罚。
（3）选择策略：
采用最佳个体保存与赌轮相结合的选择策略。
其具体操作为：
将每代群体中的N个个体按适应度由小到达排列，排在首位的个体性能最好，将它直接复制到下一代。
下一代群体的令N-1个体需要根据上一代群体的N个个体的适应度采用赌轮选择。
（4）交叉操作：
在该编码方式下有几种编码方式：
仅对车辆编码进行交叉、仅对客户编码进行交叉和同时对客户编码和车辆编码进行交叉。
本方法中采用仅对车辆编码的方式来交叉。
（5）变异操作：
本程序中对于变异操作，采用对客户编码变异的方式。
用MATLAB编程，在内存为2G，CPU2.10GHz的微机上运行。
采用运行参数：
种群规模为100，交叉概率为0.9，变异概率为0.2，进化代数100。
变异仅对客户编码，对不可行路径的惩罚权重去100km，具体程序代码见附录。
四、仿真结果
某配送中心有2台车，其载重量均为8t,车辆每次配送的最大行驶距离均为50km，配送中心与8个客户之间及8个客户之间相互距离及货物需求见下表：
表1客户需求
表2点对间距表
运行结果如下：
五、结论
从以上仿真结果可知，用遗传算法通过选择，交叉，变异等操作最终求得配送车辆物流问题中的最短路径，减少了车辆资源和时间的浪费，缩短了运输成本。
同时，在车辆调度问题中，进一步加入时间窗等参数的车辆调度问题的遗传算法的求解，还需要进一步的学习研究。
六、参考文献
[1]施朝春，王旭，葛显龙。
带有时间窗的多配送中心车辆调度问题研究[J]。
计算机工程与应用，2009；45（34）：
21—24
[2]程世东，刘小明，王兆赓。
物流配送车辆调度研究的回顾与展望[J]。
交通运输工程与信息学报，2004；2（3）：
93—97
七、附录：
程序
clearall;
closeall;
D=[06.541057.511104;
6.507.510107.57.57.56;
47.5010599157.5;
1010100107.57.5109;
5105100797.520;
7.57.597.57071010;
117.597.59701016;
107.515107.5101008;
467.5920101680];
n=40;
C=100;
Pc=0.9;
Pm=0.2;
N=8;
family=zeros（n,N）;
tic
fori=1:
n
family（i,:
）=randperm（N）;
end
Gt=family（1,:
）;
Ln=zeros（n,1）;
forkg=1:
1:
C
time（kg）=kg;
%------------------------------计算路径长度-----------------------------
fori=1:
1:
n
Ln（i,1）=fitness1（D,family（i,:
））;%计算每条染色体的适应度值
End
MinLn（kg）=min（Ln）;
minLn=MinLn（kg）;
rr=find（Ln==minLn）;
Gt=family（rr（1,1）,:
）;%更新最短路径
Family=family;
kg;
minLn;
%--------------------------------选择复制-------------------------------
K=30;
aa=0;bb=0;
[aa,bb]=size（Family）;
Family2=Family;
Ln2=Ln;
[Ln]=sort（Ln）;
fori=1:
aa
tt=find（Ln2==Ln（i,1））;
Family（i,:
）=Family（tt（1,1）,:
）;
end
fori=1:
K
j=aa+1-i;
Family（j,:
）=Family（i,:
）;
end
%---------------------------------交叉---------------------------------
[aa,bb]=size（Family）;
Family2=Family;
fori=1:
2:
aa
ifPc>rand&&iA=Family（i,:
）;
B=Family（i+1,:
）;
[A,B]=intercross（A,B）;
Family（i,:
）=A;
Family（i+1,:
）=B;
end
end
%-------------------------------变异-----------------------------------
Family2=Family;
fori=1:
aa
ifPm>=rand%变异条件
Family（i,:
）=mutate（Family（i,:
））;
End
end
Family=[Gt;Family];%保留上一代最短路径
[aa,bb]=size（Family）;
ifaa>n
Family=Family（1:
n,:
）;
end
family=Family;
clearFamily
end
toc
Gt
RL=fitness1（D,Gt）
plot（time,MinLn）;
xlabel（'times'）;ylabel（'MinLn'）;
（1）适应度函数
functionlen=fitness1（D,p）
N=8;
len=0;
fori=1:
（N-1）
len=len+D（p（i）,p（i+1））;
end
len=D（N,p
（1））+len+D（p（N）,N）;
b=0;
total=[00];
volume=8;
demand=[121214220];
b=find（p==8）;
ifb==1
total
（1）=0;
fori=2:
N
total
（2）=demand（p（i））+total
（2）;
end
elseifb==9
total
（2）=0;
fori=1:
（N-1）
total
（1）=demand（p（i））+total
（1）;
end
else
fori=1:
（b-1）
total
（1）=demand（p（i））+total
（1）;
end
fori=（b+1）:
N
total
（2）=demand（p（i））+total
（2）;
end
end
iftotal
（2）>volume|total
（1）>volume
len=len+100;
end
（2）交叉操作函数
function[a1,b1]=intercross（a1,b1）
L=length（a1）;
w=[00];
w
（1）=unidrnd（L-2）;
w
（2）=L-w
（1）;
ifw
（2）（1）[w
（1）,w
（2）]=exchange（w
（1）,w
（2））;
else
w
（1）=w
（1）;
w
（2）=w
（2）;
end
fori=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）变异函数
functionc=mutate（c）
L1=length（c）;
rray=randperm（L1）;
[c（rray
（1））,c（rray
（2））]=exchange（c（rray
（1））,c（rray
（2）））;
8/8
升级会员 