{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T07:07:41Z","timestamp":1769324861225,"version":"3.49.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2023,7,24]],"date-time":"2023-07-24T00:00:00Z","timestamp":1690156800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,24]],"date-time":"2023-07-24T00:00:00Z","timestamp":1690156800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100009534","name":"Universit\u00e4t Stuttgart","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100009534","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Intell Manuf"],"published-print":{"date-parts":[[2024,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Reducing material waste and computation time are primary objectives in cutting and packing problems (C &amp;P). A solution to the C &amp;P problem consists of many steps, including the grouping of items to be nested and the arrangement of the grouped items on a large object. Current algorithms use meta-heuristics to solve the arrangement problem directly without explicitly addressing the grouping problem. In this paper, we propose a new pipeline for the nesting problem that starts with grouping the items to be nested and then arranging them on large objects. To this end, we introduce and motivate a new concept, namely the Geometrical Compatibility Index (GCI). Items with higher GCI should be clustered together. Since no labels exist for GCIs, we propose to model GCIs as bidirectional weighted edges of a graph that we call geometrical relationship graph (GRG). We propose a novel reinforcement-learning-based framework, which consists of two graph neural networks trained in an actor-critic-like fashion to learn GCIs. Then, to group the items into clusters, we model the GRG as a capacitated vehicle routing problem graph and solve it using meta-heuristics. Experiments conducted on a private dataset with regularly and irregularly shaped items show that the proposed algorithm can achieve a significant reduction in computation time (30% to 48%) compared to an open-source nesting software while attaining similar trim loss on regular items and a threefold improvement in trim loss on irregular items.<\/jats:p>","DOI":"10.1007\/s10845-023-02179-0","type":"journal-article","created":{"date-parts":[[2023,7,24]],"date-time":"2023-07-24T03:10:47Z","timestamp":1690168247000},"page":"2811-2827","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Smart nesting: estimating geometrical compatibility in the nesting problem using graph neural networks"],"prefix":"10.1007","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5726-0124","authenticated-orcid":false,"given":"Kirolos","family":"Abdou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Osama","family":"Mohammed","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George","family":"Eskandar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amgad","family":"Ibrahim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul-Amaury","family":"Matt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco F.","family":"Huber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,24]]},"reference":[{"key":"2179_CR1","first-page":"107","volume":"19","author":"M Arenales","year":"1999","unstructured":"Arenales, M., Morabito, R., & Yanasse, H. (1999). Special issue: Cutting and packing problems. Pesquisa Operacional, 19, 107\u2013299.","journal-title":"Pesquisa Operacional"},{"key":"2179_CR2","doi-asserted-by":"publisher","first-page":"834","DOI":"10.1109\/TSMC.1983.6313077","volume":"5","author":"AG Barto","year":"1983","unstructured":"Barto, A. G., Sutton, R. S., & Anderson, C. W. (1983). Neuronlike adaptive elements that can solve difficult learning control problems. IEEE Transactions on Systems, Man, and Cybernetics, 5, 834\u2013846.","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics"},{"key":"2179_CR3","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1016\/S0010-4485(01)00109-9","volume":"34","author":"J Cagan","year":"2002","unstructured":"Cagan, J., Shimada, K., & Yin, S. (2002). A survey of computational approaches to three-dimensional layout problems. Computer-Aided Design, 34, 597\u2013611.","journal-title":"Computer-Aided Design"},{"key":"2179_CR4","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0377-2217(90)90350-K","volume":"44","author":"H Dyckhoff","year":"1990","unstructured":"Dyckhoff, H. (1990). A typology of cutting and packing problems. European Journal of Operational Research, 44, 145\u2013159.","journal-title":"European Journal of Operational Research"},{"key":"2179_CR5","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1007\/s40574-020-00253-6","volume":"13","author":"L Faina","year":"2020","unstructured":"Faina, L. (2020). A survey on the cutting and packing problems. Bollettino dell\u2019Unione Matematica Italiana, 13, 567\u2013572.","journal-title":"Bollettino dell\u2019Unione Matematica Italiana"},{"key":"2179_CR6","doi-asserted-by":"publisher","first-page":"1953","DOI":"10.1016\/j.cor.2013.02.026","volume":"40","author":"F Furini","year":"2013","unstructured":"Furini, F., & Malaguti, E. (2013). Models for the two-dimensional two-stage cutting stock problem with multiple stock size. Computers & Operations Research, 40, 1953\u20131962.","journal-title":"Computers & Operations Research"},{"key":"2179_CR7","doi-asserted-by":"publisher","first-page":"1291","DOI":"10.1109\/TSMCC.2012.2218595","volume":"42","author":"I Grondman","year":"2012","unstructured":"Grondman, I., Busoniu, L., Lopes, G. A. D., & Babuska, R. (2012). A survey of actor-critic reinforcement learning: Standard and natural policy gradients. IEEE Transactions on Systems, Man, and Cybernetics, 42, 1291\u20131307.","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics"},{"key":"2179_CR8","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.jmsy.2020.04.019","volume":"56","author":"B Guo","year":"2020","unstructured":"Guo, B., Hu, J., Wu, F., & Peng, Q. (2020). Automatic layout of 2D free-form shapes based on geometric similarity feature searching and fuzzy matching. Journal of Manufacturing Systems, 56, 37\u201349.","journal-title":"Journal of Manufacturing Systems"},{"key":"2179_CR9","doi-asserted-by":"crossref","unstructured":"Kim, J., Kim, T., Kim, S., & Yoo, C.\u00a0D. (2019). Edge-labeling graph neural network for few-shot learning. In: Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR), (pp. 11\u201320).","DOI":"10.1109\/CVPR.2019.00010"},{"key":"2179_CR10","unstructured":"Kipf, T.\u00a0N., & Welling, M. (2017). Semi-supervised classification with graph convolutional networks. In: Proceedings of the international conference on learning representations (ICLR)."},{"key":"2179_CR11","doi-asserted-by":"publisher","first-page":"66","DOI":"10.4236\/iim.2012.43010","volume":"4","author":"SN Kumar","year":"2012","unstructured":"Kumar, S. N., & Panneerselvam, R. (2012). A survey on the vehicle routing problem and its variants. Intelligent Information Management, 4, 66\u201374.","journal-title":"Intelligent Information Management"},{"key":"2179_CR12","doi-asserted-by":"crossref","unstructured":"Kundu, O., Dutta, S., & Kumar, S. (2019). Deep-pack: A vision-based 2D online bin packing algorithm with deep reinforcement learning. In: Proceedings of the IEEE international conference on robot and human interactive communication (RO-MAN), pp. 1\u20137.","DOI":"10.1109\/RO-MAN46459.2019.8956393"},{"key":"2179_CR13","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/s00521-006-0064-8","volume":"16","author":"R Labib","year":"2007","unstructured":"Labib, R., & Assadi, R. (2007). Modified multi-layered perceptron applied to packing and covering problems. Neural Computing and Applications, 16, 173\u2013186.","journal-title":"Neural Computing and Applications"},{"key":"2179_CR14","doi-asserted-by":"crossref","unstructured":"Liu, J., Ong, G. P., & Chen, X. (2022). Graphsage-based traffic speed forecasting for segment network with sparse data. IEEE Transactions on Intelligent Transportation Systems, 23, 1755\u20131766.","DOI":"10.1109\/TITS.2020.3026025"},{"key":"2179_CR15","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1080\/03052150214016","volume":"34","author":"J Michalek","year":"2002","unstructured":"Michalek, J., Choudhary, R., & Papalambros, P. (2002). Architectural layout design optimization. Engineering Optimization, 34, 461\u2013484.","journal-title":"Engineering Optimization"},{"key":"2179_CR16","unstructured":"Nazari, M., Oroojlooy, A., Snyder, L., & Takac M. (2018). Reinforcement learning for solving the vehicle routing problem. Advances in Neural Information Processing Systems"},{"key":"2179_CR17","doi-asserted-by":"crossref","unstructured":"Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). Deepwalk: Online learning of social representations. In: Proceedings of the ACM SIGKDD international conference on knowledge discovery and data mining (KDD), (pp. 701\u2013710).","DOI":"10.1145\/2623330.2623732"},{"key":"2179_CR18","unstructured":"Perron, L., & Furnon, V. Or-tools. Google. https:\/\/developers.google.com\/optimization\/"},{"key":"2179_CR19","doi-asserted-by":"publisher","first-page":"106268","DOI":"10.1016\/j.asoc.2020.106268","volume":"92","author":"RG Rakotonirainy","year":"2020","unstructured":"Rakotonirainy, R. G., & van Vuuren, J. H. (2020). Improved metaheuristics for the two-dimensional strip packing problem. Applied Soft Computing, 92, 106268.","journal-title":"Applied Soft Computing"},{"key":"2179_CR20","doi-asserted-by":"crossref","unstructured":"Szegedy, C., Liu, W., Jia, Y., Sermanet, P., Reed, S., Anguelov, D., Erhan, D., Vanhoucke, V., & Rabinovich, A. (2015). Going deeper with convolutions. In: Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR), (pp. 1\u20139)","DOI":"10.1109\/CVPR.2015.7298594"},{"key":"2179_CR21","doi-asserted-by":"publisher","first-page":"1109","DOI":"10.1016\/j.ejor.2005.12.047","volume":"183","author":"G W\u00e4scher","year":"2007","unstructured":"W\u00e4scher, G., Hau\u00dfner, H., & Schumann, H. (2007). An improved typology of cutting and packing problems. European Journal of Operational Research, 183, 1109\u20131130.","journal-title":"European Journal of Operational Research"},{"key":"2179_CR22","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1109\/TSMC.1973.4309272","volume":"5","author":"B Widrow","year":"1973","unstructured":"Widrow, B., Gupta, N. K., & Maitra, S. (1973). Punish\/reward: Learning with a critic in adaptive threshold systems. IEEE Transactions on Systems, Man, and Cybernetics, 5, 455\u2013465.","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics"},{"key":"2179_CR23","first-page":"1","volume":"34","author":"Y Yang","year":"2022","unstructured":"Yang, Y., Liu, B., Li, H., Li, X., Wang, G., & Li, S. (2022). A nesting optimization method based on digital contour similarity matching for additive manufacturing. Journal of Intelligent Manufacturing, 34, 1\u201323.","journal-title":"Journal of Intelligent Manufacturing"},{"key":"2179_CR24","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.ipl.2015.08.008","volume":"116","author":"D Zhang","year":"2016","unstructured":"Zhang, D., Shi, L., Leung, S. C. H., & Wu, T. (2016). A priority heuristic for the guillotine rectangular packing problem. Information Processing Letters, 116, 15\u201321.","journal-title":"Information Processing Letters"}],"container-title":["Journal of Intelligent Manufacturing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10845-023-02179-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10845-023-02179-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10845-023-02179-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,6]],"date-time":"2024-07-06T20:22:07Z","timestamp":1720297327000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10845-023-02179-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,24]]},"references-count":24,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["2179"],"URL":"https:\/\/doi.org\/10.1007\/s10845-023-02179-0","relation":{},"ISSN":["0956-5515","1572-8145"],"issn-type":[{"value":"0956-5515","type":"print"},{"value":"1572-8145","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,24]]},"assertion":[{"value":"14 November 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 July 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 July 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}