A Knapsack Problem for Rectangles under Center-of-Gravity Constraints.

Autor: Shperling, S. M., Kochetov, Yu. A.
Zdroj: Journal of Applied & Industrial Mathematics; May2022, Vol. 16 Issue 3, p563-571, 9p
Abstrakt: We have a set of rectangles with predefined widths, lengths, and masses and a knapsack of known width and length. Our goal is to select a subset of items and find their packing into the knapsack without overlapping so as to minimize the total empty space in the knapsack. The deviation of the center of gravity of the items from the knapsack geometric center must not exceed some threshold along both axes. We use item permutations to represent solutions and the skyline heuristic as a decoding procedure. The center-of-gravity constraint is relaxed and included into the objective function with 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. [ABSTRACT FROM AUTHOR]
Databáze: Complementary Index
Externí odkaz: