[科普中国]-集装优化

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

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

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

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

运筹学运筹学（Operations Research，又被称作作业研究），是一门应用数学学科，利用统计学和数学模型等方法，去寻找复杂问题中的最佳或近似最佳的解答。运筹学经常用于解决现实生活中的复杂问题，特别是改善或优化现有系统的效率。研究运筹学的基础知识包括矩阵论和离散数学，在应用方面多与仓储、物流等领域相关。因此运筹学与应用数学、工业工程专业密切相关。运筹学是一门研究怎么样处理事情更有效的学科，比如机械动作合理安排，计算机的多线程，高层建筑材料的合理分配，不同动植物的共同养殖等都是当今社会经济发展的热点。1

启发式搜索计算机科学中所谓的heuristic，除了有经验法则的意思外（见启发式），它还有另外两个技术上的意义。

计算机科学的两大基础目标，就是发现可证明其运行效率良好且可得最佳解或次佳解的算法。而启发式算法则试图一次提供一个或全部目标。例如它常能发现很不错的解，但也没办法证明它不会得到较坏的解；它通常可在合理时间解出答案，但也没办法知道它是否每次都可以这样的速度求解。

有时候人们会发现在某些特殊情况下，启发式算法会得到很坏的答案或效率极差，然而造成那些特殊情况的数据结构，也许永远不会在现实世界出现。因此现实世界中启发式算法很常用来解决问题。启发式算法处理许多实际问题时通常可以在合理时间内得到不错的答案。

有一类的通用启发式策略称为元启发式算法（metaheuristic），通常使用随机数搜索技巧。他们可以应用在非常广泛的问题上，但不能保证效率。1

参看线性代数

拓扑学

本词条内容贡献者为:

杨晓红 - 副教授 - 西南大学