粒子群算法求解三维装箱问题

2023-07-21 15:18:40

粒子群算法求解三维装箱问题

三维装箱问题介绍
粒子群算法
- 参数设置
- 粒子群代码
结果展示
店铺地址
欢迎加入群智能讨论群

三维装箱问题介绍

三维装箱问题定义为：给定 i 种长宽高为 Li、Wi、 Hi 的集装箱和 j 种长宽高为 lj、wj、hj ，重量为 mj 的货物，在考虑一定约束条件的同时，最大化地利用集装箱的体积或载重量，将货物装载到一个或多个集装箱中。集装箱装载问题可以根据集装箱数量、集装箱形状、装载维度、装载目标、货物种类、货物到达情况等进行分类。

基本约束条件

（1）体积约束
集装箱装载货物的过程中，空间不断缩小，集装箱体积与货物体积是装载可行性的主要标准。
（2）重量约束
货物的总重量小于或等于集装箱的最大承载量时，货物才可装入集装箱中。
（3）重量平衡约束
为了使集装箱均匀地装载货物，在制定装载方案时，应充分考虑货物摆放的重心约束。集装箱内货物的稳定有助于提高交通运输的稳定性，因此尽量减少货物之间的空隙，同时将密度较大并且质量较大的货物放入最底端，以保证集装箱的稳定性。
（4）方向约束
在确定货物装载顺序时，还需考虑特定类型货物的摆放方向，如果客户没有提出任何方向限制，那么可以根据装载需求进行装载，以提高装载效率。
（5）承载约束
在进行分层装载时，要充分考虑货物的最大承载压力，否则下面的货物会因为承载压力不够而导致损坏，因此装载层数以及装载顺序都需要被限制。
（6）装载顺序约束
不同订单的货物应按照不同的装载优先级进行处理。

模型假设

本文主要针对集装箱装载布局进行研究，将体积约束、重量约束、重量平衡约束、方向约束作为约束条件。为了提高集装箱的利用效率，将集装箱体积利用率最大作为目标函数。现将模型做如下假设
（1）集装箱形状假设为长方体。
（2）集装箱内货物的位置没有区域限制。
（3）货物均为长方体且质量分布均匀。
（4）货物可以保持其形状和尺寸，不会由于堆叠而变形，不是危险品等特殊货物。
（5）不考虑途中货物的加载与卸载。

模型建立

粒子群算法

粒子群算法（ Particle Swarm Optimization, PSO）最早是由Eberhart和Kennedy于1995年提出，它的基本概念源于对鸟群觅食行为的研究。PSO算法就从鸟类这种生物种群的觅食行为特性中得到启发并用于求解优化问题。

用一种粒子来模拟上述的鸟类个体，每个粒子可视为N维搜索空间中的一个搜索个体，粒子的当前位置即为对应优化问题的一个候选解，粒子的飞行过程即为该个体的搜索过程．粒子的飞行速度可根据粒子历史最优位置和种群历史最优位置进行动态调整．粒子仅具有两个属性：速度和位置，速度代表移动的快慢，位置代表移动的方向。每个粒子单独搜寻的最优解叫做个体极值，粒子群中最优的个体极值作为当前全局最优解。不断迭代，更新速度和位置。最终得到满足终止条件的最优解。

参数设置

%% Problem Definition

model=SelectModel();                        % Select Model

CostFunction=@(xhat) MyCost(xhat,model);    % Cost Function

VarSize=[model.N model.N];      % Decision Variables Matrix Size

nVar=prod(VarSize);             % Number of Decision Variables

VarMin=0;          % Lower Bound of Decision Variables
VarMax=1;          % Upper Bound of Decision Variables


%% PSO Parameters

MaxIt=250;      % Maximum Number of Iterations

nPop=150;        % Population Size (Swarm Size)

w=1;                % Inertia Weight
wdamp=0.99;         % Inertia Weight Damping Ratio
c1=1.5;             % Personal Learning Coefficient
c2=2.0;             % Global Learning Coefficient

粒子群代码

%% Initialization

empty_particle.Position=[];
empty_particle.Cost=[];
empty_particle.Sol=[];
empty_particle.Velocity=[];
empty_particle.Best.Position=[];
empty_particle.Best.Cost=[];
empty_particle.Best.Sol=[];

particle=repmat(empty_particle,nPop,1);

BestSol.Cost=inf;

for i=1:nPop
    
    % Initialize Position
    particle(i).Position=unifrnd(VarMin,VarMax,VarSize);
    
    % Initialize Velocity
    particle(i).Velocity=zeros(VarSize);
    
    % Evaluation
    [particle(i).Cost, particle(i).Sol]=CostFunction(particle(i).Position);
    
    % Update Personal Best
    particle(i).Best.Position=particle(i).Position;
    particle(i).Best.Cost=particle(i).Cost;
    particle(i).Best.Sol=particle(i).Sol;
    
    % Update Global Best
    if particle(i).Best.Cost<BestSol.Cost
        
        BestSol=particle(i).Best;
        
    end
    
end

BestCost=zeros(MaxIt,1);


%% PSO Main Loop

for it=1:MaxIt
    
    for i=1:nPop
        
        % Update Velocity
        particle(i).Velocity = w*particle(i).Velocity ...
            +c1*rand(VarSize).*(particle(i).Best.Position-particle(i).Position) ...
            +c2*rand(VarSize).*(BestSol.Position-particle(i).Position);
        
        % Apply Velocity Limits
        particle(i).Velocity = max(particle(i).Velocity,VelMin);
        particle(i).Velocity = min(particle(i).Velocity,VelMax);
        
        % Update Position
        particle(i).Position = particle(i).Position + particle(i).Velocity;
        
        % Velocity Mirror Effect
        IsOutside=(particle(i).Position<VarMin | particle(i).Position>VarMax);
        particle(i).Velocity(IsOutside)=-particle(i).Velocity(IsOutside);
        
        % Apply Position Limits
        particle(i).Position = max(particle(i).Position,VarMin);
        particle(i).Position = min(particle(i).Position,VarMax);
        
        % Evaluation
        [particle(i).Cost, particle(i).Sol] = CostFunction(particle(i).Position);
        
        % Mutation
        NewParticle=particle(i);
        NewParticle.Position=Mutate(particle(i).Position, model);
        [NewParticle.Cost, NewParticle.Sol]=CostFunction(NewParticle.Position);
        if NewParticle.Cost<=particle(i).Cost || rand < 0.1
            particle(i)=NewParticle;
        end
        
        % Update Personal Best
        if particle(i).Cost<particle(i).Best.Cost
            
            particle(i).Best.Position=particle(i).Position;
            particle(i).Best.Cost=particle(i).Cost;
            particle(i).Best.Sol=particle(i).Sol;
            
            % Update Global Best
            if particle(i).Best.Cost<BestSol.Cost
                
                BestSol=particle(i).Best;
                
            end
            
        end
        
    end
    
    % Local Search based on Mutation
    for k=1:3
        NewParticle=BestSol;
        NewParticle.Position=Mutate(BestSol.Position, model);
        [NewParticle.Cost, NewParticle.Sol]=CostFunction(NewParticle.Position);
        if NewParticle.Cost<=BestSol.Cost
            BestSol=NewParticle;
        end
    end

    BestCost(it)=BestSol.Cost;
    
    disp(['Iteration ' num2str(it) ': Best Cost = ' num2str(BestCost(it))]);
    
    w=w*wdamp;
    
    % Plot Best Solution
    figure(1);
    PlotSolution(BestSol.Sol,model);
    pause(0.01);
    
end

%% Results

figure;
plot(BestCost,'LineWidth',2);
xlabel('Iteration');
ylabel('Best Cost');

结果展示

店铺地址

欢迎加入群智能讨论群

新群人少，请多多关照
QQ群：688369315

码农公寓