无时间窗vrp

无时间窗vrp车场多车型车辆路径问题的改进遗传算法,车辆路径问题(Vehicle routing problem,VRP)由Dantzing和Ramser于1959年首次提出,它是指对一系列发货点(或收货点),组织适...

function VRP
tic
clc
clear
consudata =xlsread（‘data.xlsx‘‘sheet2‘‘A3:G13‘）;%读入客户信息
popsize=80;%种群规模
pc=0.85;%交叉概率
pm=0.015;%变异概率
elite_sp=0.1;%精英保留概率
N=1000;%迭代次数
Q=1.9;%车辆的载重量
p1=8;%单位距离成本
p2=0.65;%单位车辆成本
alpha=1;%距离成本权重系数
beta=1;%车辆成本权重系数
[arry_xarry_y]=size（consudata）;
chromlength=arry_x-1;%客户数量，即为染色体长度  
%通过系数为三维矩阵，行和列表示客户号，高k表示把时间分为k段
for i=1:arry_x
    for j=i:arry_x
        Distance（ij）=sqrt（（consudata（i2）-consudata（j2））^2+（consudata（i3）-consudata（j3））^2）;
        Distance（ji）=Distance（ij）;
    end
end
%随机产生初始种群
pop=initpop（popsizechromlength）;
for n=1:N %开始循环 
    %计算目标函数值
    [arry_xarry_y]=size（pop）;
    for i=1:arry_x
        unit=pop（i:）;
        [rout]=decode（unitconsudataQ）;%解码
        discost_value=count_discost（routDistancep1）;%计算距离成本
        vehcost_value=count_vehcost（routp2）;%计算车辆成本
        objvalue（i）=sum（alpha*discost_value+beta*vehcost_value）;%按照权重计算总成本
    end
    %计算个体的适应值
    fitvalue=calfitvalue（objvalue）;
    %轮盘赌选择，得到新的种群
    oppop=selection（popfitvalueelite_sp）;
    %交叉算子，得到新种群
    cropop=crossover（oppoppc）;
    %变异算子，得到新种群
    m_newpop=mutation（cropoppm）;
    %求出种群中最大适应值及个体
    [bestindividualbestfit]=best（popfitvalue）;
    %存储进化代数，绘制结果图
    generation（n）=n;
    %没代最优适应值转化为目标函数值
    final_objvalue（n）=10000./bestfit;
    %存储每带最优个体
    final_individual（n:）=bestindividual;
    %经过遗传操作后的种群替代上一个种群
    pop=m_newpop;
end%循环结束
[output_objvaluefinal_line]=min（final_objvalue）;
output_gengration=final_line%输出获得最优解的代数
output_objvalue%输出最优值
[output_rout]=decode（final_individual（final_line:）consudataQ）;
output_rout%输出最优路线
[arry_xarry_y]=size（output_rout）;
for i=1:arry_y-1
    distance1（:i）=diag（Distance（output_rout（:i）+1output_rout（:i+1）+1 ））;
end
output_distance=sum（sum（distance12））%输出最优路线的车辆行驶距离
plot（generationfinal_objvalue‘B-‘）
%title（‘进化代数与目标函数值关系图‘）
xlabel（‘进化代数‘）
ylabel（‘目标函数值‘）
figure
%提取最优路线的纵横坐标并绘制路线图
[arry_xarry_y]=size（output_rout）;
output_rout=reshape（output_rout‘1arry_x*arry_y）;
rout_x=consudata（output_rout（1:）+12）;
rout_y=consudata（output_rout（1:）+13）;
plot（rout_xrout_y‘b-o‘）
for i=1:11
    text（consudata（i2）+10consudata（i3）+1num2str（i-1））;
    %set（gca‘Fontsize‘15）
title（‘配送路线图‘）
xlabel（‘客户X轴坐标‘）
ylabel（‘客户Y轴坐标‘）
end
toc
end

%种群初始化
function pop=initpop（popsizechromlength）
pop=zeros（popsizechromlength）;
for i=1:popsize
    pop（i:）=randperm（chromlength）;
end
end

%按照距离及时间窗解码
function [routt_arrival]=decode（unitconsudataQ）
global time;
[arry_xarry_yarry_z]=size（time）;
[arry_xarry_y]=size（unit）;
load=consudata（unit（1）+14）;
time1=0;
i=2;
j=1;
k=2;
rout（11）=unit（1）;
while i<=arry_y
    load=load+consudata（unit（i）+14）;
    %检查载量和时间窗约束
    if load        rout（jk）=unit（i）;
    else
        k=1;
        j=j+1;
        rout（jk）=unit（i）;
        load=consudata（unit（i）+14）;
    end
    k=k+1;
    i=i+1;
end
[arry_xarry_y]=size（rout）;
rout

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       5938  2018-04-24 20:40  vrp.m

     文件      13792  2018-04-24 20:22  data2.xlsx

----------- ---------  ---------- -----  ----

                19730                    2