集装优化

集装优化,又名集装问题是一个利用运筹学去解决实际生活的的经典问题。简单来说,就是把大量小盒子装进大箱子并塞满的学问。但现实中要如何才能装得多又快?而物体的重量、性质、保存条件等都不相同,加上取出的顺序要能有效提高速度,又不会使运输工具失去重心,因此集装优化在效率至上运输界中是十分重要的。

传统上,数学家开发的算法是启发式算法,也就是基于一些准则,比如两个小箱子一样宽,将把宽的一边对齐,这样的好处是算得快,缺点是很多可能性(或者叫可行解)根本就没有去搜索到。在应用上,工人们会凭借经验估计,但是难以估计准,也给运输计划的制定带来困难。

拓扑学亦可用于解决这个问题。我们可以把集集装内摆放座向不同的小箱子视为一个点,把这些点之间的关系记录为一个个不同的拓扑结构。利用电脑的帮助,计算不同的拓扑结构下的可能集装方案,然后得出装得多的方案,使箱子的空间利用率得以提高。

参考资料

  • Yue, Minyi, A simple proof of the inequality FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for the FFD bin-packing algorithm, Acta Mathematicae Applicatae Sinica, October 1991, 7 (4): 321–331, ISSN 0168-9673, doi:10.1007/BF02009683 

参见