集装箱配装问题的研究方法及分析比较

        前面已经提到，集装箱装载问题可以划分为集装箱数量有限和无限两类，而在实际应用中，第二类问题比较常见，所以在此分析第二类问题。

        3.1 相同类型货物的配装

        此类配装的模型较为简单，主要的研究方法是根据已知的货物和集装箱的长、宽尺寸，将货物先顺放(货物的长与集装箱的长平行)后横放(货物的长与集装箱的长垂直)或者先横放后顺放，计算这两种装载形式的利用率,选择恰当的装载方式。

        对于此类问题，给出了集装箱积载模型将行/列约束法应用到集装箱配载中，简化了计算步骤。对于同一个实例：货物尺寸为25cm×35cm×50cm，货柜尺寸为2.28m×2.38m×11.9m，分别采用以上两种方法，所得装载结果：前者的容积利用率为96.95%。后者达到97.22%，可见对于这一例子后者的配装效果更好。

        3.2不同类型货物的配装

        此类型的配装主要依靠空间分解的思想，从而派生出一系列的算法，例如:启发式算法。三叉树空间分割算法、遗传算法等。

        3.2.1 三叉树空间分割算法，该算法通过商品在三维空间中的各方向利用率的组合选取一种主商品，然后通过改变这种商品在一个方向上的数量来与其它商品进行组合，从而使空间实际利用率达到最优；再通过空间的整合处理剩余的零散空间，以满足最优化装载的要求。这种方法适用于配装种类少而每类数量多的货物，应用此方法使集装箱配载的容积利用率达到90%以上。

        3.2.2 启发式算法，该算法是集装箱配载中比较常见的算法，在三叉树空间分割算法的基础上设计出基于空间分解的启发式算法，并在装载货物时依照定序和定位规则进行布局。所谓定序规则就是货物装载时的先后顺序,主要的定序规则有：按物体底面积递减定序；按物体最长边递减定序和按物体体积递减定序，其中以第三种最为常用。定位规则是指货物的布局定位规则，主要有：占角策略，即物体首先摆放在布局空间的某一角；顺放策略，从一个角开始，沿布局空间的某一边顺序摆放；先沿布局空间的四边摆放，然后填中心。通常采用占角策略，在加入定序规则和定位规则后设计出来的启发式算法对于货物种类多，每类货物数量少的配装情况是有效的。是采用分层的启发式算法，每层由一个以一定规则选定的货物(称为层定义盒子LDB)确定，每层再进行空间分解，并逐步装载形成的各子空间。由于每一个盒子可能有几种放置形式，且变化盒子的放置形式可以获得更多的装载方法，从而可在更大范围内取最佳方案，但每个盒子都考虑其所有可能放置形式，计算量大，不好实现。而通过变化每一层的LDB的放置形式，从而改变该层的有关数据，更新装载方法，从中选出空间利用率最高的层作为该层的最优装载方案，则是可行的。
   
        对于同一实例:
 
        结果是前者的容积利用率可以达到82.8%，后者为85.25%，可见对于该例子后者的效果更好。

        3.2.3 遗传算法，该算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。采用遗传算法作为工具,通过权重系数变化法处理多目标问题，通过罚函数法处理约束，从而解决复杂集装箱装载问题。遗传算法比空间分割算法和启发式算法更适用于求解复杂的集装箱装载问题。