运输企业管理课程设计Word文件下载.docx
《运输企业管理课程设计Word文件下载.docx》由会员分享，可在线阅读，更多相关《运输企业管理课程设计Word文件下载.docx（12页珍藏版）》请在冰点文库上搜索。
2.2遗传算法解决运输线路优化问题步骤：
设配送中心有K辆汽车，每辆汽车的载重量为Qk（k=1,2,..,K）,Q<
=10，其一次配送的最大行驶距离为40km，需要向15个需求点送货，每个需求点的需求量为qi
（i=1，2，·
·
，10），需求点i到j的运距为dij，配送中心到各需求点的距离为d0j（j=1，2，·
，15），再设nk为第k（k=1,2,..,k）辆汽车配送的需求点数（nk=0表示未使用第k辆汽车），用集合Rk表示第k条路径，其中的元素rki表示需求点rki在路径k中的顺序为i（不包括配送中心），令rk0=0表示配送中心，则可建立如下物流配送路径优化问题的数学模型：
（1）
（2）
（3）
0≤nk≤L（4）
（5）
（6）
（7）
（8）
上述模型中，
（1）式为目标函数；
（2）式保证每条路径上各需求点的需求量之和不超过汽车的载重量；
（3）式保证每条配送路径的长度不超过汽车一次配送的最大行驶距离；
（4）式表明每条路径上的需求点数不超过总需求点数；
（5）式表明每个需求点都得到配送服务；
（6）式表示每条路径的需求点的组成；
（7）式限制每个需求点仅能由一辆汽车送货；
（8）式表示当第k辆汽车服务的客户数≥1时，说明该辆汽车参加了配送，则取sign（nk）=1，当第k辆汽车服务的客户数<
1时，表示未使用该辆汽车，因此取sign（nk）=0。
针对物流配送路径优化问题的特点，构造了求解该问题的遗传算法。
（1）编码方法的确定。
根据物流配送路径优化问题的特点，采用简单直观的自然数编码方法，用0表示配送中心，用1、2、·
、L表示各需求点。
由于在配送中心有K辆汽车，则最多存在K条配送路径，每条配送路径都始于配送中心，也终于配送中心，为了在编码中反映车辆配送的路径，我采用了增加K-1个虚拟配送中心的方法，分别用L+1、L+2、·
、L+K-1表示。
这样，1、2、·
、L+K-1这L+K-1个互不重复的自然数的随机排列就构成一个个体，并对应一种配送路径方案。
（2）初始群体的确定。
随机产生一种1~L+K-1这L+K-1个互不重复的自然数的排列，即形成一个个体。
设群体规模为N，则通过随机产生N个这样的个体，即形成初始群体。
例如，对于一个有7个需求点，用3辆汽车完成配送任务的问题，则可用1、2、·
、9（8、9表示配送中心）这9个自然数的随机排列，表示物流配送路径方案。
如个体129638547表示的的配送路径方案为：
路径1：
0-1-2-9（0），路径2：
9（0）-6-3-8（0），路径3：
8（0）-5-4-7-0，共有3条配送路径；
个体573894216表示的配送路径方案为：
0-5-7-3-8（0），路径2：
9（0）-4-2-1-6-0，共有2条配送路径。
（3）适应度评估。
对于某个个体所对应的配送路径方案，要判定其优劣，一是要看其是否满足配送的约束条件；
二是要计算其目标函数值（即各条配送路径的长度之和）。
根据配送路径优化问题的特点所确定的编码方法，隐含能够满足每个需求点都得到配送服务及每个需求点仅由一辆汽车配送的约束条件，但不能保证满足每条路径上各需求点需求量之和不超过汽车载重量及每条配送路线的长度不超过汽车一次配送的最大行驶距离的约束条件。
为此，对每个个体所对应的配送路径方案，要对各条路径逐一进行判断，看其是否满足上述两个约束条件，若不满足，则将该条路径定为不可行路径，最后计算其目标函数值。
对于某个个体j，设其对应的配送路径方案的不可行路径数为Mj（Mj=0表示该个体对应一个可行解），其目标函数值为Zj，则该个体的适应度Fj可用下式表示：
式中，G为对每条不可行路径的惩罚权重，可根据目标函数的取值范围取一个相对较大的正数。
（4）选择操作。
将每代群体中的N个个体按适应度由大到小排列，排在第一位的个体性能最优，将它复制一个直接进入下一代，并排在第一位。
下一代群体的另N-1个个体需要根据前代群体的N个个体的适应度，采用赌轮选择法产生。
具体地说，就是首先计算上代群体中所有个体适应度的总和（ΣFj），再计算每个个体的适应度所占的比例（Fj/ΣFj），以此作为其被选择的概率。
这样选择方法既可保证最优个体生存至下一代，又能保证适应度较大的个体以较大的机会进入下一代。
（5）交叉操作。
对通过选择操作产生的新群体，除排在第一位的最优个体外，另N-1个个体要按交叉概率Pc进行配对交叉重组。
我们采用了一种类似OX法[2]的交叉方法，现举例说明之：
①随机在父代个体中选择一个交配区域，如两父代个体及交配区域选定为：
A=47|8563|921，B=83|4691|257；
②将B的交配区域加到A的前面，A的交配区域加到B的前面，得：
A’=4691|478563921，B’=8563|834691257；
③在A’、B’中自交配区域后依次删除与交配区相同的自然数，得到最终的两个体为：
A”=469178532，B”=856349127。
与其他交叉方法相比，这种方法在两父代个体相同的情况下仍能产生一定程度的变异效果，这对维持群体的多样化特性有一定的作用。
（6）变异操作。
由于在选择机制中采用了保留最佳样本的方式，为保持群体内个体的多样化，我们采用了连续多次对换的变异技术，使个体在排列顺序上的有较大变化。
变异操作是以概率Pm发生的，一旦变异操作发生，则用随机方法产生交换次数J，对所需变异操作的个体的基因进行J次对换（对换基因的位置也是随机产生的）。
根据上述遗传算法编制的Matlab算法进行求解
3Matlab算法
%建立m文件create_permutations.m
%------------------------------------------
functionpop=create_permutations（NVARS,FitnessFcn,options）
totalPopulationSize=sum（options.PopulationSize）;
n=NVARS;
pop=cell（totalPopulationSize,1）;
fori=1:
totalPopulationSize
pop{i}=randperm（n）;
end
%crossover_permutation.m
functionxoverKids=crossover_permutation（parents,options,NVARS,...
FitnessFcn,thisScore,thisPopulation）
nKids=length（parents）/2;
xoverKids=cell（nKids,1）;
%Normallyzeros（nKids,NVARS）;
index=1;
fori=1:
nKids
%hereiswherethespecialknowledgethatthepopulationisacell
%arrayisused.Normally,thiswouldbethisPopulation（parents（index）,:
）;
parent=thisPopulation{parents（index）};
index=index+2;
%Flipasectionofparent1.
p1=ceil（（length（parent）-1）*rand）;
p2=p1+ceil（（length（parent）-p1-1）*rand）;
child=parent;
child（p1:
p2）=fliplr（child（p1:
p2））;
xoverKids{i}=child;
%Normally,xoverKids（i,:
%mutate_permutation.m
functionmutationChildren=mutate_permutation（parents,options,NVARS,...
FitnessFcn,state,thisScore,thisPopulation,mutationRate）
mutationChildren=cell（length（parents）,1）;
%Normallyzeros（length（parents）,NVARS）;
length（parents）
parent=thisPopulation{parents（i）};
%NormallythisPopulation（parents（i）,:
）
p=ceil（length（parent）*rand（1,2））;
child（p
（1））=parent（p
（2））;
child（p
（2））=parent（p
（1））;
mutationChildren{i}=child;
%NormallymutationChildren（i,:
%traveling_salesman_fitness.m
functionscores=traveling_salesman_fitness（x,distances）
scores=zeros（size（x,1）,1）;
forj=1:
size（x,1）
%arrayisused.Normally,thiswouldbepop（j,:
p=x{j};
f=distances（p（end）,p
（1））;
fori=2:
length（p）
f=f+distances（p（i-1）,p（i））;
scores（j）=f;
%画图的traveling_salesman_plot.m
functionstate=traveling_salesman_plot（options,state,flag,locations）
[unused,i]=min（state.Score）;
genotype=state.Population{i};
plot（locations（:
1）,locations（:
2）,'
ro'
holdon
plot（locations（genotype,1）,locations（genotype,2））;
holdoff
%正文
x=[5;
5;
3;
-1;
0;
-3;
1;
-2;
2;
4];
y=[2;
-4;
-5;
-5];
z=[4,1,3,4,5,2,5,4,3,5,2,1,2,5,3]
locations=[xy];
distances=zeros（15）;
forcount1=1:
15,
forcount2=1:
count1,
x1=locations（count1,1）;
y1=locations（count1,2）;
x2=locations（count2,1）;
y2=locations（count2,2）;
distances（count1,count2）=sqrt（（x1-x2）^2+（y1-y2）^2）;
distances（count2,count1）=distances（count1,count2）;
end;
FitnessFcn=@（x）traveling_salesman_fitness（x,distances）;
my_plot=@（options,state,flag）traveling_salesman_plot（options,...
state,flag,locations）;
options=gaoptimset（'
PopulationType'
'
custom'
'
PopInitRange'
...
[1;
15]）;
options=gaoptimset（options,'
CreationFcn'
@create_permutations,...
'
CrossoverFcn'
@crossover_permutation,...
MutationFcn'
@mutate_permutation,...
PlotFcn'
my_plot,...
Generations'
500,'
PopulationSize'
60,...
StallGenLimit'
200,'
Vectorized'
on'
numberOfVariables=15;
[x,fval,reason,output]=ga（FitnessFcn,numberOfVariables,options）
Z=[62.5,61.1,60.7,59.2,58.6,57.5,53.6,52.1,51.5,50.7]
4小组分工
1熟悉使用Matlab：
2熟悉掌握遗传算法：
升级会员 