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

S. M. Shperling, Yu A. Kochetov

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

Аннотация

We have a set of rectangles with predefined widths, lengths, and masses and a knapsack ofknown width and length. Our goal is to select a subset of items and find their packing into theknapsack without overlapping so as to minimize the total empty space in the knapsack. Thedeviation of the center of gravity of the items from the knapsack geometric center must not exceedsome threshold along both axes. We use item permutations to represent solutions and the skylineheuristic as a decoding procedure. The center-of-gravity constraint is relaxed and included intothe objective function with penalty. To find the best permutation, we apply the simulatedannealing algorithm with swap neighborhood and a special rule for returning into the feasibledomain. Computational results for test instances with known optimal solutions are discussed.

Язык оригиналаанглийский
Страницы (с-по)563-571
Число страниц9
ЖурналJournal of Applied and Industrial Mathematics
Том16
Номер выпуска3
DOI
СостояниеОпубликовано - мая 2022

Предметные области OECD FOS+WOS

  • 1.01 МАТЕМАТИКА
  • 2.03 МЕХАНИКА И МАШИНОСТРОЕНИЕ

Цитировать