集装箱单箱三维装载优化研究

摘要

集装箱装载问题是货物运输过程中普遍存在的一个重要环节，一个合理的装箱方案可以提高集装箱的空间利用率，降低运输成本，从而带来巨大的经济效益。从理论角度来看，集装箱装载问题属于NP(Non-deterministic Polynomial，NP)完全问题，确定最优解非常困难。因此，寻找一个有效的解决集装箱装载问题的算法对于解决集装箱装载的实际问题以及求解NP完全问题都具有非常重要的意义。 本文首先对集装箱装载问题进行了简单的介绍，然后对解决该类问题的启发式算法和遗传算法进行了详细地分析和比较，提出了一种基于空间分解的启发式方法和遗传算法相结合的混合遗传算法。该算法首先利用启发式规则产生问题的初始解群，然后采用三空间分解法对剩余空间进行分解，采用空间合并原则将闲置空间与可用空间进行合并以达到充分利用，并根据待装货物种类和数量的不同采用了不同的装载顺序，最后对遗传算法的相关参数进行了分析比较，找出适合该类问题的最佳参数取值，并对交叉操作和变异操作进行了相应的改进。文章最后应用VC++的界面设计功能和OpenGL三维图形技术开发了一个简单的装箱系统，能够生成装箱方案，供实际装箱操作中参考。 本文采用混合遗传算法主要解决的是弱异类货物的装箱问题，对强异类和具有特殊约束条件的装箱问题也进行了简单的研究和探讨。通过对算例的分析比较，该算法在求解集装箱装载问题时表现出良好的性能，最终的装载结果与以前文献中记载的相比都有了很大的提高，所以应用本文设计的混合遗传算法求解集装箱单箱三维装载优化问题是非常可行的。