Geodesic
A knapsack problem for rectangles under the~gravity center constraints
Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 3, pp. 102-115.

Voir la notice de l'article provenant de la source Math-Net.Ru

We have a set of rectangles with pre-defined widths, lengths, and masses and a knapsack with known width and length. Our goal is to select a subset of items and find their packing into the knapsack without overlapping to minimize the total empty space in the knapsack, while deviation of the total gravity center of such items from the geometric center of the knapsack does not exceed some threshold in both axes. We use the item permutations to represent the solutions and the skyline heuristic as a decoding procedure. The gravity center constraint is relaxed and included into the objective function with a penalty. To find the best permutation, we apply the simulated annealing algorithm with swap neighborhood and a special rule for returning into the feasible domain. Computational results for test instances with known optimal solutions are discussed. Tab. 2, illustr. 3, bibliogr. 14.
Keywords: 2D packing, skyline heuristic, gravity center constraint, local search. 
@article{DA_2022_29_3_a6,
     author = {S. M. Shperling and Yu. A. Kochetov},
     title = {A knapsack problem for rectangles under the~gravity center constraints},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {102--115},
     publisher = {mathdoc},
     volume = {29},
     number = {3},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2022_29_3_a6/}
}
TY  - JOUR
AU  - S. M. Shperling
AU  - Yu. A. Kochetov
TI  - A knapsack problem for rectangles under the~gravity center constraints
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2022
SP  - 102
EP  - 115
VL  - 29
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2022_29_3_a6/
LA  - ru
ID  - DA_2022_29_3_a6
ER  - 
%0 Journal Article
%A S. M. Shperling
%A Yu. A. Kochetov
%T A knapsack problem for rectangles under the~gravity center constraints
%J Diskretnyj analiz i issledovanie operacij
%D 2022
%P 102-115
%V 29
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2022_29_3_a6/
%G ru
%F DA_2022_29_3_a6
S. M. Shperling; Yu. A. Kochetov. A knapsack problem for rectangles under the~gravity center constraints. Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 3, pp. 102-115. http://geodesic.mathdoc.fr/item/DA_2022_29_3_a6/

[1] Gallo G., Hammer P. L., Simeone B., “Quadratic knapsack problems”, Math. Program. Stud., 12 (1980), 132–149 | DOI | MR | Zbl

[2] Martello S., Toth P., Knapsack problems: Algorithms and computer implementations, John Wiley Sons, Chichester, 1990, 296 pp. | MR | Zbl

[3] Davies A. P., Bischoff E. E., “Weight distribution considerations in container loading”, Eur. J. Oper. Res., 114:3 (1999), 509–527 | DOI | Zbl

[4] Ratcliff M. S. W., Bischoff E. E., “Allowing for weight considerations in container loading”, OR Spectrum, 20:1 (1998), 65–71 | DOI | MR | Zbl

[5] Baldi M. M., Perboli G., Tadei R., “The three-dimensional knapsack problem with balancing constraints”, Appl. Math. Comput., 218 (2021), 9802–9818 | MR

[6] Kaluzny B. L., Shaw R. H. A. D., “Optimal aircraft load balancing”, Int. Trans. Oper. Res., 16:6 (2009), 767–787 | DOI | Zbl

[7] Mongeau M., Bès C., “Optimization of aircraft container loading”, IEEE Trans. Aerosp. Electron. Syst., 39:1 (2003), 140–150 | DOI

[8] Trivella A., Pisinger D., “The load-balanced multi-dimensional bin-packing problem”, Comput. Oper. Res., 74 (2016), 152–164 | DOI | MR | Zbl

[9] Fernández A., Gil C., Baños R., Montoya M. G., “A parallel multi-objective algorithm for two-dimensional bin packing with rotations and load balancing”, Expert Syst. Appl., 40:13 (2013), 5169–5180 | DOI

[10] Liu D. S., Tan K. C., Huang S. Y., Goh C. K., Ho W. K., “On solving multiobjective bin packing problems using evolutionary particle swarm optimization”, Eur. J. Oper. Res., 190:2 (2008), 357–382 | DOI | MR | Zbl

[11] Kirkpatrick S., Gelatt C. D., Jr., Vecchi M. P., “Optimization by simulated annealing”, Science, 220:4598 (1983), 671–680 | DOI | MR | Zbl

[12] Dowsland K. A., “Some experiments with simulated annealing techniques for packing problems”, Eur. J. Oper. Res., 68:3 (1993), 389–399 | DOI | Zbl

[13] Vasilyev I., Ushakov A. V., Barkova M. V., Zhang D., Ren J., Chen J., “Fast heuristic algorithms for the multiple strip packing problems”, Mathematical Optimization Theory and Operations Research, Recent Trends. Rev. Sel. Pap. 20th Int. Conf. (Irkutsk, Russia, July 5–10 2021), Commun. Comput. Inf. Sci., 1476, Springer, Cham, 2021, 285–297 | MR

[14] Gurobi optimizer reference manual, Gurobi Optimization, Beaverton, 2021 (accessed May 16, 2022) www.gurobi.com/documentation/9.5/refman/index.html