Задача о рюкзаке для прямоугольных предметов с ограничением на расположение центра тяжести

Задача о рюкзаке для прямоугольных предметов с ограничением на расположение центра тяжести

Шперлинг С. М., Кочетов Ю. А.
Дискретный анализ и исследование операций, 29, 3, 102-115 (2022)
Скачать статью

УДК 519.8+518.25 
DOI: 10.33048/daio.2022.29.741

Аннотация:

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

Литература:
  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).

Исследование выполнено в рамках государственного задания ИМ СО РАН (проект FWNF–2022–0019).

Шперлинг Софья Михайловна
  1. Новосибирский гос. университет,
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: s.shperling@g.nsu.ru

Кочетов Юрий Андреевич
  1. Институт математики им. С. Л. Соболева, 
    пр. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: jkochet@math.nsc.ru

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

Abstract:

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.

References:
  1. G. Gallo, P. L. Hammer, and B. Simeone, Quadratic knapsack problems, Math. Program. Stud. 12, 132–149 (1980).
     
  2. S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer Implementations (John Wiley & Sons, Chichester, 1990).
     
  3. A. P. Davies and E. E. Bischoff, Weight distribution considerations in container loading, Eur. J. Oper. Res. 114 (3), 509–527 (1999).
     
  4. M. S. W. Ratcliff and E. E. Bischoff, Allowing for weight considerations in container loading, OR Spectrum 20 (1), 65–71 (1998).
     
  5. M. M. Baldi, G. Perboli, and R. Tadei, The three-dimensional knapsack problem with balancing constraints, Appl. Math. Comput. 218, 9802–9818 (2021).
     
  6. B. L. Kaluzny and R. H. A. D. Shaw, Optimal aircraft load balancing, Int. Trans. Oper. Res. 16 (6), 767–787 (2009). 
     
  7. M. Mongeau and C. Bés, Optimization of aircraft container loading, IEEE Trans. Aerosp. Electron. Syst. 39 (1), 140–150 (2003).
     
  8. A. Trivella and D. Pisinger, The load-balanced multi-dimensional binpacking problem, Comput. Oper. Res. 74, 152–164 (2016).
     
  9. A. Fernández, C. Gil, R. Baños and M. G. Montoya, A parallel multiobjective algorithm for two-dimensional bin packing with rotations and load balancing, Expert Syst. Appl. 40 (13), 5169–5180 (2013).
     
  10. D. S. Liu, K. C. Tan, S. Y. Huang, C. K. Goh, and W. K. Ho, On solving multiobjective bin packing problems using evolutionary particle swarm optimization, Eur. J. Oper. Res. 190 (2), 357–382 (2008).
     
  11. S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi, Optimization by simulated annealing, Science 220 (4598), 671–680 (1983).
     
  12. K. A. Dowsland, Some experiments with simulated annealing techniques for packing problems, Eur. J. Oper. Res. 68 (3), 389–399 (1993).
     
  13. I. Vasilyev, A. V. Ushakov, M. V. Barkova, D. Zhang, J. Ren, and J. Chen, Fast heuristic algorithms for the multiple strip packing problems, in Mathematical Optimization Theory and Operations Research: Recent Trends (Rev. Sel. Pap. 20th Int. Conf., Irkutsk, Russia, July 5–10, 2021) (Springer, Cham, 2021), pp. 285–297 (Commun. Comput. Inf. Sci., Vol. 1476).
     
  14. Gurobi Optimizer Reference Manual (Gurobi Optimization, Beaverton, 2021). Available at www.gurobi.com/documentation/9.5/refman/index.html (accessed May 16, 2022).