计算机工程与应用
www.ceaj.org
Computer Engineering a nd Applications计算机工程与应用
2019，55（5）
1 引言
装箱问题是指将一组二维矩形或者三维长方体，放
置到二维或者三维空间中，以使得空间的填充率最大或
者容积最小。它作为一个传统的优化组合问题，不仅得
到了大量的理论研究，还被广泛地应用在了实际生产和
生活的各个领域。特别是针对三维装箱问题，由于其更
加贴近真实情况，已经在工业中得到了大量使用，例如
以三维空间利用率为目标的集装箱放置和木材切割问
高效求解三维装箱问题的剩余空间最优化算法
尚正阳
1
，顾寄南
2
，唐仕喜
2
，孙晓红
2
1.安徽工程大学 机械与汽车工程学院，安徽 芜湖 241000
2.江苏大学 制造业信息化研究中心，江苏 镇江 212000
摘 要：为实现三维装箱问题的高效求解，提出了一个三维的剩余空间最优化算法（Three-Dimen sional Residual-
Space-Optimized Algorithm，3D-R SO）。在满足 3个著名约束的条件下，该算法将三维问题转化为带有高度约束的二
维问题，通过对箱子放置后的剩余空间状态分析，提出了基于概率较优的空间分割方法和箱子布置规则。相比于传
统算法，3D-RSO 在求解过程中不需要任何的预处理和搜索操作，是一种最坏计算复杂度为 O(2n
2
) 的直接求解算
法。针对强异构体的实验表明，该算法能够在极短的时间内对算例进行高效求解，适合应用在大规模或者需要被快
速求解的三维装箱问题中。
关键词：三维装箱问题 ；启发式算法；快速求解 ；调度优化
文献标志码：A 中图分类号：TP 301 doi：10.3778/j.issn.1002-8331.1808-0176
尚正阳，顾寄南，唐仕喜,等 .高效求解三维装箱问题的剩余空间最优化算法 .计算机工程与应用，201 9，55（5）：44-50.
SH ANG Zhengyang, GU Jinan, TANG Shixi, et al. Efficient resi dual-space-optim ization alg orithm for three dimensional
container loading problem. Computer Engineering and Applica tions , 2019, 55（5）：44-50.
Efficient Residual-Space-OptimizationAlgorithm for Three Dimensional Container Loading Problem
SHANG Zhengyang
1
, GU Jinan
2
, TANG Shixi
2
, SUN Xiaohong
2
1.S chool of Mechanical and Automotive Eng ineering, Anhui Polytechnic University, Wuhu, Anhui 241000, China
2.Mechanical Information Research C enter, Jiangsu University, Zhenjiang , Jiangsu 212000, China
Ab stract：A Three-Dimensional Residual-Space -Optimized algorithm（3D-RSO）is proposed to efficient ly solve 3D
container loading problems. Under the condition of satisfying th ree famous constraints, 3D-RSO transforms a 3D problem
into a 2D problem with height constraint. Through state analysis of the remaining space, it puts forward a probability-based
spatial segmentation method and box layout rule respect ively. Compared with traditional algorithms, 3D- RSO doesn’t
need any preproc essing or searching operation durin g the solving process, and is a direct solving algorithm with the worst
computational complexity O(2n
2
) . Experiments on strongly heterogeneous data- sets sh ow 3D- RSO can efficiently
solve 3D packing proble m within very short time. Thus, this heuristic is suitable for some cases that are at large scale or
should be solved quickly.
Key words：three-dimensional container loading problem; heuristic algorithm; fast solving algorithm; scheduling optimization
基金项目：安徽工程大学引进人才科研启动基金（No.2018YQQ006）；某部委基础科研计划项目（No.JCKY2013414C001）。
作者简介：尚正阳（1987—），通讯作者，男，博士，讲师，主要研究方向：机械系统仿真，优化算法设计，E-mail：shzy0205@163.com；
顾寄南（1963—），男，博士，教授，主要研究方向：制造业信息化，智能机器人，复杂产品建模与创新设计理论；唐仕喜
（1975—），男，博士在读，副教授，主要研究方向：制造业信息化，人工智能；孙晓红（1979—），女，博士在读，讲师，主要
研究方向：机器视觉。
收稿日期：2018-08-09 修回日期：2018-12-04 文章编号：1002-8331（2019）05-0044-07
CN KI网络出版：2018-12- 24, http://kns.cnki. net/kcms/detail/11.2127. tp.20181220.1008.019.html
44
评论0