求解圆形packing问题的启发式方法
|
摘要
至今无严格有效的方法能保证在合理的计算时间内找出NP难问题的最优解。受自然界和人类社会中智慧的启发，我们提出了有效地近似求解具有NP难度的圆形packing问题的启发式方法。
本文所做的工作主要有：
第一，得出了一个高效地近似求解圆形packing问题的快速拟物拟人算法。此算法比之于前人所得的最好算法，其效能有了显著的提高。对于困难的问题实例，在保持优度相等的前提下，其速度大致提高了10～100倍。
第二，受物理世界中弹性物体运动规律的启发，得到了一个预测搜索前景的策略，它通过及早地终止将会陷入局部极小值陷阱的搜索，提高了搜索的效率；受自然界中优胜劣汰规律的启发得出另一个策略，它通过很好地利用人类在社会活动中积累的智慧，使搜索逃离局部极小值的陷阱，并走向更有前途的方向。结合这两个启发式策略以及拟物拟人法得到了快速拟物拟人算法。
第三，在模拟物理世界中弹性物体运动的基础上，借鉴模拟退火法的思想，得出了二个启发式方法。这两个方法通过在搜索过程中以不同的规则接受不优于当前解的新解，使搜索有可能逃离局部极小值陷阱，从而有效地求解了等圆packing问题。
第四，在用各启发式方法有效地求解大量实例的基础上，研究了启发式方法的工作原理，提出了设计启发式方法的可行的方案。
Now there does not exist an exactly effective method that can always provide an optimal solution for NP-hard problems within a reasonable time limit. Inspired by the wisdom of the nature and the human society, we present heuristic methods to effectively provide approximate solutions to one of the NP-hard problems, the disks packing problem.
Most of our work was done as follows:
Firstly, a fast quasi-physical and quasi-human algorithm, which can effectively provide approximate solutions to the disks packing problem, is obtained. The performance of this algorithm is obviously better than the best algorithm obtained so far. This algorithm's computational speeds on the difficult instances are between 10 and 100 times faster than those of the best algorithm, on the condition of keeping the quality of the solutions same.
Secondly, inspired by the movement rule of the elastic objects of the physical world, a strategy that predicts the prospect of the search is obtained. It improves the performance of the search by early stopping the search that will get trapped in local minima; Inspired by the survival of the fittest principle of the nature, another strategy lets the search escape from local minima to the direction of better prospect by using the wisdom that human has accumulated in social events. The fast quasi-physical and quasi-human algorithm is obtained as the integration of the above two methods and the quasi-physical and quasi-human algorithm.
Thirdly, based on simulating the elastic objects movement, two heuristic algorithms are presented by using the idea of the simulated annealing algorithm. By accepting the new solution, whose quality is not better than the previous one, according to the different rules, the above two algorithms are possible to let the search escape from local minima and thus effectively solve the equal disks packing problem.
Finally, by effectively using obtained heuristic methods to solve a lot of instances, we study the working principle of the heuristic methods, and present a feasible plan to design the heuristic methods.
本文所做的工作主要有：
第一，得出了一个高效地近似求解圆形packing问题的快速拟物拟人算法。此算法比之于前人所得的最好算法，其效能有了显著的提高。对于困难的问题实例，在保持优度相等的前提下，其速度大致提高了10～100倍。
第二，受物理世界中弹性物体运动规律的启发，得到了一个预测搜索前景的策略，它通过及早地终止将会陷入局部极小值陷阱的搜索，提高了搜索的效率；受自然界中优胜劣汰规律的启发得出另一个策略，它通过很好地利用人类在社会活动中积累的智慧，使搜索逃离局部极小值的陷阱，并走向更有前途的方向。结合这两个启发式策略以及拟物拟人法得到了快速拟物拟人算法。
第三，在模拟物理世界中弹性物体运动的基础上，借鉴模拟退火法的思想，得出了二个启发式方法。这两个方法通过在搜索过程中以不同的规则接受不优于当前解的新解，使搜索有可能逃离局部极小值陷阱，从而有效地求解了等圆packing问题。
第四，在用各启发式方法有效地求解大量实例的基础上，研究了启发式方法的工作原理，提出了设计启发式方法的可行的方案。
Now there does not exist an exactly effective method that can always provide an optimal solution for NP-hard problems within a reasonable time limit. Inspired by the wisdom of the nature and the human society, we present heuristic methods to effectively provide approximate solutions to one of the NP-hard problems, the disks packing problem.
Most of our work was done as follows:
Firstly, a fast quasi-physical and quasi-human algorithm, which can effectively provide approximate solutions to the disks packing problem, is obtained. The performance of this algorithm is obviously better than the best algorithm obtained so far. This algorithm's computational speeds on the difficult instances are between 10 and 100 times faster than those of the best algorithm, on the condition of keeping the quality of the solutions same.
Secondly, inspired by the movement rule of the elastic objects of the physical world, a strategy that predicts the prospect of the search is obtained. It improves the performance of the search by early stopping the search that will get trapped in local minima; Inspired by the survival of the fittest principle of the nature, another strategy lets the search escape from local minima to the direction of better prospect by using the wisdom that human has accumulated in social events. The fast quasi-physical and quasi-human algorithm is obtained as the integration of the above two methods and the quasi-physical and quasi-human algorithm.
Thirdly, based on simulating the elastic objects movement, two heuristic algorithms are presented by using the idea of the simulated annealing algorithm. By accepting the new solution, whose quality is not better than the previous one, according to the different rules, the above two algorithms are possible to let the search escape from local minima and thus effectively solve the equal disks packing problem.
Finally, by effectively using obtained heuristic methods to solve a lot of instances, we study the working principle of the heuristic methods, and present a feasible plan to design the heuristic methods.
引文
[1] C. H.Papadimitriou,K.Steiglitz.Combinatorial Optimization: Algorithm and Complexity. Prentice-Hall Inc., 1982．(中译本：刘振宏，蔡茂诚译．组合最优 化算法和复杂性．第一版．北京：清华大学出版社，1988．198～247)
[2] 陈宝林．最优化理论与算法．第一版．北京：清华大学出版社，1989．1～8
[3] M.R. Garey, D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W.H. Freeman and Company, 1979. (中译本：张立昂，沈泓，毕源章．计算机和难解性：NP完全性理论导引．第一版．北京：科学出版社，1987．1～186)
[4] M.D. Davis, E.J. Weyuker. Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science. INC: Academic Press, 1983.(中译本：张立昂，耿素云译．可计算性、复杂性与语言：理论计算机科学基础．第一版．北京：清华大学出版社，1989．242～252)
[5] 王永庆．人工智能——原理·方法·应用．第一版．西安：西安交通大学出版社，1995．1～22
[6] N.J. Nillson. Problem-Solving Methods in Artificial Intelligence. 1st edition. New York: McGraw-Hill Press, 1971.1～14
[7] 陆汝钤．人工智能．第一版．北京：科学出版社，1989．1～146
[8] F. Glover. Tabu Search: Part Ⅰ. ORSA Journal on Computing, 1989 (1): 190～206
[9] F. Glover. Tabu Search: Part Ⅱ. ORSA Journal on Computing, 1990 (1): 4～32
[10] J. Hopfield, D. Tank. 'Neural' Computation of Decisions in Optimization Problems. Biological Cybernetics, 1985 (52): 141～152
[11] J. Hopfield, D. Tank. Computing with Neural Circuits: A Model. Science, 1986 (223): 625～633
[12] M. Dorigo, V. Maniezzo, A. Colony. Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics, 1996 (26/1): 29～41
[13] 康立山，谢云，尤矢勇，罗祖华．非数值并行算法(第一册)——模拟退火算法．第一版．北京：科学出版社，1998．22～55
[14] S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi. Optimization by Simulated Annealing. Science, 1983 (220): 671～689
[15] 陈国良，王煦法，庄镇泉，王东生．遗传算法及其应用．第一版．北京：人民邮电出版社，1996．101～163
[16] 刘勇，康立山，陈毓屏．非数值并行算法(第二册)——遗传算法．第一版．北京：科学出版社，1998．1～37
[17] G. Polya. How to Solve It? 1st edition. Princeton: Princeton University Press, 1948. 1～80
[18] H.I. Osman. Metaheuristics: A Bibliography. Annals of Operations Research, 1996 (63): 513～623
[19] 黄文奇，詹叔浩．求解Packing问题的拟物方法．应用数学学报，1979(2／2)：176～180
[20] 黄文奇．求解Covering问题的拟物方法——NP难度问题的一个处理途径．计算机学报，1989(8)：610～616
[21] 黄文奇，陈亮．求解有关空间利用的调度问题的拟物方法．中国科学，A辑，1991(3)：325～331
[22] 黄文奇．处理NP难度问题的拟物和拟人方法．国际离散数学与算法研讨会文集，暨南大学出版社，广州，1994
[23] 李未，黄文奇．一种求解合取范式可满足问题的数学物理方法．中国科学，A辑，1994(24／11)，1208～1217
[24] 黄文奇，金人超．求解SAT问题的拟物拟人算——Solar．中国科学，E辑，1997(27／2)：179～186
[25] 黄文奇，许如初．支持求解圆形Packing问题的两个拟人策略．中国科学，E辑，1999(29／4)：347～353
[26] Yu-Liang Wu, Wenqi Huang, Siu-Chung Lau, C.K. Wong, G. H. Young. An Effective Quasi-Human Based Heuristic for Solving the Rectangle Packing Problem. European Journal of Operational Research, 2002 (141): 341～358
[27] E.R. Paternoster, P.E. Sweehey. Cutting and Packing Problems: A Categorized Application-Orientated Research Bibliography. Journal of the Operational Research Society, 1992 (7): 691- 706
[28] K.A. Dowsland, W.B. Dowsland. Packing problems. European Journal of Operational Research, 1992 (56/1): 2～14
[29] E.E. Bischoff, G. Wascher. Cutting and Packing. European Journal of
Operational Research, 1995 (84) : 503-505
[30] H. Dyckhoff, G Scheithauer, J. Terno. Cutting and Packing (C&P). Annotated Bibliographies in Combinatorial Optimization. Chichester: John Wiley & Sons Press, 1997． 393-412
[31] P.Y. Wang, G Wascher. Cutting and Packing. European Journal of Operational Research, 2002 (141) : 239-240
[32] E.G Coffman, M.R. Garey, D.S. Johnson. Approximation Algorithms for Bin-Packing-An Updated Survey. Algorithms Design for Computer Systems Design. 1st edition. Vienna: Springer Verlag Press, 1984． 49-106
[33] S.C. Sarin. Two-Dimensional Stock Cutting Problems and Solution Methodologies. ASME Transactions Journal of Engineering for Industry, 1983 (104) : 155-160
[34] R.W. Haessler, P.E. Sweeney. Cutting Stock Problems and Solution Procedures. European Journal of Operational Research, 1991 (54) : 141-150
[35] S. Eilon, N. Christofides. The Loading Problem. Management Science, 1971 (17) : 259-268
[36] D. Pisinger, P. Toth. Knapsack Problems, Handbook of Combinatorial Optimization. 1st edition. Boston: Kluwer Academic Publishers, 1998． 299-428
[37] H. Dyckhoff. Typology of Cutting and Packing Problems. European Journal of Operational Research, 1990 (44) : 145-159
[38] R.L. Brooks, C.A.B. Smith, W.T. Tutte. The Dissection of Rectangles into Squares. Duke Mathematical Journal, 1940 (7) : 312-340
[39] J.H. Conway. Mrs. Perking's quilt. Proceedings of the Cambridge Philosophical Society, 1964 (60) : 363-368
[40] L.V. Kantorovich. Mathematical Methods of Organising and Planning Production. Management Science, 1960 (6) : 366-422
[41] E. Eilon. Optimising the Shearing of Steel Bars. Journal of Mechanical Engineering Science, 1960 (2) : 129-142
[42] P.C. Gilmore, R.E. Gomory. A Linear Programming Approach to the Cutting-Stock Problem (Part 1) . Operations Research, 1961 (9) : 849-859
[43] P.C. Gilmore, R.E. Gomory. A Linear Programming Approach to the Cutting-Stock Problem (Part 2) . Operations Research, 1963 (11) : 863-888
[44] B.S. Baker, E.G Coffman, R.L. Rivest. Orthogonal Packing in Two
Dimensional. SIAM Journal of Computing, 1980 (6) : 846-855
[45] G. Scheithauer. Equivalence and Dominance for Problems of Optimal Packing of Rectangles. Ricerca Operativa, 1997 (83) : 3-34
[46] A. Lodi, S. Martello, D. Vigo. Recent Advances on Two-Dimensional Bin Packing Problems. Discrete Applied Mathematics, 2002 (123/124) : 373-380
[47] A. Lodi, S. Martello, M. Monaci. Two-Dimensional Packing Problems: A Survey. European Journal of Operational Research, 2002 (141) : 241-252
[48] C. Kenyon, E. Remila. A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem. Mathematics of Operations Research, 2002 (25) : 645-656
[49] Faina, Loris. A Global Optimization Algorithm for the Three-Dimensional Packing Problem. European Journal of Operational Research, 2000 (126) : 340-354
[50] S. Martello, D. Pisinger, D. Vigo. The Three-Dimensional Bin Packing Problem. Operations Research, 2000 (48) : 256-267
[51] J.K. Lenstra, A.H.G Rinnooy Kan. Complexity of Packing, Covering, and Partitioning Problems, Packing and Covering in Combinatorics Mathematisch Centrum, Amsterdam: Elsevier science, 1979． 275-291
[52] R.J. Fowler, M.S. Paterson, S.L. Tanimoto. Optimal Packing and Covering in the Plane are NP-Complete. Information Processing Letters, 1981 (12/3) : 133-137
[53] B. Kroger, P. Schwenderling, O. Vornberger. Parallel Genetic Packing of Rectangles, Parallel Problem Solving from Nature First Workshop. 1st edition. Berlin: Springer Verlag Press, 1991． 160-164
[54] B. Kroger. Guillontineable Bin-packing: A Genetic Approach. European Journal of Operational Research, 1995 (84) : 645-661
[55] E.A. Herbert, K.A. Dowsland. A Family of Genetic Algorithms for the Pallet Loading Problem. Annals of Operations Research, 1996 (63) : 415-436
[56] S. Jacobs. On Genetic Algorithms for the Packing of Polygons. European Journal of Operational Research, 1996 (88) : 165-181
[57] K.K. Lai, W.M. Chan. An Evolutionary Algorithm for the Rectangular Cutting Stock Problem. International Journal of Industrial Engineering, 1997 (4) : 130-139
[58] E. Hopper, B.C.H. Turton. A Genetic Algorithm for a 2D Industrial Packing
Problem. Computers in Engineering 1999 (37) : 375-378．
[59] A. Bortfeldt, H. Gehring. A Hybrid Genetic Algorithm for the Container Loading Problem. European Journal of Operational Research, 2001 (131) : 143-161
[60] T. Kampke. Simulated Annealing: Use of a New Tool in Bin-Packing. Annals of Operations Research, 1988 (16) : 327-332
[61] K.A. Dowsland. Some Experiments with Simulated Annealing Techniques for Packing Problems. European Journal of Operational Research, 1993 (68) : 389-399
[62] L. Faina. An Application of Simulated Annealing to the Cutting Stock Problem. European Journal of Operational Research, 1999 (114) : 542-556
[63] A. Lodi, S. Martello, D. Vigo. Approximation Algorithms for the Oriented Two-Dimensional Bin Packing Problem. European Journal of Operational Research, 1999(112) : 158-166
[64] B. Chazelle. The Bottom-left Bin-Packing Heuristic: An Efficient Implementation. IEEE Transactions on Computers, 1983 (32/8) : 697-707
[65] K.A. Dowsland, S. Vaid, W.B. Dowsland. An Algorithm for Polygon Placement Using a Bottom-Left Strategy. European Journal of Operational Research, 2002 (141) : 371-381
[66] A. Albano, G Sappupo. A Heuristic Solution of the Rectangular Cutting Stock Problem. The Computer Journal, 1978 (23) : 338-343
[67] S.A. Roberts. Application of Heuristic Techniques to the Cutting-Stock Problem for Worktops. Journal of the Operational Research Society, 1984 (5) : 369-377
[68] A. Lodi, S. Martello, D. Vigo. Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problems. INFORMS Journal on Computing, 1999 (11) : 345-357
[69] E. Hopper, B.C.H. Turton. An Empirical Investigation of Meta-Heuristic and Heuristic Algorithms for a 2D Packing Problem. European Journal of Operational Research, 2000 (128) : 34-57
[70] G Yong-Gun, Kang, Maing-Kyu. A Fast Algorithm for Two-Dimensional Pallet Loading Problems of Large Size. European Journal of Operational Research, 2001 (134) : 193-202
[71] Pisinger, David. Heurisitcs for the Container Loading Problem. European
Journal of Operational Research, 2002 (141): 382～392
[72] A. Lodi, S. Martello, D. Vigo. Heuristic Algorithms for the Three-Dimensional Bin Packing Problem. European Journal of Operational Research, 2002 (141): 410～420
[73] 王金敏，陈东祥，查建中，王爱虎，章节笑．关于约束底盘装载问题的一种启发式算法．软件学报，1996(7／10)：616～620
[74] 袁苗龙，周济，张新访．三维几何布局的一类启发式求解算法．计算机学报，1999(22／9)：923～930
[75] 李言照，滕弘飞，钟万勰，娄汉文．旋转舱内长方体群的装填布局优化．宇航学报，1993(14／1)：37～43
[76] 滕弘飞，孙守林，葛文海，钟万勰．转动圆桌平衡摆盘——带平衡性能约束的Packing问题．中国科学，A辑，1994(24／7)：754～760
[77] 唐飞，滕弘飞．一种改进的遗传算法及其在布局优化中的应用．软件学报，1999(10／10)：1096～1102
[78] Dequan Liu, Hongfei Teng. An Improved BL-algorithm for Genetic Algorithm of the Orthogonal Packing of Rectangles. European Journal of Operational Research, 1999 (112): 413～420
[79] Hong-fei Teng, Shou-lin Sun, De-quan Liu, Yan-zhao Li. Layout Optimization for the Objects Located within a Rotating Vessel—A Three-Dimensional Packing Problem with Behavioral Constriants. Computers & Operations Research, 2001 (28): 521～535
[80] 钱志勤，滕弘飞，孙治国．人机交互的遗传算法及其在约束布局优化中的应用．计算机学报，2001(24／5)：553～559
[81] S. Kravitz. Packing Cylinders into Cylindrical Containers. Mathematics Magazine, 1967 (40): 65～71
[82] M. Goldberg. Packing of 14,16,17 and 20 Circles in a Circle. Mathematics Magazine, 1971 (44): 134～139
[83] G.E. Reis. Dense Packings of Equal Circles within a Circle. Mathematics Magazine, 1975 (48): 33～37
[84] J.B.M. Melissen. Densest Packing of Eleven Congruent Circles in a Circle. Geometriae Dedicata, 1994 (50): 15～25
[85] D. Lubachevsky, R.L. Graham. Curved Hexagonal Packing of Equal Disks in a Circle. Discrete & Computational Geometry, 1997 (18): 179～194
[86] R.L. Graham, B.D. Lubachevsky, K.J. Nurmela, P.R.J. Ostergard. Dense Packings of Congruent Circles in a Circle. Discrete Mathematics, 1998 (181) : 139-154
[87] F. Fodor. The Densest Packing of 19 Congruent Circles in a Circle. Geometriae Dedicata, 1999(74) : 139-145
[88] J.B.M. Melissen. Densest Packings for Congruent Circles in an Equilateral Triangle. American Mathematical Monthly, 1993 (100) : 916-925
[89] J.B.M. Melissen. Optimal Packings of Eleven Equal Circles in an Equilateral Triangle. Acta Mathematica Hungarica, 1994 (65) : 389-393
[90] J.B.M. Melissen, P.C. Schuur. Packing 16, 17 or 18 Circles in an Equilateral Triangle. Discrete Mathematics, 1995 (145) : 333-342
[91] J. Schaer. The Densest Packing of Nine Circles in a Square. Canadian Mathematical Bulletin, 1965 (8) : 273-277
[92] B.L. Schwartz. Separating Points in a Square. Journal of Recreational Mathmatics, 1970 (3) : 195-204
[93] M. Goldberg. The Packing of Equal Circles in a Square. Mathematics Magazine, 1970 (43) : 24-30
[94] J. Schaer. On the Densest Packing of Ten Equal Circles in a Square. Mathematics Magazine, 1971 (44) : 139-140
[95] G Valette. A Better Packing of Ten Circles in a Square. Discrete Mathematics, 1989 (76) : 57-59
[96] M. Mollard, C. Payan. Some Progress in the Packing of Equal Circles in a Square. Discrete Mathematics, 1990 (84) : 303-307
[97] R. Perkert, D. Wtlrtz, M. Monagan, C. de Groot. Packing Circles in a Square: A Review and New Results, System Modelling and Optimization, Volume 180 of Lecture Notes in Control and Information Sciences. 1st edition. Berlin: Springer Verlag Press, 1992． 45-54
[98] D. Wtlrtz, M. Monagan, R. Peikert. The History of Packing Circles in a Square. Maple Technical Newsletter. Maple in Mathematics and the Sciences-A Special Issue, 1994 (0) : 35-42
[99] H. Melissen. Densest Packing of Six Equal Circles in a Square. Elemente der Mathematik, 1994 (49) : 27-31
[100] C.D. Maranas, C.A. Floudas, P.M. Pardalos. New Results in the Packing of
Equal Circles in a Square. Discrete Mathematics, 1995 (142): 287～293
[101] H. Isermann, Heuristiken zur Lsung. Des zweidi-mensionalen Packproblems fr Rundgefβe. OR Spektrum, 1991 (13): 213～223
[102] H.J. Fraser, J.A. George. Integrated Container Loading Software for Pulp and Paper Industry. European Journal of Operational Research, 1994 (77/3): 466～474
[103] K.A. Dowsland. Palletisation of Cylinders in Cases. OR Spektrum, 1991 (13): 171～172
[104] J.A. George, J.M. George, B. W. Lamar. Packing Different-sized Disks into a Rectangular Container. European Journal of Operational Research, 1995 (84): 693～712
[105] J.A. George. Multiple Container Packing: A Case Study of Pipe Packing. Journal of Operational Research Society, 1996, 1098～1109
[106] D.S. Hochbaum, W. Maass. Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI. Journal of the Association for Computing Machinery, 1985 (23/1): 130～136
[107] B.D. Lubachevsky. How to Simulate Billiards and Similar Systems. Journal of Computational Physics, 1991 (94): 255～283
[108] 康立山，谢云，尤矢勇，罗祖华．非数值并行算法(第一册)——模拟退火算法．第一版．北京：科学出版社，1998．10～37
[109] Huang Wenqi, Kang Yan. A Heuristic Quasi-Physical Strategy for Solving Disks Packing Problem. Simulation Modelling Practice and Theory. To appear
[110] 康雁，黄文奇．求解圆形packing问题的一个启发式算法．计算机研究与发展，2002(39／4)：410～414．
[111] Huang Wenqi, Kang Yan. A Short Note on a Simple Search Heuristic for the Disks Packing Problem. Annals of Operations Research, To appear
[2] 陈宝林．最优化理论与算法．第一版．北京：清华大学出版社，1989．1～8
[3] M.R. Garey, D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W.H. Freeman and Company, 1979. (中译本：张立昂，沈泓，毕源章．计算机和难解性：NP完全性理论导引．第一版．北京：科学出版社，1987．1～186)
[4] M.D. Davis, E.J. Weyuker. Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science. INC: Academic Press, 1983.(中译本：张立昂，耿素云译．可计算性、复杂性与语言：理论计算机科学基础．第一版．北京：清华大学出版社，1989．242～252)
[5] 王永庆．人工智能——原理·方法·应用．第一版．西安：西安交通大学出版社，1995．1～22
[6] N.J. Nillson. Problem-Solving Methods in Artificial Intelligence. 1st edition. New York: McGraw-Hill Press, 1971.1～14
[7] 陆汝钤．人工智能．第一版．北京：科学出版社，1989．1～146
[8] F. Glover. Tabu Search: Part Ⅰ. ORSA Journal on Computing, 1989 (1): 190～206
[9] F. Glover. Tabu Search: Part Ⅱ. ORSA Journal on Computing, 1990 (1): 4～32
[10] J. Hopfield, D. Tank. 'Neural' Computation of Decisions in Optimization Problems. Biological Cybernetics, 1985 (52): 141～152
[11] J. Hopfield, D. Tank. Computing with Neural Circuits: A Model. Science, 1986 (223): 625～633
[12] M. Dorigo, V. Maniezzo, A. Colony. Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics, 1996 (26/1): 29～41
[13] 康立山，谢云，尤矢勇，罗祖华．非数值并行算法(第一册)——模拟退火算法．第一版．北京：科学出版社，1998．22～55
[14] S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi. Optimization by Simulated Annealing. Science, 1983 (220): 671～689
[15] 陈国良，王煦法，庄镇泉，王东生．遗传算法及其应用．第一版．北京：人民邮电出版社，1996．101～163
[16] 刘勇，康立山，陈毓屏．非数值并行算法(第二册)——遗传算法．第一版．北京：科学出版社，1998．1～37
[17] G. Polya. How to Solve It? 1st edition. Princeton: Princeton University Press, 1948. 1～80
[18] H.I. Osman. Metaheuristics: A Bibliography. Annals of Operations Research, 1996 (63): 513～623
[19] 黄文奇，詹叔浩．求解Packing问题的拟物方法．应用数学学报，1979(2／2)：176～180
[20] 黄文奇．求解Covering问题的拟物方法——NP难度问题的一个处理途径．计算机学报，1989(8)：610～616
[21] 黄文奇，陈亮．求解有关空间利用的调度问题的拟物方法．中国科学，A辑，1991(3)：325～331
[22] 黄文奇．处理NP难度问题的拟物和拟人方法．国际离散数学与算法研讨会文集，暨南大学出版社，广州，1994
[23] 李未，黄文奇．一种求解合取范式可满足问题的数学物理方法．中国科学，A辑，1994(24／11)，1208～1217
[24] 黄文奇，金人超．求解SAT问题的拟物拟人算——Solar．中国科学，E辑，1997(27／2)：179～186
[25] 黄文奇，许如初．支持求解圆形Packing问题的两个拟人策略．中国科学，E辑，1999(29／4)：347～353
[26] Yu-Liang Wu, Wenqi Huang, Siu-Chung Lau, C.K. Wong, G. H. Young. An Effective Quasi-Human Based Heuristic for Solving the Rectangle Packing Problem. European Journal of Operational Research, 2002 (141): 341～358
[27] E.R. Paternoster, P.E. Sweehey. Cutting and Packing Problems: A Categorized Application-Orientated Research Bibliography. Journal of the Operational Research Society, 1992 (7): 691- 706
[28] K.A. Dowsland, W.B. Dowsland. Packing problems. European Journal of Operational Research, 1992 (56/1): 2～14
[29] E.E. Bischoff, G. Wascher. Cutting and Packing. European Journal of
Operational Research, 1995 (84) : 503-505
[30] H. Dyckhoff, G Scheithauer, J. Terno. Cutting and Packing (C&P). Annotated Bibliographies in Combinatorial Optimization. Chichester: John Wiley & Sons Press, 1997． 393-412
[31] P.Y. Wang, G Wascher. Cutting and Packing. European Journal of Operational Research, 2002 (141) : 239-240
[32] E.G Coffman, M.R. Garey, D.S. Johnson. Approximation Algorithms for Bin-Packing-An Updated Survey. Algorithms Design for Computer Systems Design. 1st edition. Vienna: Springer Verlag Press, 1984． 49-106
[33] S.C. Sarin. Two-Dimensional Stock Cutting Problems and Solution Methodologies. ASME Transactions Journal of Engineering for Industry, 1983 (104) : 155-160
[34] R.W. Haessler, P.E. Sweeney. Cutting Stock Problems and Solution Procedures. European Journal of Operational Research, 1991 (54) : 141-150
[35] S. Eilon, N. Christofides. The Loading Problem. Management Science, 1971 (17) : 259-268
[36] D. Pisinger, P. Toth. Knapsack Problems, Handbook of Combinatorial Optimization. 1st edition. Boston: Kluwer Academic Publishers, 1998． 299-428
[37] H. Dyckhoff. Typology of Cutting and Packing Problems. European Journal of Operational Research, 1990 (44) : 145-159
[38] R.L. Brooks, C.A.B. Smith, W.T. Tutte. The Dissection of Rectangles into Squares. Duke Mathematical Journal, 1940 (7) : 312-340
[39] J.H. Conway. Mrs. Perking's quilt. Proceedings of the Cambridge Philosophical Society, 1964 (60) : 363-368
[40] L.V. Kantorovich. Mathematical Methods of Organising and Planning Production. Management Science, 1960 (6) : 366-422
[41] E. Eilon. Optimising the Shearing of Steel Bars. Journal of Mechanical Engineering Science, 1960 (2) : 129-142
[42] P.C. Gilmore, R.E. Gomory. A Linear Programming Approach to the Cutting-Stock Problem (Part 1) . Operations Research, 1961 (9) : 849-859
[43] P.C. Gilmore, R.E. Gomory. A Linear Programming Approach to the Cutting-Stock Problem (Part 2) . Operations Research, 1963 (11) : 863-888
[44] B.S. Baker, E.G Coffman, R.L. Rivest. Orthogonal Packing in Two
Dimensional. SIAM Journal of Computing, 1980 (6) : 846-855
[45] G. Scheithauer. Equivalence and Dominance for Problems of Optimal Packing of Rectangles. Ricerca Operativa, 1997 (83) : 3-34
[46] A. Lodi, S. Martello, D. Vigo. Recent Advances on Two-Dimensional Bin Packing Problems. Discrete Applied Mathematics, 2002 (123/124) : 373-380
[47] A. Lodi, S. Martello, M. Monaci. Two-Dimensional Packing Problems: A Survey. European Journal of Operational Research, 2002 (141) : 241-252
[48] C. Kenyon, E. Remila. A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem. Mathematics of Operations Research, 2002 (25) : 645-656
[49] Faina, Loris. A Global Optimization Algorithm for the Three-Dimensional Packing Problem. European Journal of Operational Research, 2000 (126) : 340-354
[50] S. Martello, D. Pisinger, D. Vigo. The Three-Dimensional Bin Packing Problem. Operations Research, 2000 (48) : 256-267
[51] J.K. Lenstra, A.H.G Rinnooy Kan. Complexity of Packing, Covering, and Partitioning Problems, Packing and Covering in Combinatorics Mathematisch Centrum, Amsterdam: Elsevier science, 1979． 275-291
[52] R.J. Fowler, M.S. Paterson, S.L. Tanimoto. Optimal Packing and Covering in the Plane are NP-Complete. Information Processing Letters, 1981 (12/3) : 133-137
[53] B. Kroger, P. Schwenderling, O. Vornberger. Parallel Genetic Packing of Rectangles, Parallel Problem Solving from Nature First Workshop. 1st edition. Berlin: Springer Verlag Press, 1991． 160-164
[54] B. Kroger. Guillontineable Bin-packing: A Genetic Approach. European Journal of Operational Research, 1995 (84) : 645-661
[55] E.A. Herbert, K.A. Dowsland. A Family of Genetic Algorithms for the Pallet Loading Problem. Annals of Operations Research, 1996 (63) : 415-436
[56] S. Jacobs. On Genetic Algorithms for the Packing of Polygons. European Journal of Operational Research, 1996 (88) : 165-181
[57] K.K. Lai, W.M. Chan. An Evolutionary Algorithm for the Rectangular Cutting Stock Problem. International Journal of Industrial Engineering, 1997 (4) : 130-139
[58] E. Hopper, B.C.H. Turton. A Genetic Algorithm for a 2D Industrial Packing
Problem. Computers in Engineering 1999 (37) : 375-378．
[59] A. Bortfeldt, H. Gehring. A Hybrid Genetic Algorithm for the Container Loading Problem. European Journal of Operational Research, 2001 (131) : 143-161
[60] T. Kampke. Simulated Annealing: Use of a New Tool in Bin-Packing. Annals of Operations Research, 1988 (16) : 327-332
[61] K.A. Dowsland. Some Experiments with Simulated Annealing Techniques for Packing Problems. European Journal of Operational Research, 1993 (68) : 389-399
[62] L. Faina. An Application of Simulated Annealing to the Cutting Stock Problem. European Journal of Operational Research, 1999 (114) : 542-556
[63] A. Lodi, S. Martello, D. Vigo. Approximation Algorithms for the Oriented Two-Dimensional Bin Packing Problem. European Journal of Operational Research, 1999(112) : 158-166
[64] B. Chazelle. The Bottom-left Bin-Packing Heuristic: An Efficient Implementation. IEEE Transactions on Computers, 1983 (32/8) : 697-707
[65] K.A. Dowsland, S. Vaid, W.B. Dowsland. An Algorithm for Polygon Placement Using a Bottom-Left Strategy. European Journal of Operational Research, 2002 (141) : 371-381
[66] A. Albano, G Sappupo. A Heuristic Solution of the Rectangular Cutting Stock Problem. The Computer Journal, 1978 (23) : 338-343
[67] S.A. Roberts. Application of Heuristic Techniques to the Cutting-Stock Problem for Worktops. Journal of the Operational Research Society, 1984 (5) : 369-377
[68] A. Lodi, S. Martello, D. Vigo. Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problems. INFORMS Journal on Computing, 1999 (11) : 345-357
[69] E. Hopper, B.C.H. Turton. An Empirical Investigation of Meta-Heuristic and Heuristic Algorithms for a 2D Packing Problem. European Journal of Operational Research, 2000 (128) : 34-57
[70] G Yong-Gun, Kang, Maing-Kyu. A Fast Algorithm for Two-Dimensional Pallet Loading Problems of Large Size. European Journal of Operational Research, 2001 (134) : 193-202
[71] Pisinger, David. Heurisitcs for the Container Loading Problem. European
Journal of Operational Research, 2002 (141): 382～392
[72] A. Lodi, S. Martello, D. Vigo. Heuristic Algorithms for the Three-Dimensional Bin Packing Problem. European Journal of Operational Research, 2002 (141): 410～420
[73] 王金敏，陈东祥，查建中，王爱虎，章节笑．关于约束底盘装载问题的一种启发式算法．软件学报，1996(7／10)：616～620
[74] 袁苗龙，周济，张新访．三维几何布局的一类启发式求解算法．计算机学报，1999(22／9)：923～930
[75] 李言照，滕弘飞，钟万勰，娄汉文．旋转舱内长方体群的装填布局优化．宇航学报，1993(14／1)：37～43
[76] 滕弘飞，孙守林，葛文海，钟万勰．转动圆桌平衡摆盘——带平衡性能约束的Packing问题．中国科学，A辑，1994(24／7)：754～760
[77] 唐飞，滕弘飞．一种改进的遗传算法及其在布局优化中的应用．软件学报，1999(10／10)：1096～1102
[78] Dequan Liu, Hongfei Teng. An Improved BL-algorithm for Genetic Algorithm of the Orthogonal Packing of Rectangles. European Journal of Operational Research, 1999 (112): 413～420
[79] Hong-fei Teng, Shou-lin Sun, De-quan Liu, Yan-zhao Li. Layout Optimization for the Objects Located within a Rotating Vessel—A Three-Dimensional Packing Problem with Behavioral Constriants. Computers & Operations Research, 2001 (28): 521～535
[80] 钱志勤，滕弘飞，孙治国．人机交互的遗传算法及其在约束布局优化中的应用．计算机学报，2001(24／5)：553～559
[81] S. Kravitz. Packing Cylinders into Cylindrical Containers. Mathematics Magazine, 1967 (40): 65～71
[82] M. Goldberg. Packing of 14,16,17 and 20 Circles in a Circle. Mathematics Magazine, 1971 (44): 134～139
[83] G.E. Reis. Dense Packings of Equal Circles within a Circle. Mathematics Magazine, 1975 (48): 33～37
[84] J.B.M. Melissen. Densest Packing of Eleven Congruent Circles in a Circle. Geometriae Dedicata, 1994 (50): 15～25
[85] D. Lubachevsky, R.L. Graham. Curved Hexagonal Packing of Equal Disks in a Circle. Discrete & Computational Geometry, 1997 (18): 179～194
[86] R.L. Graham, B.D. Lubachevsky, K.J. Nurmela, P.R.J. Ostergard. Dense Packings of Congruent Circles in a Circle. Discrete Mathematics, 1998 (181) : 139-154
[87] F. Fodor. The Densest Packing of 19 Congruent Circles in a Circle. Geometriae Dedicata, 1999(74) : 139-145
[88] J.B.M. Melissen. Densest Packings for Congruent Circles in an Equilateral Triangle. American Mathematical Monthly, 1993 (100) : 916-925
[89] J.B.M. Melissen. Optimal Packings of Eleven Equal Circles in an Equilateral Triangle. Acta Mathematica Hungarica, 1994 (65) : 389-393
[90] J.B.M. Melissen, P.C. Schuur. Packing 16, 17 or 18 Circles in an Equilateral Triangle. Discrete Mathematics, 1995 (145) : 333-342
[91] J. Schaer. The Densest Packing of Nine Circles in a Square. Canadian Mathematical Bulletin, 1965 (8) : 273-277
[92] B.L. Schwartz. Separating Points in a Square. Journal of Recreational Mathmatics, 1970 (3) : 195-204
[93] M. Goldberg. The Packing of Equal Circles in a Square. Mathematics Magazine, 1970 (43) : 24-30
[94] J. Schaer. On the Densest Packing of Ten Equal Circles in a Square. Mathematics Magazine, 1971 (44) : 139-140
[95] G Valette. A Better Packing of Ten Circles in a Square. Discrete Mathematics, 1989 (76) : 57-59
[96] M. Mollard, C. Payan. Some Progress in the Packing of Equal Circles in a Square. Discrete Mathematics, 1990 (84) : 303-307
[97] R. Perkert, D. Wtlrtz, M. Monagan, C. de Groot. Packing Circles in a Square: A Review and New Results, System Modelling and Optimization, Volume 180 of Lecture Notes in Control and Information Sciences. 1st edition. Berlin: Springer Verlag Press, 1992． 45-54
[98] D. Wtlrtz, M. Monagan, R. Peikert. The History of Packing Circles in a Square. Maple Technical Newsletter. Maple in Mathematics and the Sciences-A Special Issue, 1994 (0) : 35-42
[99] H. Melissen. Densest Packing of Six Equal Circles in a Square. Elemente der Mathematik, 1994 (49) : 27-31
[100] C.D. Maranas, C.A. Floudas, P.M. Pardalos. New Results in the Packing of
Equal Circles in a Square. Discrete Mathematics, 1995 (142): 287～293
[101] H. Isermann, Heuristiken zur Lsung. Des zweidi-mensionalen Packproblems fr Rundgefβe. OR Spektrum, 1991 (13): 213～223
[102] H.J. Fraser, J.A. George. Integrated Container Loading Software for Pulp and Paper Industry. European Journal of Operational Research, 1994 (77/3): 466～474
[103] K.A. Dowsland. Palletisation of Cylinders in Cases. OR Spektrum, 1991 (13): 171～172
[104] J.A. George, J.M. George, B. W. Lamar. Packing Different-sized Disks into a Rectangular Container. European Journal of Operational Research, 1995 (84): 693～712
[105] J.A. George. Multiple Container Packing: A Case Study of Pipe Packing. Journal of Operational Research Society, 1996, 1098～1109
[106] D.S. Hochbaum, W. Maass. Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI. Journal of the Association for Computing Machinery, 1985 (23/1): 130～136
[107] B.D. Lubachevsky. How to Simulate Billiards and Similar Systems. Journal of Computational Physics, 1991 (94): 255～283
[108] 康立山，谢云，尤矢勇，罗祖华．非数值并行算法(第一册)——模拟退火算法．第一版．北京：科学出版社，1998．10～37
[109] Huang Wenqi, Kang Yan. A Heuristic Quasi-Physical Strategy for Solving Disks Packing Problem. Simulation Modelling Practice and Theory. To appear
[110] 康雁，黄文奇．求解圆形packing问题的一个启发式算法．计算机研究与发展，2002(39／4)：410～414．
[111] Huang Wenqi, Kang Yan. A Short Note on a Simple Search Heuristic for the Disks Packing Problem. Annals of Operations Research, To appear