集装优化，又名裝箱問題是一個利用作業研究去解決實際生活的的經典問題。簡單來說，就是把大量小盒子裝進大箱子並塞滿的學問。但現實中要如何才能裝得多又快？而物體的重量、性質、保存條件等都不相同，加上取出的順序要能有效提高速度，又不會使運輸工具失去重心，因此裝箱最佳化在效率至上運輸界中是十分重要的。
傳統上，數學家開發的演算法是啟發式演算法，也就是基於一些準則，比如兩個小箱子一樣寬，將把寬的一邊對齊，這樣的好處是算得快，缺點是很多可能性（或者叫可行解）根本就沒有去搜索到。在應用上，工人們會憑藉經驗估計，但是難以估計準，也給運輸計劃的制定帶來困難。
拓撲學亦可用於解決這個問題。我們可以把集裝箱內擺放座向不同的小箱子視為一個點，把這些點之間的關係記錄為一個個不同的拓撲結構。利用電腦的幫助，計算不同的拓撲結構下的可能裝箱方案，然後得出裝得多的方案，使箱子的空間利用率得以提高。
装箱问题 是一个优化问题，其中不同尺寸的物品必须装箱到有限数量的箱子或容器中，每个箱子或容器的容量都是固定的，目的是使使用的箱子数量最小化。 该问题有很多应用，例如填充集装箱、在重量限制下装载卡车、在介质中创建文件备份、将网络前缀拆分为多个子网以及FPGA半导体芯片设计中的技术映射。
从计算角度来看，该问题是NP 难的，相应的判定问题（即判断物品是否可以放入指定数量的箱子中）是NP 完全的。 尽管该问题在最坏情况下难度很高，但利用复杂的算法可以针对非常大的实例生成最优解。 此外，还有许多近似算法。 例如，首次适应算法提供了一种快速但通常不是最优的解决方案，它将每个物品放入第一个能够容纳它的箱子中。 它需要Θ ( n) 日志 n ）时间，其中n是要包装的物品数量。 通过先将项目列表按降序排列（有时称为首次适应递减算法），可以大大提高算法的效率，但这仍然不能保证找到最优解，并且对于较长的列表，可能会增加算法的运行时间。 然而，已知总存在至少一种物品排序方式，使得首次适应算法能够产生最优解。
这个问题有很多变体，例如二维装箱、线性装箱、按重量装箱、按成本装箱等等。 装箱问题也可以看作是切割库存问题的一个特例。 当箱子的数量限制为 1，并且每个物品都有体积和价值两个特征时，最大化可以装入箱子的物品价值的问题被称为背包问题。
实际应用中，装箱的一种变体是物品可以共享空间并被装入箱子。 具体来说，一组物品打包在一起所占用的空间可能比它们各自体积之和要小。 这种变体被称为 VM 打包因为当虚拟机(VM) 打包到服务器中时，由于 VM 共享的页面只需要存储一次，因此它们的总内存需求可能会减少。 如果物品可以以任意方式共享空间，那么装箱问题甚至很难近似求解。 但是，如果空间共享符合层次结构（例如虚拟机中的内存共享），则可以有效地近似计算装箱问题。
实践中另一个值得关注的装箱变体是所谓的在线装箱。 这里不同体积的物品应该按顺序到达，决策者必须决定是选择并包装当前观察到的物品，还是让它通过。 每个决定都无法回忆。 相比之下，离线装箱允许重新排列物品，希望在其他物品到达后能够实现更好的包装。 当然，这需要额外的存储空间来存放需要重新整理的物品。
參考資料
*
參見
- 線性代數
- 拓撲學
评论 (0)