单品种货物装车问题的两阶段优化算法

针对同种同规格货物的三维装车问题,基于分层思想,将三维装车问题进行降维,转化为二维布局优化问题,提出九种分层装车策略,在算法设计上,提出了两阶段优化算法,第一阶段沿车厢的长、宽或高进行分层,针对不同的层高,通过动态规划算法求解平面内的最大货物装载量,得到货物的最优布局;第二阶段结合背包算法对层进行组合,得到车厢每个维度下的最优层,最后择优选取可装货物数量最多的方案,即为最优装载方案;最后通过两个数据集共8个算例对算法进行测试。结果表明,对于数据集一来说,本文算法求得的平均装载率可达99.43%,优于带排列分层算法、动态规划算法,以及混合递归算法求得的平均装载率;而对于数据集二来说,本文算法求得的平均装载率也达到了96.11%,优于二维排列算法,说明本文提出的两阶段优化算法在一定程度上可以生成较好的装载方案。