VRP 解决车辆路径问题使用矩阵蚂蚁算法

解决车辆路径问题使用矩阵蚂蚁算法，车辆调度问题（Vehicle Routing Problem，VRP）是一个典型的NP 难题，只有在需点数和路段数较少时才有可能寻求其精确解，一般情况下，很难得到全局最优解或满意解

%%
%--------------------------------------------------------------------------
%%参数说明
%%G_K:各代最优车辆数目
%%G_best_route：各代最优路线
%%G_best_length：各代最优路线长度
%%K：最优车辆数目
%%best_route：最优路线
%%best_length：最优路线长度
%%length_ave：各代平均长度
%%C：DC和工厂的坐标
%%NC_max：最大迭代次数
%%m：蚂蚁数目
%%Alpha：重要度系数
%%Beta：能见度系数
%%Rho：挥发度系数
%%Q：信息更新参数
%%W:车辆载重量
%%
%%第一步 初始化变量和系数

m=16;Alpha=1;Beta=2;gama=2;Rho=0.3;NC_max=200;Q=100;W=8;qq=0.05; 
C=[0 0
   1 2
   2 0
  4 1
  3 4
   5 3
   0 6
   1 -2
   6 1
   5 -3
   0 -4
   3 -5
   -2 -6
   -4 -5
   -3 -3
   -4 -2
   -5 3
   -1 3
   -4 4
  -2 -1]; 
t=[0 1.3 1.8 1 1.7 1.5 1.2 2.5 2.7 1.7 0.6 0.2 2.4 1.9 2.0 0.7 0.5 2.2 3.1 1.0];

%构造仓库和工厂等之间的距离矩阵

n=size（C1）;%n表示问题的规模（城市个数） 
D=zeros（nn）;%D表示完全图的赋权邻接矩阵 
for i=1:n 
for j=1:n 
if i~=j 
D（ij）=（（C（i1）-C（j1））^2+（C（i2）-C（j2））^2）^0.5; 
else 
D（ij）=eps; 
end 
D（ji）=D（ij）; 
end 
end 

%构造节省量矩阵
U=zeros（nn）;%U表示工厂之间的连接和其与仓库之间连接能节省的距离
for i=1:n 
for j=1:n 
if i~=j 
U（ij）=D（i1）+D（j1）-D（ij）;
else 
U（ij）=eps; 
end 
U（ji）=U（ij）; 
end 
end 
load_w=0;
Eta=1./D;%Eta为启发因子，这里设为距离的倒数 
Tau=ones（nn）;%Tau为信息素矩阵 
Tabu=zeros（mn+20）;%存储并记录路径的生成 
NC=1;%迭代计数器 
G_best_route=[NC_maxn+20];%各代最佳路线 
G_best_length=inf.*ones（NC_max1）;%各代最佳路线的长度 
length_ave=zeros（NC_max1）;%各代路线的平均长度

%%第二步，把蚂蚁放到DC内
while NC<=NC_max%停止条件之一：达到最大迭代次数 
    Tabu（:1）=randint（m1[11]）;
%%第三步，m只蚂蚁按照要求的方法选择工厂，并完成周游 
for i=1:m
    visited=Tabu（i:）;
    visited=visited（visited>0）;
    to_visit=setdiff（1:nvisited）;
    c_temp=length（to_visit）;
    j=1;
       while j<=n
          if ~isempty（to_visit）
    %visit_thisant=[];
    %while to_visit~=[1]
    %for ee=1:（2*c_temp） 
   %while c_temp>=2
   %if length（to_visit）>1
    %visited=Tabu（i:）;
    %to_visit=setdiff（1:nvisited）;
    %to_visit=[1to_visit];
    %c_temp=length（to_visit）;
    %visit_thisant=[];
   % if c_temp~=1
        %for b=1:c_temp
            %if （load_w+t（to_visit（b）））<=W
                %visit_thisant=[visit_thisantto_visit（b）];
            %end
        %end
        %jj=visited（visited>0）;
%% 按照规则选下一个工厂或者是回到仓库
%for k=1:length（visit_thisant）
    for k=1:length（to_visit）
  x（k）=（Tau（visited（end）to_visit（k））^Alpha）*（Eta（visited（end）to_visit（k））^Beta）*（U（visited（end）to_visit（k））^gama）;
    end   
        ww=rand;
if ww    Select=find（max（x））;
    %Tabu（ilength（visited（visited>0））+1）=to_visit（Select（1））; 
else
x=x/（sum（x））; 
%按概率原则选取下一个城市 
xcum=cumsum（x）; 
Select=find（xcum>=rand）;
%Tabu（ilength（visited（visited>0））+1）=to_visi（Select（1））; 
end
if isempty（Select）
    Select=1;
    load_w=load_w+t（Select）;
else
load_w=load_w+t（to_visit（Select（1）））;
end
if load_w>W
    Select=1;
       j=j-1;
    load_w=0;
    Tabu（ilength（visited）+1）=Select（1）;
else
Tabu（ilength（visited）+1）=to_visit（Select（1））; 
end
%if Select（1）==1

%else
    %load_w=load_w+t（Select（1））;
%end
          end
    visited=Tabu（i:）;
    visited=visited（v

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        5414  2012-10-25 17:36  VRP.m