Efficient use of collision detection for volume maximization problems

Jonas Tollenaere, Hatice Çalık and Tony Wauters

European Journal of Operational Research, 2024, vol. 319, issue 3, 967-982

Abstract: This paper proposes improved local search heuristics based on collision detection for solving volume maximization problems, with a particular focus on single item volume maximization. The objective is to find the biggest item of a predefined shape that can be extracted from a larger container. Both the item and the container are three-dimensional objects and can have irregular shapes. Our goal is to find high-quality solutions for these problems within a reasonable amount of time, even for complex instances where the object and container are represented by thousands of triangles. We consider an approach where the position and orientation of an item are optimized heuristically, while the scale of the item is maximized using a fast inflation procedure. This inflation procedure uses bisection search and collision detection to determine the largest possible scale that satisfies all geometric constraints for a given position and orientation of the item within the container. We introduce improvements to this approach to reduce the required amount of geometric computations required. Finally, we compare our results against a matheuristic method from the literature on an expanded data set, which shows the improved collision detection approach is more than 100 times faster and highlights the impact of our improvements.

Keywords: Cutting; Maximum volume extraction; 3D irregular cutting and packing; Collision detection (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724004272
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:319:y:2024:i:3:p:967-982

DOI: 10.1016/j.ejor.2024.05.048

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().