Heuristic Simulated Annealing Algorithm for Orthogonal Rectangle Packing Problem with Static Non-Equilibrium Constraints
LIU Jing-Fa1,2,3, ZHANG Zhen1,2, XUE Yu1,2, LIU Wen-Jie1,2, JIANG Yu-Cong1,2
1.Jiangsu Engineering Center of Network Monitoring, Nanjing University of Information Science and Technology, Nanjing 210044 2.School of Computer and Software, Nanjing University of Information Science and Technology, Nanjing 210044 3.Network Information Center, Nanjing University of Information Science and Technology, Nanjing 210044
Abstract：With the background of the satellite module layout, the orthogonal rectangle packing problem with static non-equilibrium constraints is studied. By drawing lessons from quasiphysical strategy and defining embedded computing formula between each two rectangles, and between the rectangle and the circular container, this problem is converted into an unconstrained optimization problem. By incorporating heuristic configuration update strategies, local search strategy based on the gradient method and the simulated annealing algorithm with global optimization, a heuristic simulated annealing algorithm for orthogonal rectangle packing problem with static non-equilibrium constraints is put forward.The heuristic configuration update strategies in this algorithm produce new configurations and jump out of trap. The gradient method is searched for lower-energy minima near newly generated configurations. In addition, in the process of layout optimization, a static non-equilibrium penalty term on the basis of the extrusive elastic energy is introduced. Subsequently, by adopting the translation of the center of mass, the static non-equilibrium constraints of the whole system can be satisfied. The experimental results show that the proposed algorithm is an effective algorithm for solving the orthogonal rectangle packing problem with static non-equilibrium constraints.
[1] Zachariadis E E, Tarantilis C D, Kiranoudis C T. A Guided Tabu Search for the Vehicle Routing Problem with Two-Dimensional Loa-ding Constraints. European Journal of Operational Research, 2009, 195(3): 729-743 [2] Dominguez O, Juan A A, Barrios B, et al. Using Biased Randomization for Solving the Two-Dimensional Loading Vehicle Routing Problem with Heterogeneous Fleet. Annals of Operations Research, 2014. DOI: 10.1007/s10479-014-1551-4 [3] Ji J, Lu Y P, Zha J Z, et al. A Deterministic Algorithm for Optimal Two-Segment Cutting Patterns of Rectangular Blanks. Chinese Journal of Computers, 2012, 35(1): 183-191 (in Chinese) (季 君,陆一平,查建中,等.生成矩形毛坯最优两段排样方式的确定型算法.计算机学报, 2012, 35(1): 183-191) [4] He K, Jin Y, Huang W Q. Heuristics for Two-Dimensional Strip Packing Problem with 90° Rotations. Expert Systems with Applications, 2013, 40(14): 5542-5550 [5] Wang Y S, Teng H F. Knowledge Fusion Design Method: Satellite Module Layout. Chinese Journal of Aeronautics, 2009, 22(1): 32-42 [6] He K, Mo D Z, Ye T, et al. A Coarse-to-Fine Quasi-Physical Optimization Method for Solving the Circle Packing Problem with Equilibrium Constraints. Computers & Industrial Engineering, 2013, 66(4): 1049-1060 [7] Lodi A, Martello S, Monaci M. Two-Dimensional Packing Pro-blems: A Survey. European Journal of Operational Research, 2002, 141(2): 241-252 [8] Wang P, Huang S, Zhu Z Q. Exploring Improved Artificial Bee Co-lony Algorithm for Solving Circle Packing Problem with Equilibrium Constraints. Journal of Northwestern Polytechnical University, 2014, 32(2): 240-245 (in Chinese) (王 鹏,黄 帅,朱舟全.求解带平衡约束圆形packing问题的改进人工蜂群算法.西北工业大学学报, 2014, 32(2): 240-245) [9] Feng E M, Xu G J, Teng H F. Optimization Layout Models of Rectangular Elements with Behavior Constraints and Non-interference Judging Algorithm. Applied Mathematics: A Journal of Chinese Universities, 1993, 8(1): 53-60 (in Chinese) (冯恩民,许广键,滕弘飞.带性能约束的矩形图元布局优化模型及不干涉性算法.高校应用数学学报, 1993, 8(1): 53-60) [10] Feng E M, Wang X L, Wang X M, et al. A Global Optimization Algorithm for Layout Problems with Behavior Constraints. Applied Mathematics: A Journal of Chinese Universities, 1999, 14A(1): 98-104 (in Chinese) (冯恩民,王锡禄,王秀梅,等.带性能约束布局问题的全局优化算法.高校应用数学学报, 1999, 14A(1): 98-104) [11] Xu Y C, Xiao R B, Amos M. Particle Swarm Algorithm for Weighted Rectangle Placement // Proc of the 3rd International Confe-rence on Natural Computation. Haikou, China, 2007: 728-732 [12] Xu Y C, Dong F M, Liu Y, et al. Genetic Algorithm for Rectangle Layout Optimization with Equilibrium Constraints. Pattern Recognition and Artificial Intelligence, 2010, 23(6): 794-801 (in Chinese) (徐义春,董方敏,刘 勇,等.带平衡约束矩形布局优化问题的遗传算法.模式识别与人工智能, 2010, 23(6): 794-801) [13] Huang Z D, Xiao R B. Hybrid Algorithm for the Rectangular Pac-king Problem with Constraints of Equilibrium. Journal of Huazhong University of Science and Technology: Natural Science Edition, 2011, 39(3): 96-99, 104 (in Chinese) (黄振东,肖人彬.求解带平衡约束矩形布局问题的混合算法.华中科技大学学报:自然科学版, 2011, 39(3): 96-99, 104) [14] Liu J F, Zhou Z L, Liu Z X, et al. Improved Tabu Search Algorithm for the Rectangle Packing Problem with Equilibrium Constraints. Journal of Information & Computational Science, 2012, 9(18): 5831-5839 [15] Liu J F, Li G. Basin Filling Algorithm for the Circular Packing Problem with Equilibrium Behavioral Constraints. Science China: Information Sciences, 2010, 40(3): 423-432 (in Chinese) (刘景发,李 刚.求解带平衡性能约束的圆形装填问题的吸引盘填充算法.中国科学:信息科学, 2010, 40(3): 423-432) [16] He K, Mo D Z, Xu R C, et al. A Quasi-Physical Algorithm Based on Coarse and Fine Adjustment for Solving Circles Packing Problem with Constraints of Equilibrium. Chinese Journal of Computers, 2013, 36(6): 1224-1234 (in Chinese) (何 琨,莫旦增,许如初,等.基于粗精调技术的求解带平衡约束圆形Packing问题的拟物算法.计算机学报, 2013, 36(6): 1224-1234) [17] Zhai J G, Feng E M, Li Z M, et al. Non-overlapped Genetic Algorithm for Layout Problem with Behavioral Constraints. Journal of Dalian University of Technology, 1999, 39(3): 352-357 (in Chinese) (翟金刚,冯恩民,李振民,等.带性能约束布局问题的不干涉遗传算法.大连理工大学学报, 1999, 39(3): 352-357)
2015, Vol. 28 
