【VRP】遗传算法求解单中心VRP问题【Matlab104期】

一、简介

1 车辆路径问题概述
车辆路径问题(vehicle routing problem,VRP)给定一组有容量限制的车辆的集合、一个物流中心(或供货地)、若干有供货需求的客户,组织适当的行车路线,使车辆有序地通过所有的客户,在满足一定的约束条件(如需求量、服务时间限制、车辆容量限制、行驶里程限制等)下,达到一定的目标(如路程最短、费用极小、时间尽量少、使用车辆数尽量少等)。
以配送总里程最短为目标函数,约束条件满足:(1)每条配送路径上各客户的需求量之和不超过配送车辆的载重量;(2)每条配送路径的长度不超过配送车辆一次配送的最大行驶距离;(3)每个客户的需求必须满足,且只能由一台配送车辆送货。

2 遗传算法
遗传算法(Genetic Algorithm, GA)是一种较为经典的智能优化算法,经大量的研究表明,其在求解离散组合优化问题中有着优异的表现。遗传算法的思想为优胜劣汰,通过交叉操作、变异操作获得多样性的解,在下一代中保留目标函数最优的解,并通过轮盘赌方式选择下一代个体,不断循环迭代,从而不断优化问题的解。本文采用Matlab R2010b编程实现,遗传算法求解车辆路径问题的具体内容及步骤如下:
2.1 编码操作
车辆路径问题为离散优化问题,结合约束条件3:每个客户的需求必须满足,且只能由一台配送车辆送货,可以以客户整数编号的排序进行编码,保证每个客户编号能且只能出现一次。比如说:客户数量为8,则编码的染色体可以为1-2-3-4-5-6-7-8。

2.2 解码操作
解码操作需要在满足约束条件1、2的前提下,将染色体解码为车辆的配送路径,为计算目标值做好准备。根据排列顺序进行解码,主要判断该客户加入到车辆配送路径后,是否满足该车的最大行驶距离,是否满足该车的最大载重量。比如说染色体1-2-3-4-5-6-7-8,第1辆车路径:将客户1加入到该车的路径中,则第1辆车的行驶路线为0-1-0,表示,该车从物流中心0出发,将货物运到客户1,再返回物流中心,计算行驶距离是否满足第1辆车的最大行驶距离,同时计算运货量是否满足第1辆车的最大载货量,再确定客户2如果加入第1辆车的路径是否满足以上2个条件,如果满足,则第1辆车的行驶路线为0-1-2-0,依次类推,如果不满足其中的1个条件,则需要增加1辆车即为从物流中心出发的第2条行驶路线。

2.3 计算目标值
根据解码出来的车辆行驶路径,计算目标值即为总配送里程。但需要判断解码出来的行驶路径的数量是否超过总车辆数,若未超过则按所有车辆路径相加得到总配送里程,若超过总车辆数,则说明该配送路径不可行,该解为不可行解,因该问题为最小化优化问题,可通过罚函数增大目标值来淘汰掉该不可行解。

2.4 交叉操作
交叉操作是根据两个父代的染色体信息,根据交叉概率Pc交换某些片段,从而使父代的信息能够遗传给子代,本质是根据父代的染色体信息产生子代(新解),交叉操作的实现方式有多种,本文给出了一种交换染色体片段的交叉操作,如下图所示。
【VRP】遗传算法求解单中心VRP问题【Matlab104期】

2.5. 变异操作
变异操作是在父代的染色体信息基础上,根据变异概率Pm改变某些基因位,从而使整个染色体发生变化,该操作对染色体的改变程度小于交叉操作,变异操作的实现方式有多种,本文给出了一种单点位基因突变的变异操作,如下图所示。
【VRP】遗传算法求解单中心VRP问题【Matlab104期】

2.6. 选择操作
选择操作以目标值较好的染色体及随机产生的新染色体组成,在确保优良基因能传递给下一代的基础上,通过随机产生的新解扩大染色体的多样性。
2.7. 算法流程
遗传算法求解车辆路径问题的算法步骤如下:
【VRP】遗传算法求解单中心VRP问题【Matlab104期】

3、算法验证
实例1:某物流中心有2台配送车辆,其载重量均为8t,车辆每次配送的最大行驶距离为50Km,配送中心(编号为0)与8个客户之间及8个客户相互之间的距离dij、8个客户的货物需求量qj(i, j=1,2,……,8)见下表1。要求合理安排车辆配送路线,使配送总里程最短。
【VRP】遗传算法求解单中心VRP问题【Matlab104期】
根据以上问题的数据信息,设置好遗传算法的参数,通过遗传算法求解该车辆路径问题得到最有解为【1-3-5-6-4-7-2-8】,最短距离为【69.5】,解码操作得到的车辆路径为【0-1-3-5-6-0】、【0-4-7-2-8-0】。

二、源代码

 clc
clear
close all;
tic;
%%
%算法参数
population_num=80;%种群规模
Max_gen=200;%迭代次数
Pc=0.9;%交叉概率
Pm=0.09;%变异概率
%%
%问题参数
%车辆数量Car_num=2
%客户数量Customer_num=8
%车辆容量capacity_max=8
%行驶距离distance_max=50
Car_num=2;
Customer_num=8;
capacity_max=8;
distance_max=50;
load Demand %客户的需求
load Distance %客户间的距离
load X %物流中心到客户间的距离
%%
%种群初始化
population=zeros(population_num,Customer_num);
for i=1:population_num
     population(i,:)=randperm(Customer_num);
end
%%
y=1;%循环计数器
 while y<Max_gen
     %交叉
     [new_pop_intercross]=Mating_pool(population_num,population,Pc);
     %变异
     [new_pop_mutation]=Mutation(new_pop_intercross,Pm);
     %计算目标函数
     mutation_num=size(new_pop_mutation,1);
     Total_Dis=[];
     for k=1:mutation_num
     [Result]=decode(new_pop_mutation(k,:),distance_max,capacity_max);
     [Total_Dis(k,1)]=parameter(Result,Customer_num,Car_num);
     end
     %更新种群
     new_pop_new=zeros(population_num,Customer_num);
     [Total_Dissort, index] = sort(Total_Dis);
     for k=1:population_num
         new_pop_new(k,:)=new_pop_mutation(index(k),:);
     end
     population=new_pop_new;
     %迭代次数加一
     y=y+1;
 end
 function [new_pop_intercross]=Mating_pool(population_num,population,Pc)
%%
%输入:population,population_num,Pc
%输出:1.new_popopulation_intercross
%     2.c3,配对池:随机将种群population两两配对
%     3.pool
%%
pl=randperm(population_num);
num=population_num/2;
c3=zeros(2,num);
pool=[];
new_pop_intercross=population;
for kj=1:num
    c3(1,kj)=pl(2*kj-1);
    c3(2,kj)=pl(2*kj);
end%生成“配对池c3”

%%判断“配对池c3”每一对个体的随机数是否小于交叉概率Pc
rd=rand(1,num);
for kj=1:num
    if rd(kj)<Pc
       pool=[pool,c3(:,kj)];
    end
end
%%判断配对池每一对个体的随机数是否小于交叉概率Pc,若小于,保存到“产子池pool”1

pool_num=size(pool,2);
for kj=1:pool_num
    c1=population(pool(1,kj),:);
    c2=population(pool(2,kj),:);
    [new_c1,new_c2]=cross(c1,c2);
    new_pop_intercross(pool(1,kj),:)=new_c1;
    new_pop_intercross(pool(2,kj),:)=new_c2;
end
end
function [Total_Dis]=parameter(Result,Customer_num,Car_num)
%% 解码1
if Result(Customer_num,2)<=Car_num
Current_Workstation=1;
Total_Dis=0;
for i=1:Customer_num
    if Result(i,2)==Current_Workstation;
        continue
    else
        Total_Dis=Total_Dis+Result(i-1,3);
        Current_Workstation=Current_Workstation+1;
    end  
end
Total_Dis=Total_Dis+Result(Customer_num,3);
else
    Total_Dis=10000;%引入罚函数
end
    
 

三、运行结果

【VRP】遗传算法求解单中心VRP问题【Matlab104期】

四、备注

版本:2014a
完整代码或代写加QQ912100926

上一篇:VRP系统管理


下一篇:【VRP问题】基于粒子群算法求解VRPTW模型matlab源码