Optimal packing of convex polytopes using quasi-phi-functions

• Main Authors: Pankratov, A. V., Romanova, T. E., Chugay, A. M.
• Format: Article
• Language: English
• Published: Journal of Mechanical Engineering 2015
• Subjects: packing; polytopes; continuous rotations; non-overlapping; allowable distances; quasi-phi-functions; mathematical model; non-linear optimization; УДК 519.859; упаковка; многогранники; непрерывные повороты; непересечение; допустимые расстояния; квази-phi-функции; математическая модель; нелинейная оптимизация; багатогранники; безперервні повороти; неперетинання; припустимі відстані; квазі-phi-функції; математична модель; нелінійна оптимізація
• Online Access: https://journals.uran.ua/jme/article/view/46687

We study a packing problem of a given collection of convex polytopes into a rectangular container of minimal volume. Continuous rotations and translations of polytopes are allowed. In addition a given minimal allowable distances between polytopes are taking into account. We employ radical free quasi-phi-functions and adjusted quasi-phi-functions to describe placement constraints. The use of quasi-phi-functions, instead of phi-functions, allows us to simplify non-overlapping, as well as, to describe distance constraints, but there is a price to pay: now the optimization has to be performed over a larger set of parameters, including the extra variables used by our new functions. We provide an exact mathematical model of the problem as a nonlinear programming problem. We also develop an efficient solution algorithm which involves a starting point algorithm, using homothetic trasformations of geometric objects and efficient local optimization procedure, which allows us to runtime and memory). We present here a number of examples to demonstrate the efficiency of our methodology.