一种新的多约束尺寸可变的装箱问题

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (19): 242-244.

一种新的多约束尺寸可变的装箱问题

杜少波1，张国基1，刘清2

1.华南理工大学理学院，广州 510640
2.华南理工大学计算机科学与工程学院，广州 510640

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-07-01 发布日期:2011-07-01

New multi-constrained variable-sized bin packing problem

DU Shaobo1，ZHANG Guoji1，LIU Qing2

1.School of Science，South China University of Technology，Guangzhou 510640，China
2.School of Computer Science and Engineering，South China University of Technology，Guangzhou 510640，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-07-01 Published:2011-07-01

摘要/Abstract

摘要： 多约束尺寸可变的装箱问题作为经典装箱问题的扩展，具有极为广泛的应用背景。在以货车运输为主的物流公司的装载环节中，运输成本不仅仅由车厢的空间利用率决定。分析了该类装箱问题与传统的集装箱装载问题的区别，并据此给出了一种新的尺寸可变装箱问题的定义。除了经典装箱问题中物品体积这一参数，还引入了物品类型、箱子类型等参数，建立了数学模型，将经典的FFD（First Fit Decreasing）算法进行了推广，提出了新的算法MFFD，并分析了相关的算法复杂性。最后对FF、FFD以及MFFD算法进行了模拟实验，实验结果表明，在相关参数符合均匀分布的条件下，MFFD算法效果较好。

关键词: 装箱问题, 多约束, 尺寸可变, FFD算法

Abstract: As the extension of classical bin packing problem，the multi-constrained variable-sized bin packing problem has many extensive applications.In the loading section of logistics it has mainly transported by truck，the transportation cost is not only determined by the bin space utilization.In this paper，the difference between truck loading and classical container bin problem is analyzed，a new definition of variable-sized bin packing problem is given based on the analysis.The type of items and bins are introduced in the mathematical model，as well as the volume of the items.On the base of classical First Fit Decreasing（FFD） algorithm，a new algorithm MFFD is presented，and the algorithmic complexity is analyzed.In the simulation experiments，the proposed algorithm MFFD plays a better performance than other algorithms when the parameters are uniform distributed.

Key words: bin packing problem, multi-constrained, variable-sized, First Fit Decreasing（FFD） algorithm

杜少波1，张国基1，刘清2. 一种新的多约束尺寸可变的装箱问题[J]. 计算机工程与应用, 2011, 47(19): 242-244.

DU Shaobo1，ZHANG Guoji1，LIU Qing2. New multi-constrained variable-sized bin packing problem[J]. Computer Engineering and Applications, 2011, 47(19): 242-244.

[1]	尚正阳1，顾寄南2，唐仕喜2，孙晓红2. 高效求解三维装箱问题的剩余空间最优化算法[J]. 计算机工程与应用, 2019, 55(5): 44-50.
[2]	张钧，贺可太. 求解三维装箱问题的混合遗传模拟退火算法[J]. 计算机工程与应用, 2019, 55(14): 32-39.
[3]	黄海1，李松斌2，3. 求解online packing problem的F-B绝对近似算法[J]. 计算机工程与应用, 2017, 53(11): 73-78.
[4]	田保珍，余隋怀，王淑侠，曲敏，裴卉宁，刘昕. 多约束条件下定制产品模块划分方法[J]. 计算机工程与应用, 2016, 52(19): 234-240.
[5]	杨坚，彭玉旭. 基于自适应ACO的多约束QoS路由研究[J]. 计算机工程与应用, 2015, 51(13): 106-110.
[6]	刘林浩1，杨鼎强1，王晨2. 一种带脆度的尺寸可变装箱问题[J]. 计算机工程与应用, 2013, 49(12): 263-266.
[7]	余蕾，陈国宏. 卸货顺序约束的单容器矩形装箱问题[J]. 计算机工程与应用, 2012, 48(28): 240-244.
[8]	张旭君，吕志民. 基于约束规划的一类排序问题通用求解方法[J]. 计算机工程与应用, 2012, 48(26): 219-224.
[9]	曹大勇1，杨梅2，刘润涛3. 二维离线非旋转装箱问题的一个混合算法[J]. 计算机工程与应用, 2011, 47(7): 16-19.
[10]	李敏^1，2，陆芸婷¹，邹粤^1，2. IP Mesh网络的多约束QoS选路研究[J]. 计算机工程与应用, 2011, 47(6): 78-81.
[11]	胡琼琼，雷秀娟，张兰. 改进的蚁群算法在QoS网络路由中的应用[J]. 计算机工程与应用, 2011, 47(13): 212-215.
[12]	古明家，宣士斌，廉侃超，李永胜. 求解QoS组播路由的自适应变异二次蚁群算法[J]. 计算机工程与应用, 2010, 46(13): 98-100.
[13]	王敏，李铁克. 求解入库堆垛问题的改进约束满足算法[J]. 计算机工程与应用, 2010, 46(1): 7-10.
[14]	宁爱兵¹,熊小华^1,2,马良¹. 城市物流配送中的三维装箱算法[J]. 计算机工程与应用, 2009, 45(9): 207-208.
[15]	蒋兴波，刘晓荣. 求解单容器矩形装箱问题的混合算法[J]. 计算机工程与应用, 2009, 45(27): 196-199.