www.pudn.com > ZHINENGSHUIDI.rar > 智能水滴.txt, change:2016-05-26,size:7613b


clear all; 
clc; 
format short g; 
data=[ 
    100 100 0   0    0   40 
    60 100 10 0.2  0   3 
    20 110 15 0.3  0 4 
    160 150 21 0.3  1 6 
    160 110 16 0.4  0 4 
    30 20 25 0.3  1 4 
    100 60 22 0.2  0 6 
    100 170 15 0.1  0 5 
    30 10 12 0.4  0 6 
    60 50 15 0.3  1 7 
    160 160 20 0.2  0 6 
    50 140 23 0.3  0 6]; 
% 配送中心及各个需求点之间的距离矩阵D 
D=squareform(pdist(data(:,1:2),'euclidean')); 
% 车辆的单位行驶成本: h 
% 动用每辆车的固定成本:R. 
% 车辆的行驶速度v; 
% 车辆的最大装载量 Qmax。 
h=20;R=100;v=50;Qmax=50;epsilon=0.001; 
% 车辆在配送中心及各个需求点之间行驶的时间矩阵 T 
T=D/v; 
% 最大迭代次数 
Iter=80; 
% 水滴个数N 
N=size(data,1); 
% 速度更新参数: 
av=1;bv=0.01;cv=1; 
% 泥土量更新参数: 
as=1;bs=0.01;cs=1; 
% 局部泥土更新权系数 
alpha=0.9; 
% 全局泥土更新权系数 
beta=0.9; 
% 任意两点间的初始泥土量 Initsoil 
Initsoil=1000; 
% 初始泥土量矩阵W ??? 
W=ones(N)*1000; 
% 每个水滴的初始速度InitVel; 
InitVel=100; 
% 全局最优目标函数值 
TotalZ=1000000; 
% 全局最优路径 
TotalRoute=[]; 
% 主程序 
t=0; 
WaterDrop(1,N)=struct('SW',[],... % 水滴对应的初始泥土量矩阵 
    'Source',[],... % 水滴的出发点为1; 即配送中心 
    'Target',[],... % 
    'VisitNode',[],... % 已访问过的点序列 (访问路径) 
    'UnvisitNode',[],... % 未访问过的点的集合 
    'Vel',[],... % 水滴的初始速度 
    'Soil',[],... % 水滴携带的初始泥土量 
    'Q',[],... % 水滴出发时的装载量 
    'S',[],... % 水滴到达source(k)点的时刻 
    'ZZ',[],... %水滴对应的目标函数初始值 
    'FK',[]); % 从source(k)出发可以去的下一个需求点的集合 FV 
q=data(:,3); % 每个需求点的需求量 
ss=data(:,4); % 每个需求点的服务时间 
E=data(:,5); % 每个需求点的时间窗下限 
L=data(:,6); % 每个需求点的时间窗上限 
I=1:N; 
while t < Iter 
    % 设置初始动态变量: 
    % 本次迭代的最优目标函数值 
    Z=1000000; 
    % 本次迭代的最优路径 
    Route=[]; 
    for k=1:N 
        WaterDrop(k).SW=W; 
        WaterDrop(k).Source=1; 
        WaterDrop(k).VisitNode=[1]; 
        WaterDrop(k).UnvisitNode=I;   
        WaterDrop(k).Vel= InitVel; 
        % 水滴携带的初始泥土量 
        WaterDrop(k).Soil=0; 
        % 水滴出发时的装载量 
        WaterDrop(k).Q(WaterDrop(k).Source)=0; 
        % 水滴到达source(k)点的时刻; 
        WaterDrop(k).S(WaterDrop(k).Source)=0; 
        % 第k个水滴对应的目标函数初始值 
        WaterDrop(k).ZZ=0;         
    end 
    for k=1:N 
        while WaterDrop(k).Source~=1 || ~isequal(WaterDrop(k).UnvisitNode,[1]) 
            WaterDrop(k).FK=[]; 
            if WaterDrop(k).Source==1 
                alt=2; 
            else 
                alt=1; 
            end              
            for i=alt:N 
                if sum(ismember(WaterDrop(k).UnvisitNode,i)) 
                    WaterDrop(k).Q(i)=WaterDrop(k).Q(WaterDrop(k).Source)+q(i); 
                    WaterDrop(k).S(i)=WaterDrop(k).S(WaterDrop(k).Source)+ss(WaterDrop(k).Source)+T(WaterDrop(k).Source,i);  
                    if WaterDrop(k).Q(i)<Qmax && WaterDrop(k).S(i)>=E(i) && WaterDrop(k).S(i)<=L(i)  
                        WaterDrop(k).FK=[WaterDrop(k).FK,i]; 
                    end 
                end 
            end 
            % 计算去下一个可以服务的需求点的概率 
            % 判断从source(k)到下一个可以服务的需求点的路径上泥土量的最小值是否小于0 
            Minsoil=0; 
            for u=1:N                           
                if sum(ismember(WaterDrop(k).FK,u)) 
                    if WaterDrop(k).SW(WaterDrop(k).Source,u)<Minsoil 
                        Minsoil=WaterDrop(k).SW(WaterDrop(k).Source,u); 
                    end 
                end 
            end 
            % 求下一个可以服务需求点对应的函数f之和 
            SumF=0; 
            for u=1:N 
                if sum(ismember(WaterDrop(k).FK,u)) 
                    g(WaterDrop(k).Source,u)=WaterDrop(k).SW(WaterDrop(k).Source,u)-Minsoil; 
                    f(WaterDrop(k).Source,u)=1/(0.01+g(WaterDrop(k).Source,u)); 
                    SumF=SumF+f(WaterDrop(k).Source,u); 
                end 
            end 
            % 求可以服务需求点对应的概率 
            P=[]; 
            U=[]; 
            for u=1:N 
                if sum(ismember(WaterDrop(k).FK,u)) 
                    P=[P,f(WaterDrop(k).Source,u)/SumF]; 
                    U=[U,u]; 
                end 
            end 
            % 按照概率P(source(k),u), 用轮盘赌法从FV(k) 集合中随机选择一个点 
            WaterDrop(k).Target=U(RoutedGame(P)); 
            % 更新水滴的速度 
            WaterDrop(k).Vel=WaterDrop(k).Vel+av/(bv+cv*WaterDrop(k).SW(WaterDrop(k).Source,WaterDrop(k).Target)^2); 
            Maxtime=max(epsilon,WaterDrop(k).Vel); 
            % 计算水滴流动到目标点需要的时间 
            TT(WaterDrop(k).Source,WaterDrop(k).Target)=D(WaterDrop(k).Source,WaterDrop(k).Target)/Maxtime; 
            % 计算水滴携带泥土的增量 
            DeltaSW(WaterDrop(k).Source,WaterDrop(k).Target)= as/(bs+cs*TT(WaterDrop(k).Source,WaterDrop(k).Target)^2); 
            % 更新水滴流过的路径上的泥土量 
            WaterDrop(k).SW(WaterDrop(k).Source,WaterDrop(k).Target)=... 
                (1-alpha)*WaterDrop(k).SW(WaterDrop(k).Source,WaterDrop(k).Target)-alpha*DeltaSW(WaterDrop(k).Source,WaterDrop(k).Target); 
            % 更新水滴携带的泥土量 
            WaterDrop(k).Soil=WaterDrop(k).Soil+DeltaSW(WaterDrop(k).Source,WaterDrop(k).Target); 
            if  WaterDrop(k).Target==1 
                % (有序集合)配送车辆返回配送中心 
                WaterDrop(k).VisitNode=[WaterDrop(k).VisitNode,WaterDrop(k).Target]; 
                % 目标函数中增加动用一辆车的固定成本(表示形成了一辆车的回路) 
                WaterDrop(k).ZZ=WaterDrop(k).ZZ+h*D(WaterDrop(k).Source,WaterDrop(k).Target)+R; 
                WaterDrop(k).Source=WaterDrop(k).Target; 
                WaterDrop(k).Q(WaterDrop(k).Source)=0; 
                WaterDrop(k).S(WaterDrop(k).Source)=0; 
            else 
                % 访问Target(k)点,已访问点增加1个 
                WaterDrop(k).VisitNode=[WaterDrop(k).VisitNode,WaterDrop(k).Target]; 
                % 未访问点减少一个 
                WaterDrop(k).UnvisitNode(WaterDrop(k).UnvisitNode==WaterDrop(k).Target)=[];  %%%%%????? 
                % 目标函数只增加车辆运行成本 
                WaterDrop(k).ZZ=WaterDrop(k).ZZ+h*D(WaterDrop(k).Source,WaterDrop(k).Target); 
                % 计算第k辆车到达下一个点时的装载量 
                WaterDrop(k).Q(WaterDrop(k).Target)=WaterDrop(k).Q(WaterDrop(k).Source)+q(WaterDrop(k).Target); 
                % 计算第k辆车到达下一个点的时刻 
                WaterDrop(k).S(WaterDrop(k).Target)=WaterDrop(k).S(WaterDrop(k).Source)+... 
                    ss(WaterDrop(k).Source)+T(WaterDrop(k).Source,WaterDrop(k).Target); 
                % 将下一个点作为出发点 
                WaterDrop(k).Source=WaterDrop(k).Target; 
            end 
            %如果第k个水滴的路径已经完成(即所有需求点都被服务完毕) 
        end 
        if WaterDrop(k).ZZ<Z 
            Z=WaterDrop(k).ZZ; 
            Route=WaterDrop(k).VisitNode; 
            Soil=WaterDrop(k).Soil; 
        end 
    end 
    % 对本次循环得到的最优解对应的路径Route上的泥土量进行更新 
    M=size(Route,2); 
    % 路径以外的边上泥土量不变。 
    for i=1:M-1 
        W(Route(i),Route(i+1))=(1+beta)* W(Route(i),Route(i+1))-beta*Soil/(M-1); 
    end 
    if Z<TotalZ 
        TotalZ=Z; 
        TotalRoute=Route; 
    end 
    %更新迭代次数 
    t=t+1; 
end 
TotalZ 
TotalRoute 
 
========================================= 
 
function [j]=RoutedGame(P) 
P=[0,P]; 
cdf=cumsum(P); 
N=length(cdf); 
u=rand(1); 
for i=1:N-1 
    if u>cdf(i) && u<cdf(i+1) 
        j=i; 
    end 
end