Research on three dimensional bin packing problem with multi-type bins based on tabu search algorithm

doi:10.3778/j.issn.1002-8331.2009.22.063

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (22): 197-199.DOI: 10.3778/j.issn.1002-8331.2009.22.063

• 工程与应用 • Previous Articles Next Articles

Research on three dimensional bin packing problem with multi-type bins based on tabu search algorithm

ZHONG Shi-quan¹，WANG Xue-lian²

1.School of Management，Tianjin University，Tianjin 300072，China
2.School of Management，Hebei University of Technology，Tianjin 300130，China

Received:2008-04-23 Revised:2008-08-14 Online:2009-08-01 Published:2009-08-01
Contact: ZHONG Shi-quan1

多箱型三维装箱问题及其优化研究

钟石泉¹，王雪莲²

1.天津大学管理学院，天津 300072
2.河北工业大学管理学院，天津 300130

通讯作者: 钟石泉

Abstract

Abstract: A three dimensional Bin Packing problem（3BP） with multi-type bins is presented in this paper.A Tabu Search algorithm（TS） is designed to solve this problem on nature number.Three kinds of neighborhood are proposed in this algorithm to extend the search space.The algorithm uses the operation of neighborhood to control the bin number limit.Weight limit and center of gravity limit are controlled with penalty function.The principium of the TS are introduced，two representative results and the analysis are given.The experiment indicates the validity of the TS to the three dimensional bin packing problem with multi-type bins.

Key words: bin packing problem, three dimensional, tabu search algorithm

摘要： 对多箱型三维装箱问题进行了描述，提出了求解该问题的禁忌算法。算法基于自然数编码，设计了货物的摆放规则和序列生成方式，采用三种邻域，利用邻域操作控制集装箱数量限制，采用惩罚函数处理集装箱重量约束和重心约束。介绍了算法的原理，给出了具有代表性算例实验结果并且进行了分析。实验结果表明了提出的禁忌算法对优化多箱型三维装箱问题的有效性。

关键词: 装箱问题, 三维, 禁忌算法

ZHONG Shi-quan¹，WANG Xue-lian². Research on three dimensional bin packing problem with multi-type bins based on tabu search algorithm[J]. Computer Engineering and Applications, 2009, 45(22): 197-199.

钟石泉¹，王雪莲². 多箱型三维装箱问题及其优化研究[J]. 计算机工程与应用, 2009, 45(22): 197-199.

[1]	CHEN Zhan, GONG Jianning, LIU Yuanyuan, XU Jingbang. Multi-AGV System Path Optimization Algorithm Based on Tabu Search [J]. Computer Engineering and Applications, 2021, 57(10): 273-278.
[2]	GE Xianlong1，2, XUE Guiqin1. Multi-Products Joint Distribution Vehicle Routing Optimization with Uncertain Circumstance [J]. Computer Engineering and Applications, 2019, 55(9): 264-270.
[3]	PANG Lili1, XU Qiqing1, XIE Jiaye1，2. Reduction of NLOS Error in Three-Dimensional Positioning under Ellipsoid Constraint [J]. Computer Engineering and Applications, 2019, 55(7): 115-119.
[4]	CHEN Lei, ZHANG Hongmei, ZHANG Xiangli. Adaptive dynamic neighborhood hybrid cuckoo search algorithm for solving traveling salesman problems [J]. Computer Engineering and Applications, 2018, 54(23): 42-50.
[5]	ZHANG Quangui, LI Fan, WANG Bingchao, WANG Xing. Method of three dimensional model retrieval based on Fuzzy topology and CRSC [J]. Computer Engineering and Applications, 2017, 53(7): 192-196.
[6]	LIU Jun1，2, QIAN Qingqing1，2, WU Xi1，2, WANG Wei1，2, CHEN Tian1，2, REN Fuji3. Optimizing pre-bond and post-bond test time for three dimension IP cores [J]. Computer Engineering and Applications, 2016, 52(22): 44-48.
[7]	JI Ronghua1, LI Xiang1, GAO Wanlin1, WANG Fengchen2, QI Lijun2. Parameters optimization of staged continuous Tabu search algorithm based on multidimensional normal distribution [J]. Computer Engineering and Applications, 2015, 51(6): 59-63.
[8]	MAO Qibo. Solution for three dimensional Helmholtz equations under arbitrary wave numbers [J]. Computer Engineering and Applications, 2015, 51(2): 26-29.
[9]	LIU Hao1, CAO Wei2. Rapid updating method of local high-precision terrain data in 3D terrain scene [J]. Computer Engineering and Applications, 2014, 50(7): 1-4.
[10]	ZHAO Feng1, YANG Wei1，2，3, YANG Zhaoxu3, SUN Shaoshan3. UAV three-dimensional dynamic route planning and guidance control research [J]. Computer Engineering and Applications, 2014, 50(2): 58-64.
[11]	HOU Pei1，2, TIAN Qingguo1，2, GE Baozhen1，2. Research on method of extracting skeletal curves of 3D human scanning data based on optimizing DRG [J]. Computer Engineering and Applications, 2014, 50(18): 182-187.
[12]	ZHAO Feng, FAN Jiulun. Three-dimensional Otsu’s method with non local spatial gray information [J]. Computer Engineering and Applications, 2013, 49(3): 30-33.
[13]	XIA Xinjiang1，2, HU Gang1，2, WANG Yehua1，2. Research on three-dimensional positioning algorithm of wireless sensor network based on cross domain gravity center of anchor balls [J]. Computer Engineering and Applications, 2013, 49(10): 76-79.
[14]	OUYANG Hao, CHEN Bo. Solution of minimum spanning tree based on niche genetic algorithm Importing Tabu Search [J]. Computer Engineering and Applications, 2013, 49(1): 59-61.
[15]	WANG Jia1，2, FU Zhuo1. Research on design and optimum-method of double-layer urban transit network [J]. Computer Engineering and Applications, 2012, 48(36): 1-8.

Research on three dimensional bin packing problem with multi-type bins based on tabu search algorithm

多箱型三维装箱问题及其优化研究

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics