Том 29, номер 3, 2022 г., Стр. 102-115

УДК 519.8+518.25
Шперлинг С. М., Кочетов Ю. А.
Задача о рюкзаке для прямоугольных предметов с ограничением на расположение центра тяжести

Аннотация:
Имеется множество предметов прямоугольной формы с заданными шириной, длиной и массой и большой прямоугольник (рюкзак) с известными шириной и длиной. Требуется выбрать такое подмножество предметов и найти их расположение в рюкзаке без взаимных пересечений, чтобы минимизировать свободное место в рюкзаке. Центр тяжести упакованных предметов не должен уклоняться от геометрического центра рюкзака по обеим координатам больше заданного порога. Мы представляем решение задачи в виде перестановки предметов и используем известный skyline алгоритм в роли декодирующей процедуры. Ограничение на расположение центра тяжести включается в целевую функцию в виде штрафа. Чтобы найти наилучшую перестановку, используется алгоритм имитации отжига. Для генерации соседних решений два предмета меняются местами в перестановке, а при нарушении ограничений используется специальное правило для сдвига центра тяжести в нужную сторону. Обсуждаются результаты численных экспериментов для примеров с известными оптимальными решениями.
Табл. 2, ил. 3, библиогр. 14.

Ключевые слова: двумерная упаковка, алгоритм skyline, ограничение на расположение центра тяжести, локальный поиск.

DOI: 10.33048/daio.2022.29.741

Шперлинг Софья Михайловна ¹
Кочетов Юрий Андреевич ²
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
2. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: s.shperling@g.nsu.ru, jkochet@math.nsc.ru

Статья поступила 16 мая 2022 г.
После доработки — 23 мая 2022 г.
Принята к публикации 24 мая 2022 г.

Литература

[1] Gallo G., Hammer P. L., Simeone B. Quadratic knapsack problems // Math. Program. Stud. 1980. V. 12. P. 132–149.

[2] Martello S., Toth P. Knapsack problems: Algorithms and computer implementations. Chichester: John Wiley & Sons, 1990. 296 p.

[3] Davies A. P., Bischoff E. E. Weight distribution considerations in container loading // Eur. J. Oper. Res. 1999. V. 114, No. 3. P. 509–527.

[4] Ratcliff M. S. W., Bischoff E. E. Allowing for weight considerations in container loading // OR Spectrum. 1998. V. 20, No. 1. P. 65–71.

[5] Baldi M. M., Perboli G., Tadei R. The three-dimensional knapsack problem with balancing constraints // Appl. Math. Comput. 2021. V. 218. P. 9802–9818.

[6] Kaluzny B. L., Shaw R. H. A. D. Optimal aircraft load balancing // Int. Trans. Oper. Res. 2009. V. 16, No. 6. P. 767–787.

[7] Mongeau M., Bès C. Optimization of aircraft container loading // IEEE Trans. Aerosp. Electron. Syst. 2003. V. 39, No. 1. P. 140–150.

[8] Trivella A., Pisinger D. The load-balanced multi-dimensional bin-packing problem // Comput. Oper. Res. 2016. V. 74. P. 152–164.

[9] Fernández A., Gil C., Baños R., Montoya M. G. A parallel multiobjective algorithm for two-dimensional bin packing with rotations and load balancing // Expert Syst. Appl. 2013. V. 40, No. 13. P. 5169–5180.

[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. 2008. V. 190, No. 2. P. 357–382.

[11] Kirkpatrick S., Gelatt C. D., Jr., Vecchi M. P. Optimization by simulated annealing // Science. 1983. V. 220, No. 4598. P. 671–680.

[12] Dowsland K. A. Some experiments with simulated annealing techniques for packing problems // Eur. J. Oper. Res. 1993. V. 68, No. 3. P. 389–399.

[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). Cham: Springer, 2021. P. 285–297. (Commun. Comput. Inf. Sci.; V. 1476).

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