Hybrid algorithm for solving Single-Container Rectangular Packing Problem

doi:10.3778/j.issn.1002-8331.2009.27.060

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (27): 196-199.DOI: 10.3778/j.issn.1002-8331.2009.27.060

• 工程与应用 • Previous Articles Next Articles

Hybrid algorithm for solving Single-Container Rectangular Packing Problem

JIANG Xing-bo，LIU Xiao-rong

Department of Health Service，Second Military Medical University，Shanghai 200433，China

Received:2008-11-05 Revised:2009-02-16 Online:2009-09-21 Published:2009-09-21
Contact: JIANG Xing-bo

求解单容器矩形装箱问题的混合算法

蒋兴波，刘晓荣

第二军医大学卫生勤务学教研室，上海 200433

通讯作者: 蒋兴波

Abstract

Abstract: The Single-Container Rectangular Packing Problem（SCRPP） is a typical combinatorial optimization problem and possesses widespread application in the industry.Firstly，a new heuristic algorithm，Lowest-Horizontal-Line Best Fit（LHLBF） algorithm，is proposed.The LHLBF algorithm can dynamically select the better-fit rectangle for packing according to five rules.Secondly，the hybrid algorithm can be obtained by combining LHLBF algorithm with the Genetic Algorithm（GA） for solving the SCRPP.The computational results show that GA+LHLBF algorithm is more effective than existing algorithms from the literature.

Key words: Single-Container Rectangular Packing Problem（SCRPP）, Lowest-Horizontal-Line Best Fit（LHLBF） algorithm, Genetic Algorithm（GA）, hybrid algorithm

摘要： 单容器矩形装箱问题是一个典型的组合优化问题，其在工业界有着广泛的应用。首先提出了一种新的启发式布局算法，即底部匹配算法，该算法在矩形的装入过程中根据五种启发式规则自动选择与装填区域相匹配的下一个矩形。然后将底部匹配算法与遗传算法相结合形成混合算法来求解单容器矩形装箱问题。实验结果表明，与已有算法相比，该文提出的算法更加有效。

关键词: 单容器矩形装箱问题, 底部匹配算法, 遗传算法, 混合算法

CLC Number:

TP391

JIANG Xing-bo，LIU Xiao-rong. Hybrid algorithm for solving Single-Container Rectangular Packing Problem[J]. Computer Engineering and Applications, 2009, 45(27): 196-199.

蒋兴波，刘晓荣. 求解单容器矩形装箱问题的混合算法[J]. 计算机工程与应用, 2009, 45(27): 196-199.

[1]	WU Guangfu, CHEN Ying. Summary of Research and Application of Flower Pollination Algorithm [J]. Computer Engineering and Applications, 2021, 57(15): 30-41.
[2]	FENG Xiaodong, HUANG Shirong, DAI Guan’ou, YANG Weijia, LUO Yaozhi. Research and Application of Beetle Antennae Genetic Hybrid Algorithm [J]. Computer Engineering and Applications, 2021, 57(15): 90-100.
[3]	LIAO Liefa, YANG Hong. Review of Beetle Antennae Search [J]. Computer Engineering and Applications, 2021, 57(12): 54-64.
[4]	ZHANG Songcan, PU Jiexin, SI Yanna, SUN Lifan. Survey on Application of Ant Colony Algorithm in Path Planning of Mobile Robot [J]. Computer Engineering and Applications, 2020, 56(8): 10-19.
[5]	WU Congcong, HE Yichao, ZHAO Jianli. New Genetic Algorithm for Discounted {0-1} Knapsack Problem [J]. Computer Engineering and Applications, 2020, 56(7): 57-66.
[6]	QIN Qin, LIANG Chengji. Optimization of Equipment Coordination Scheduling with Considering Buffer Space in Automated Container Terminal [J]. Computer Engineering and Applications, 2020, 56(6): 262-270.
[7]	LIANG Chengji, YU Jian. Research on Dispatching of Container Terminals Quay Crane Scheduling with Interference Constraints [J]. Computer Engineering and Applications, 2020, 56(10): 273-278.
[8]	YAN Xu, YE Chunming. Hybrid Grasshopper Optimization Algorithm for Job-Shop Scheduling Problem [J]. Computer Engineering and Applications, 2019, 55(6): 257-264.
[9]	DONG Hao1, ZHANG Haiping2, LI Zhongjin1, LIU Hui1. Computation Offloading for Service Workflow in Mobile Edge Computing [J]. Computer Engineering and Applications, 2019, 55(2): 36-43.
[10]	XUE Meng, JIANG Shujuan, WANG Rongcun. Systematic review of test data generation based on intelligent optimization algorithm [J]. Computer Engineering and Applications, 2018, 54(17): 16-23.
[11]	LOU Gaoxiang, CAI Zongyan, LIU Qingtao. Application of new hybrid algorithm in mixed model assembly scheduling [J]. Computer Engineering and Applications, 2018, 54(16): 254-259.
[12]	WANG Xinyue, GUO Jianquan. Subsidy strategy model of multi-period closed-loop hybrid system under carbon tax [J]. Computer Engineering and Applications, 2018, 54(14): 236-240.
[13]	LUO Xianglong1，2, ZHANG Shengrui1, NIU Liyao2. Short-term traffic flow prediction based on detector optimal selection [J]. Computer Engineering and Applications, 2017, 53(8): 199-202.
[14]	LIANG Chengji, WU Yu. Simultaneous berth and quay crane scheduling under uncertainty environments in container terminals [J]. Computer Engineering and Applications, 2017, 53(7): 212-219.
[15]	JIN Yanxia, REN Chao, LI Zhao, CHEN Siyue, WANG He, HAN Huiyan. Research on collision detection algorithm based on fusion intelligent algorithm [J]. Computer Engineering and Applications, 2017, 53(19): 130-135.

Hybrid algorithm for solving Single-Container Rectangular Packing Problem

求解单容器矩形装箱问题的混合算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics