Voxel-Based Solution Approaches to the Three-Dimensional Irregular Packing Problem

References

• Abeysooriya RP, Bennell JA, Martinez-Sykora A (2018) Jostle heuristics for the 2D-irregular shapes bin packing problems with free rotation. Internat. J. Production Econom. 195:12–26.Crossref, Google Scholar
• Art R (1966) An approach to the two dimensional irregular cutting stock problem. Unpublished thesis, Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
• Attene M (2015) Shapes in a box: Disassembling 3D objects for efficient packing and fabrication. Comput. Graphics Forum 34(8):64–76.Crossref, Google Scholar
• Baert J, Lagae A, Dutré P (2014) Out-of-core construction of sparse voxel octrees. Comput. Graphics Forum 33(6):220–227.Crossref, Google Scholar
• Baumers M, Tuck C, Wildman R, Ashcroft I, Rosamond E, Hague R (2013) Transparency built-in: Energy consumption and cost estimation for additive manufacturing. J. Indust. Ecology 17(3):418–431.Crossref, Google Scholar
• Bennell JA, Dowsland KA (1999) A tabu thresholding implementation for the irregular stock cutting problem. Internat. J. Production Res. 37(18):4259–4275.Crossref, Google Scholar
• Bennell JA, Dowsland KA (2001) Hybridising tabu search with optimisation techniques for irregular stock cutting. Management Sci. 47(8):1160–1172.Link, Google Scholar
• Bennell J, Oliveira J (2008) The geometry of nesting problems: A tutorial. Eur. J. Oper. Res. 184(2):397–415.Crossref, Google Scholar
• Bennell Ja, Oliveira JF (2009) A tutorial in irregular shape packing problems. J. Oper. Res. Soc. 60:S93–S105.Crossref, Google Scholar
• Bennell JA, Dowsland KA, Dowsland WB (2000) The irregular cutting-stock problem: A new procedure for deriving the no-fit polygon. Comput. Oper. Res. 28(3):271–287.Crossref, Google Scholar
• Bennell J, Scheithauer G, Stoyan Y, Romanova T (2010) Tools of mathematical modeling of arbitrary object packing problems. Ann. Oper. Res. 179(1):343–368.Crossref, Google Scholar
• Błazewicz J, Hawryluk P, Walkowiak R (1993) Using a tabu search approach for solving the two-dimensional irregular cutting problem. Ann. Oper. Res. 41(4):313–325.Crossref, Google Scholar
• Burke E, Hyde M, Kendall G, Woodward J (2010) A genetic programming hyper-heuristic approach for evolving 2-D strip packing heuristics. IEEE Trans. Evolutionary Comput. 14(6):942–958.Crossref, Google Scholar
• Byholm T, Toivakka M, Westerholm J (2009) Effective packing of 3-dimensional voxel-based arbitrarily shaped particles. Powder Tech. 196(2):139–146.Crossref, Google Scholar
• Cagan J, Degentesh D, Yin S (1998) A simulated annealing-based algorithm using hierarchical models for general three-dimensional component layout. Comput.-Aided Design 30(10):781–790.Crossref, Google Scholar
• de Korte A, Brouwers H (2013) Random packing of digitized particles. Powder Tech. 233:319–324.Crossref, Google Scholar
• Dickinson JJK, Knopf GKG (1998) Serial packing of arbitrary 3D objects for optimizing layered manufacturing. Proc. SPIE 3522:130–138.Crossref, Google Scholar
• Dowsland KA, Dowsland WB, Bennell JA (1998) Jostling for position: Local improvement for irregular cutting patterns. J. Oper. Res. Soc. 49(6):647–658.Crossref, Google Scholar
• Edelkamp S, Wichern P (2015) Packing irregular-shaped objects for 3D printing. Hölldobler S, Krötzsch M, Peñaloza R, Rudolph S, eds. KI 2015: Adv. Artificial Intelligence: 38th Annual German Conf. AI, Lecture Notes in Computer Science, vol. 9324 (Springer International Publishing, Cham, Switzerland), 45–58.Google Scholar
• Edwards T (2014) Classic chess set from glChess. Accessed December 1, 2019, https://www.thingiverse.com/thing:322616.Google Scholar
• Egeblad J, Nielsen BK, Brazil M (2009) Translational packing of arbitrary polytopes. Comput. Geometry 42(4):269–288.Crossref, Google Scholar
• Egeblad J, Nielsen BK, Odgaard A (2007) Fast neighborhood search for two- and three-dimensional nesting problems. Eur. J. Oper. Res. 183(3):1249–1266.Crossref, Google Scholar
• Egeblad J, Garavelli C, Lisi S, Pisinger D (2010) Heuristics for container loading of furniture. Eur. J. Oper. Res. 200(3):881–892.Crossref, Google Scholar
• Glover F (1989) Tabu search-part I. ORSA J. Comput. 1(3):190–206.Link, Google Scholar
• Glover F, Laguna M (2013) Tabu Search* In: Pardalos P, Du DZ, Graham R, eds. Handbook of Combinatorial Optimization (Springer, New York, NY), 3261?3362.Google Scholar
• Gomes A, Oliveira JF (2002) A 2-exchange heuristic for nesting problems. Eur. J. Oper. Res. 141(2):359–370.Crossref, Google Scholar
• Gomes AM, Oliveira JF (2006) Solving irregular strip packing problems by hybridising simulated annealing and linear programming. Eur. J. Oper. Res. 171(3):811–829.Crossref, Google Scholar
• Griffiths V, Scanlan JP, Eres MH, Martinez-Sykora A, Chinchapatnam P (2019) Cost-driven build orientation and bin packing of parts in selective laser melting (SLM). Eur. J. Oper. Res. 273(1):334–352.Crossref, Google Scholar
• Harrell E (2015) Toyota 4 cylinder engine 22RE, complete working model. Accessed December 1, 2019, http://www.thingiverse.com/thing:644933.Google Scholar
• Hur SM, Choi KH, Lee SH, Chang PK (2001) Determination of fabricating orientation and packing in SLS process. J. Materials Processing Tech. 112(2-3):236–243.Crossref, Google Scholar
• Ikonen I, Biles W, Kumar A, Wissel J, Ragade R (1997) A genetic algorithm for packing three-dimensional non-convex objects having cavities and holes. Proc. 7th Internat. Conf. Genetic Algorithms (Morgan Kaufmann Publishers, East Lansing, Michigan), 591–598.Google Scholar
• Imamichi T, Yagiura M, Nagamochi H (2009) An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem. Discrete Optim. 6(4):345–361.Crossref, Google Scholar
• Jia X, Williams R (2001) A packing algorithm for particles of arbitrary shapes. Powder Tech. 120(3):175–186.Crossref, Google Scholar
• Lemus E, Bribiesca E, Garduño E (2015) Surface trees–Representation of boundary surfaces using a tree descriptor. J. Visual Comm. Image Representation 31(C):101–111.Crossref, Google Scholar
• Liu X, Liu JM, Cao AX, Yao ZL (2015) HAPE3D–A new constructive algorithm for the 3D irregular packing problem. Frontiers Inform. Tech. Electronic Engrg. 16(5):380–390.Crossref, Google Scholar
• López-Ibáñez M, Dubois-Lacoste J, Pérez Cáceres L, Birattari M, Stützle T (2016) The irace package: Iterated racing for automatic algorithm configuration. Oper. Res. Perspect. 3:43–58.Crossref, Google Scholar
• Lourenço HR, Martin OC, Stützle T (2010) Iterated Local Search: Framework and Applications (Springer, Boston), 363–397.Crossref, Google Scholar
• Ma Y, Chen Z, Hu W, Wang W (2018) Packing irregular objects in 3D space via hybrid optimization. Comput. Graphics Forum 37(5):49–59.Crossref, Google Scholar
• Mangiaracina R, Marchet G, Perotti S, Tumino A (2015) A review of the environmental implications of B2C e-commerce: A logistics perspective. Internat. J. Physical Distribution Logist. Management 45(6):565–591.Crossref, Google Scholar
• Mazareanu E (2020) Parcel traffic worldwide by sector 2015-2019. https://www.statista.com/statistics/737418/parcel-traffic-worldwide-by-sector/.Google Scholar
• Milenkovic V, Daniels K, Li Z (1992) Placement and compaction of nonconvex polygons for clothing manufacture. Proc. Fourth Canadian Conf. Comput. Geometry (Memorial University of Newfoundland, St. John’s NL, Canada), 236–243.Google Scholar
• Min P (2019) Binvox. http://www.patrickmin.com/binvox or https://www.google.com/search?q=binvox.Google Scholar
• Mladenović N, Hansen P (1997) Variable neighborhood search. Comput. Oper. Res. 24(11):1097–1100.Crossref, Google Scholar
• Mundim LR, Andretta M, Carravilla MA, Oliveira JF (2018) A general heuristic for two-dimensional nesting problems with limited-size containers. Internat. J. Production Res. 56(1-2):709–732.Crossref, Google Scholar
• Nooruddin FS, Turk G (2003) Simplification and repair of polygonal models using volumetric techniques. IEEE Trans. Visualization Comput. Graphics 9(2):191–205.Crossref, Google Scholar
• Oliveira JF, Gomes AM, Ferreira JS (2000) TOPOS–A new constructive algorithm for nesting problems. OR Spectrum 22(2):263.Crossref, Google Scholar
• Pankratov AV, Romanova TE, Chugay AM, Problems E, Acad N (2015) Optimal packing of convex polytopes using quasi-phi-functions. Jixie Gongcheng Xuebao 18(2):55–64.Google Scholar
• Robidoux N, Stelldinger P, Cupitt J (2011) Simple random generation of smooth connected irregular shapes for cognitive studies. Proc. Fourth Internat. C* Conf. Comput. Sci. Software Engrg. (ACM Press, New York), 17–24.Google Scholar
• Romanova T, Bennell J, Stoyan Y, Pankratov A (2018) Packing of concave polyhedra with continuous rotations using nonlinear optimisation. Eur. J. Oper. Res. 268(1):37–53.Crossref, Google Scholar
• Sánchez-Cruz H, López-Valdez HH, Cuevas FJ (2014) A new relative chain code in 3D. Pattern Recognition 47(2):769–788.Crossref, Google Scholar
• Scheithauer G, Stoyan YG, Romanova TY (2005) Mathematical modeling of interactions of primary geometric 3D objects. Cybernetics Systems Anal. 41(3):332–342.Crossref, Google Scholar
• Schwarz M, Seidel HP (2010) Fast parallel surface and solid voxelization on GPUs. ACM Trans. Graphics 29(6):1–10.Crossref, Google Scholar
• Stoyan YG (1983) Mathematical methods for geometric design. Advances in CAD/CAM, Proc. PROLAMAT82, Leningrad, USSR, May 1982 (North-Holland, Amsterdam), 67–86.Google Scholar
• Stoyan YG, Gil N, Pankratov A, Scheithauer G (2004) Packing non-convex polytopes into a parallelepiped. Preprint MATH-NM-06-2004: Technische Universität of Dresden.Google Scholar
• Stoyan YG, Gil NI, Scheithauer G, Pankratov A, Magdalina I (2005) Packing of convex polytopes into a parallelepiped. Optim. 54(2):215–235.Crossref, Google Scholar
• Terashima-Marín H, Ross P, Farías-Zárate CJ, López-Camacho E, Valenzuela-Rendón M (2010) Generalized hyper-heuristics for solving 2D regular and irregular packing problems. Ann. Oper. Res. 179(1):369–392.Crossref, Google Scholar
• Thompson MK, Moroni G, Vaneker T, Fadel G, Campbell RI, Gibson I, Bernard A, et al. (2016) Design for additive manufacturing: Trends, opportunities, considerations, and constraints. CIRP Ann. Manufacturing Tech. 65(2):737–760.Crossref, Google Scholar
• Toledo FM, Carravilla MA, Ribeiro C, Oliveira JF, Gomes AM (2013) The dotted-board model: A new MIP model for nesting irregular shapes. Internat. J. Production Econom. 145(2):478–487.Crossref, Google Scholar
• Umetani S, Yagiura M, Imahori S, Imamichi T, Nonobe K, Ibaraki T (2009) Solving the irregular strip packing problem via guided local search for overlap minimization. Internat. Trans. Oper. Res. 16(6):661–683.Crossref, Google Scholar
• Wäscher G, Haußner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur. J. Oper. Res. 183:1109–1130.Crossref, Google Scholar