Topology Optimization of Architectural Panels to Minimize Waste during Fabrication: Algorithms for Panel Unfolding and Nesting
Publication: Journal of Construction Engineering and Management
Volume 147, Issue 7
Abstract
The need to optimize the geometry and topology of construction components and assemblies can often be framed as combinatorial optimization problems (COPs). Such COPs occur throughout construction and are particularly relevant in architectural panel systems, given the complexity of panel topology, large component quantity in most projects, and the need to reduce waste produced during fabrication. The contribution of this paper is the development of novel combinatorial optimization algorithms for unfolding and nesting panels: a process that is central to realizing a fully automated and optimized file-to-factory system. The first algorithm for panel unfolding explores both enumerative and metaheuristic optimization to determine circumstances and applications where each are favorable. Then, a modified two-dimensional (2D) cutting stock algorithm using metaheuristics is developed for deriving optimal nest configurations. The combination of these novel algorithms is shown to produce 11% less fabrication waste in a case study for a typical residential construction project.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
Some or all data (e.g., Excel file analysis), models (e.g., Rhinoceros files), or code (e.g., the Grasshopper programs) that support the findings of this study are available from the corresponding author upon reasonable request.
Acknowledgments
The authors acknowledge the financial support of the Natural Sciences and Engineering Research Council (NSERC) of Canada, Mitacs Accelerate, and Edge Architects for this research.
References
Agirbas, A. 2019. “Façade form-finding with swarm intelligence.” Autom. Constr. 99 (Mar): 140–151. https://doi.org/10.1016/j.autcon.2018.12.003.
Ali, A. K., O. J. Lee, and H. Song. 2021. “Robot-based facade spatial assembly optimization.” J. Build. Eng. 33 (Jan): 101556. https://doi.org/10.1016/j.jobe.2020.101556.
Amiri, R., J. M. Sardroud, and B. G. de Soto. 2017. “BIM-based applications of metaheuristic algorithms to support the decision-making process: Uses in the planning of construction site layout.” Procedia Eng. 196 (Jan): 558–564. https://doi.org/10.1016/j.proeng.2017.08.030.
Anagnostopoulos, K. P., and G. K. Koulinas. 2010. “A simulated annealing hyperheuristic for construction resource levelling.” Constr. Manage. Econ. 28 (2): 163–175. https://doi.org/10.1080/01446190903369907.
AXYZ. 2020. “CNC router for ACM fabricated panels: PANELBuilder.” Accessed 17 August, 2020. https://www.axyz.com/us/product/panelbuilder/.
Beghini, L. L., A. Beghini, N. Katz, W. F. Baker, and G. H. Paulino. 2014. “Connecting architecture and engineering through structural topology optimization.” Eng. Struct. 59: 716–726. https://doi.org/10.1016/j.engstruct.2013.10.032.
Blum, C., and A. Roli. 2003. “Metaheuristics in combinatorial optimization: Overview and conceptual comparison.” ACM Comput. Surv. 35 (3): 268–308. https://doi.org/10.1145/937503.937505.
Blum, C., A. Roli, and M. Sampels. 2008. Hybrid metaheuristics: An emerging approach to optimization. Berlin: Springer.
Boschetti, M. A., and L. Montaletti. 2010. “An exact algorithm for the two-dimensional strip-packing problem.” Oper. Res. 58 (6): 1774–1791. https://doi.org/10.1287/opre.1100.0833.
Camp, C. V., B. J. Bichon, and S. P. Stovall. 2005. “Design of steel frames using ant colony optimization.” J. Struct. Eng. 131 (3): 369–379. https://doi.org/10.1061/(ASCE)0733-9445(2005)131:3(369).
Carravilla, M. A., C. Ribeiro, and J. F. Oliveira. 2003. “Solving nesting problems with non-convex polygons by constraint logic programming.” Int. Tran. Oper. Res. 10 (6): 651–663. https://doi.org/10.1111/1475-3995.00434.
Castaneda, E., B. Lauret, J. Lirola, and G. Ovando. 2015. “Free-form architectural envelopes: Digital processes opportunities of industrial production at a reasonable price.” J. Facade Des. Eng. 3 (1): 1–13.
Chan, C. M., L. Zhang, and J. T. Ng. 2009. “Optimization of pile groups using hybrid genetic algorithms.” J. Geotech. Geoenviron. Eng. 135 (4): 497–505. https://doi.org/10.1061/(ASCE)1090-0241(2009)135:4(497).
Cui, Y., Y. Cui, and L. Yang. 2014. “Heuristic for the two-dimensional arbitrary stock-size cutting stock problem.” Comput. Ind. Eng. 78 (Dec): 195–204. https://doi.org/10.1016/j.cie.2014.10.009.
Deng, M., V. J. L. Gan, Y. Tan, A. Joneja, and J. C. P. Cheng. 2019. “Automatic generation of fabrication drawings for façade mullions and transoms through BIM models.” Adv. Eng. Inf. 42 (Oct): 100964. https://doi.org/10.1016/j.aei.2019.100964.
Di Giuda, G. M., P. E. Giana, G. Masera, E. Seghezzi, and V. Villa. 2019. “A BIM-based approach to façade cladding optimization: Geometrical, economic, and production-control in a DfMA perspective.” In Proc., 2019 European Conf. on Computing in Construction, 324–331. Chania, Greece: European Council on Computing in Construction.
Dyckhoff, H. 1990. “A typology of cutting and packing problems.” Eur. J. Oper. Res. 44 (2): 145–159. https://doi.org/10.1016/0377-2217(90)90350-K.
Eastman, C., C. M. Eastman, P. Teicholz, and R. Sacks. 2011. BIM handbook: A guide to building information modeling for owners, managers, designers, engineers and contractors. Hoboken, NJ: Wiley.
Eigensatz, M., M. Kilian, A. Schiftner, N. J. Mitra, H. Pottmann, and M. Pauly. 2010. “Paneling architectural freeform surfaces.” In Proc., ACM SIGGRAPH 2010, 1–10. New York: Association for Computing Machinery.
Evtimov, G., and S. Fidanova. 2017. “Heuristic algorithm for 2D cutting stock problem.” In Proc., Int. Conf. on Large-Scale Scientific Computing, 350–357. New York: Springer.
Hartmanis, J. 1982. “Computers and intractability: A guide to the theory of np-completeness.” SIAM Rev. 24 (1): 90–91. https://doi.org/10.1137/1024022.
Kacprzyk, J., C. A. Coello Coello, and C. Dhaenens. 2010. Advances in multi-objective nature inspired computing. Berlin: Springer.
Kandil, A., K. El-Rayes, and O. El-Anwar. 2010. “Optimization research: Enhancing the robustness of large-scale multiobjective optimization in construction.” J. Constr. Eng. Manage. 136 (1): 17–25. https://doi.org/10.1061/(ASCE)CO.1943-7862.0000140.
Kaveh, A. 2017. Applications of metaheuristic optimization algorithms in civil engineering. Basel, Switzerland: Springer.
Khalili, A., and D. K. Chua. 2014. “Integrated prefabrication configuration and component grouping for resource optimization of precast production.” J. Constr. Eng. Manage. 140 (2): 4013052. https://doi.org/10.1061/(ASCE)CO.1943-7862.0000798.
Kierkosz, I., and M. Luczak. 2014. “A hybrid evolutionary algorithm for the two-dimensional packing problem.” Cent. Eur. J. Oper. Res. 22 (4): 729–753. https://doi.org/10.1007/s10100-013-0300-0.
Lee, A. D., P. Shepherd, M. C. Evernden, and D. Metcalfe. 2018. “Optimizing the architectural layouts and technical specifications of curtain walls to minimize use of aluminium.” In Structures, 8–25. Amsterdam, Netherlands: Elsevier.
Li, H., and P. Love. 1997. “Using improved genetic algorithms to facilitate time-cost optimization.” J. Constr. Eng. Manage. 123 (3): 233–237. https://doi.org/10.1061/(ASCE)0733-9364(1997)123:3(233).
Liao, T. W., P. Egbelu, B. Sarker, and S. Leu. 2011. “Metaheuristics for project and construction management—A state-of-the-art review.” Autom. Constr. 20 (5): 491–505. https://doi.org/10.1016/j.autcon.2010.12.006.
Manrique, J. D., M. Al-Hussein, A. Bouferguene, H. Safouhi, and R. Nasseri. 2011. “Combinatorial algorithm for optimizing wood waste in framing designs.” J. Constr. Eng. Manage. 137 (3): 188–197. https://doi.org/10.1061/(ASCE)CO.1943-7862.0000117.
Montali, J., M. Sauchelli, Q. Jin, and M. Overend. 2019. “Knowledge-rich optimisation of prefabricated façades to support conceptual design.” Autom. Constr. 97 (Jan): 192–204. https://doi.org/10.1016/j.autcon.2018.11.002.
Naqash, M. T. 2019. “Design and fabrication of aluminum cladding and curtain wall of a sports club.” Open J. Civ. Eng. 9 (1): 1. https://doi.org/10.4236/ojce.2019.91001.
Pantazis, E., and D. Gerber. 2018. “A framework for generating and evaluating façade designs using a multi-agent system approach.” Int. J. Archit. Comput. 16 (4): 248–270. https://doi.org/10.1177/1478077118805874.
Puchinger, J., and G. R. Raidl. 2005. “Combining metaheuristics and exact algorithms in combinatorial optimization: A survey and classification.” In Proc., Int. Work-Conf. on the Interplay between Natural and Artificial Computation, 41–53. New York: Springer.
Rausch, C., M. Nahangi, M. Perreault, C. T. Haas, and J. West. 2016. “Optimum assembly planning for modular construction components.” J. Comput. Civ. Eng. 31 (1): 04016039. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000605.
Rausch, C., B. Sanchez, M. E. Esfahani, and C. Haas. 2020. “Computational algorithms for digital twin support in construction.” In Proc., Construction Research Council 2020. Reston, VA: ASCE.
Ribeiro Filho, J. L., P. C. Treleaven, and C. Alippi. 1994. “Genetic-algorithm programming environments.” Computer 27 (6): 28–43. https://doi.org/10.1109/2.294850.
Rutten, D. 2013. Galapagos: On the logic and limitations of generic solvers, 132–135. New York: Wiley.
Said, H. M., T. Chalasani, and S. Logan. 2017. “Exterior prefabricated panelized walls platform optimization.” Autom. Constr. 76 (Apr): 1–13. https://doi.org/10.1016/j.autcon.2017.01.002.
Said, H. M., and K. Prathyaj. 2018. “Performance measurement of building sheet-metal ductwork prefabrication under batch production settings.” J. Constr. Eng. Manage. 144 (2): 04017107. https://doi.org/10.1061/(ASCE)CO.1943-7862.0001423.
Salem, O., A. Shahin, and Y. Khalifa. 2007. “Minimizing cutting wastes of reinforcement steel bars using genetic algorithms and integer programming models.” J. Constr. Eng. Manage. 133 (12): 982–992. https://doi.org/10.1061/(ASCE)0733-9364(2007)133:12(982).
Schrijver, A. 2005. “On the history of combinatorial optimization (till 1960).” In Vol. 12 of Handbooks in operations research and management science, 1–68. Amsterdam, Netherlands: Elsevier.
Shalaby, M. A., and M. Kashkoush. 2013. “A particle swarm optimization algorithm for a 2-D irregular strip packing problem.” Am. J. Oper. Res. 3 (2): 268–278. https://doi.org/10.4236/ajor.2013.32024.
Sherif, S. U., N. Jawahar, and M. Balamurali. 2014. “Sequential optimization approach for nesting and cutting sequence in laser cutting.” J. Manuf. Syst. 33 (4): 624–638. https://doi.org/10.1016/j.jmsy.2014.05.011.
Shewchuk, J. P., and C. Guo. 2011. “Panel stacking, panel sequencing, and stack locating in residential construction: Lean approach.” J. Constr. Eng. Manage. 138 (9): 1006–1016. https://doi.org/10.1061/(ASCE)CO.1943-7862.0000520.
Taborianski, V. M., and R. T. Prado. 2012. “Methodology of emission evaluation in the life cycle of office building façades.” Environ. Impact Assess. Rev. 33 (1): 41–47. https://doi.org/10.1016/j.eiar.2011.10.004.
Wang, P., Y. Mohamed, S. M. Abourizk, and A. T. Rawa. 2009. “Flow production of pipe spool fabrication: Simulation to support implementation of lean technique.” J. Constr. Eng. Manage. 135 (10): 1027–1038. https://doi.org/10.1061/(ASCE)CO.1943-7862.0000068.
Wäscher, G., H. Haußner, and H. Schumann. 2007. “An improved typology of cutting and packing problems.” Eur. J. Oper. Res. 183 (3): 1109–1130. https://doi.org/10.1016/j.ejor.2005.12.047.
Woeginger, G. J., M. Jünger, G. Reinelt, and G. Rinaldi. 2003. Exact algorithms for NP-hard problems. A survey: Lecture notes in computer science, 185–207. New York: Springer.
Wu, K., B. G. de Soto, and F. Zhang. 2020. “Spatio-temporal planning for tower cranes in construction projects with simulated annealing.” Autom. Constr. 111 (Mar): 103060. https://doi.org/10.1016/j.autcon.2019.103060.
Xu, Y. 2016. “An efficient heuristic approach for irregular cutting stock problem in ship building industry.” In Mathematical problems in engineering, 2016. London: Hindawi.
Yahya, M., and M. Saka. 2014. “Construction site layout planning using multi-objective artificial bee colony algorithm with Levy flights.” Autom. Constr. 38: 14–29. https://doi.org/10.1016/j.autcon.2013.11.001.
Zani, A., M. Andaloro, L. Deblasio, P. Ruttico, and A. G. Mainini. 2017. “Computational design and parametric optimization approach with genetic algorithms of an innovative concrete shading device system.” Procedia Eng. 180 (Jan): 1473–1483. https://doi.org/10.1016/j.proeng.2017.04.310.
Zhao, Y., C. Rausch, and C. T. Haas. 2021. “Optimizing 3D irregular object packing from 3D scans using metaheuristics.” Adv. Eng. Inf. 47: 101234. https://doi.org/10.1016/j.aei.2020.101234.
Zhou, J., P. E. Love, X. Wang, K. L. Teo, and Z. Irani. 2013. “A review of methods and algorithms for optimizing construction scheduling.” J. Oper. Res. Soc. 64 (8): 1091–1105. https://doi.org/10.1057/jors.2012.174.
Information & Authors
Information
Published In
Journal of Construction Engineering and Management
Volume 147 • Issue 7 • July 2021
Copyright
© 2021 American Society of Civil Engineers.
History
Received: Aug 28, 2020
Accepted: Feb 2, 2021
Published online: May 14, 2021
Published in print: Jul 1, 2021
Discussion open until: Oct 14, 2021
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.