×

A new quasi-human algorithm for solving the packing problem of unit equilateral triangles. (English) Zbl 1470.90108

Summary: The packing problem of unit equilateral triangles not only has the theoretical significance but also offers broad prospects in material processing and network resource optimization. Because this problem is nondeterministic polynomial (NP) hard and has the feature of continuity, it is necessary to limit the placements of unit equilateral triangles before optimizing and obtaining approximate solution (e.g., the unit equilateral triangles are not allowed to be rotated). This paper adopts a new quasi-human strategy to study the packing problem of unit equilateral triangles. Some new concepts are put forward such as side-clinging action, and an approximation algorithm for solving the addressed problem is designed. Time complexity analysis and the calculation results indicate that the proposed method is a polynomial time algorithm, which provides the possibility to solve the packing problem of arbitrary triangles.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming

Software:

Packlib2; OR-Library
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dyckhoff, H., A typology of cutting and packing problems, European Journal of Operational Research, 44, 2, 145-159 (1990) · Zbl 0684.90076 · doi:10.1016/0377-2217(90)90350-K
[2] Wäscher, G.; Haußner, H.; Schumann, H., An improved typology of cutting and packing problems, European Journal of Operational Research, 183, 3, 1109-1130 (2007) · Zbl 1278.90347 · doi:10.1016/j.ejor.2005.12.047
[3] Barnes, F. W., Best packing of rods into boxes, Discrete Mathematics, 142, 1-3, 271-275 (1995) · Zbl 0832.05025 · doi:10.1016/0012-365X(94)00020-J
[4] Fekete, S. P.; Schepers, J., A combinatorial characterization of higher-dimensional orthogonal packing, Mathematics of Operations Research, 29, 2, 353-368 (2004) · Zbl 1082.90095 · doi:10.1287/moor.1030.0079
[5] Fekete, S. P.; Schepers, J., A general framework for bounds for higher-dimensional orthogonal packing problems, Mathematical Methods of Operations Research, 60, 2, 311-329 (2004) · Zbl 1076.90049 · doi:10.1007/s001860400376
[6] Fekete, S. P.; Schepers, J.; Van der Veen, J. C., An exact algorithm for higher-dimensional orthogonal packing, Operations Research, 55, 3, 569-587 (2007) · Zbl 1167.90483 · doi:10.1287/opre.1060.0369
[7] Beasley, J. E., OR-Library: distributing test problems by electronic mail, Journal of the Operational Research Society, 41, 11, 1069-1072 (1990) · doi:10.1057/jors.1990.166
[8] Fekete, S. P.; van der Veen, J. C., \(PackLib^2\): an integrated library of multi-dimensional packing problems, European Journal of Operational Research, 183, 3, 1131-1135 (2007) · Zbl 1136.90452 · doi:10.1016/j.ejor.2006.04.023
[9] Parreño, F.; Alvarez-Valdes, R.; Tamarit, J. M.; Oliveira, J. F., A maximal-space algorithm for the container loading problem, INFORMS Journal on Computing, 20, 3, 413-422 (2008) · Zbl 1243.90094 · doi:10.1287/ijoc.l070.0254
[10] Parreño, F.; Alvarez-Valdes, R.; Oliveira, J. F.; Tamarit, J. M., Neighborhood structures for the container loading problem: a VNS implementation, Journal of Heuristics, 16, 1, 1-22 (2010) · Zbl 1184.90174 · doi:10.1007/s10732-008-9081-3
[11] Lu, Z.; Huang, W., PERM for solving circle packing problem, Computers & Operations Research, 35, 5, 1742-1755 (2008) · Zbl 1211.90198 · doi:10.1016/j.cor.2006.10.012
[12] Addis, B.; Locatelli, M.; Schoen, F., Disk packing in a square: a new global optimization approach, Informs Journal on Computing, 20, 4, 516-524 (2008) · Zbl 1243.90084 · doi:10.1287/ijoc.l080.0263
[13] Wenqi, H.; Yan, K., A heuristic quasi-physical strategy for solving disks packing problem, Simulation Modelling Practice and Theory, 10, 3-4, 195-207 (2002) · Zbl 1011.68829 · doi:10.1016/S1569-190X(02)00099-0
[14] He, K.; Mo, D.; Ye, T.; Huang, W., A coarse-to-fine quasi-physical optimization method for solving the circle packing problem with equilibrium constraints, Computers & Industrial Engineering, 66, 4, 1049-1060 (2013)
[15] Eley, M., Solving container loading problems by block arrangement, European Journal of Operational Research, 141, 2, 393-409 (2002) · Zbl 1081.90610 · doi:10.1016/S0377-2217(02)00133-9
[16] Ngoi, B. K. A.; Tay, M. L.; Chua, E. S., Applying spatial representation techniques to the container packing problem, International Journal of Production Research, 32, 1, 111-123 (1994) · Zbl 0905.90145 · doi:10.1080/00207549408956919
[17] Gehring, H.; Bortfeldt, A., A genetic algorithm for solving the container loading problem, International Transactions in Operational Research, 4, 5-6, 401-418 (1997) · Zbl 0906.90145 · doi:10.1111/j.1475-3995.1997.tb00095.x
[18] Wang, Z.; Li, K. W.; Levy, J. K., A heuristic for the container loading problem: a tertiary-tree-based dynamic space decomposition approach, European Journal of Operational Research, 191, 1, 84-97 (2008) · Zbl 1146.90507 · doi:10.1016/j.ejor.2007.08.017
[19] Lu, Y. P.; Zha, J. Z., Sequence triplet method for 3D rectangle packing problem, Journal of Software, 13, 11, 2183-2187 (2002)
[20] Beasley, J. E., A population heuristic for constrained two-dimensional non-guillotine cutting, European Journal of Operational Research, 156, 3, 601-627 (2004) · Zbl 1056.90011 · doi:10.1016/S0377-2217(03)00139-5
[21] Wu, Y. L.; Huang, W.; Lau, S. C.; Wong, C. K.; Young, G. H., An effective quasi-human based heuristic for solving the rectangle packing problem, European Journal of Operational Research, 141, 2, 341-358 (2002) · Zbl 1081.90615 · doi:10.1016/S0377-2217(02)00129-7
[22] Zhang, D.; Deng, A.; Kang, Y., A hybrid heuristic algorithm for the rectangular packing problem, Proceedings of the 5th International Conference on Computational Science (ICCS ’05)
[23] Wang, R.; Luo, Y.; Dong, J.; Liu, S.; Qi, X., A heuristic algorithm for solving triangle packing problem, Discrete Dynamics in Nature and Society, 2013 (2013) · doi:10.1155/2013/686845
[24] Zhang, S.; Wang, Z.; Ding, D.; Shu, H., Fuzzy filtering with randomly occurring parameter uncertainties, interval delays, and channel fadings, IEEE Transactions on Cybernetics, 44, 3, 406-417 (2014)
[25] Zhang, S.; Wang, Z.; Ding, D.; Shu, H., \(H_\infty\) fuzzy control with randomly occurr ing infinite distributed delays and channel fadings, IEEE Transactions on Fuzzy Systems, 22, 1, 189-200 (2014)
[26] Dong, H.; Wang, Z.; Gao, H., Distributed \(H_\infty\) filtering for a class of markovian jump nonlinear time-delay systems over lossy sensor networks, IEEE Transactions on Industrial Electronics, 60, 10, 4665-4672 (2013) · doi:10.1109/TIE.2012.2213553
[27] He, X.; Wang, Z.; Liu, Y.; Zhou, D. H., Least-squares fault detection and diagnosis for networked sensing systems using a direct state estimation approach, IEEE Transactions on Industrial Informatics, 9, 3, 1670-1679 (2013) · doi:10.1109/TII.2013.2251891
[28] He, X.; Wang, Z.; Wang, X.; Zhou, D. H., Networked strong tracking filtering with multiple packet dropouts: algorithms and applications, IEEE Transactions on Industrial Electronics, 61, 3, 1454-1463 (2014) · doi:10.1109/TIE.2013.2261038
[29] Shen, B.; Wang, Z.; Ding, D.; Shu, H., \(H_\infty\) state estimation for comple x networks with uncertain inner coupling and incomplete measurements, IEEE Transactions on Neural Networks and Learning Systems, 24, 12, 2027-2037 (2013) · doi:10.1109/TNNLS.2013.2271357
[30] Wang, Z.; Ding, D.; Dong, H.; Shu, H., H∞ consensus control for multi-agent systems with missing measurements: the finite-horizon case, Systems and Control Letters, 62, 10, 827-836 (2013) · Zbl 1281.93010 · doi:10.1016/j.sysconle.2013.06.004
[31] Ding, D.; Wang, Z.; Hu, J.; Shu, H., Dissipative control for state-saturated discrete time-varying systems with randomly occurring nonlinearities and missing measurements, International Journal of Control, 86, 4, 674-688 (2013) · Zbl 1278.93279 · doi:10.1080/00207179.2012.757652
[32] Ding, D.; Wang, Z.; Shen, B.; Shu, H., State-saturated \(H_\infty\) filtering with randomly occurring nonlinearities and packet dropouts: the finite-horizon case, International Journal of Robust and Nonlinear Control, 23, 16, 1803-1821 (2013) · Zbl 1285.93096 · doi:10.1002/rnc.2850
[33] Hu, J.; Wang, Z.; Shen, B.; Gao, H., Quantised recursive filtering for a class of nonlinear systems with multiplicative noises and missing measurements, International Journal of Control, 86, 4, 650-663 (2013) · Zbl 1278.93269 · doi:10.1080/00207179.2012.756149
[34] Hu, J.; Wang, Z.; Gao, H., Recursive filtering with random parameter matrices, multiple fading measurements and correlated noises, Automatica, 49, 11, 3440-3448 (2013) · Zbl 1315.93081
[35] Wang, Z.; Dong, H.; Shen, B.; Gao, H., Finite-horizon \(H_\infty\) filtering with missing measurements and quantization effects, IEEE Transactions on Automatic Control, 58, 7, 1707-1718 (2013) · Zbl 1369.93660 · doi:10.1109/TAC.2013.2241492
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.