Об одной задаче оптимизации размещения товаров на складе

Об одной задаче оптимизации размещения товаров на складе

Моторин К. О., Пяткин А. В.
Дискретный анализ и исследование операций, 32, 1, 75-98 (2025)
Скачать статью

УДК 519.8 
DOI: 10.33048/daio.2025.32.806

Аннотация:

Рассматривается задача поиска расположения товаров на складе, при котором минимизируется суммарное время составления заказов из заданного списка. Доказано, что задача NP-трудна даже в простейшем частном случае. Построена математическая модель ЦЛП для этой задачи. Предложено два эвристических алгоритма её решения, работа которых проанализирована на случайно сгенерированных примерах.

Табл. 3, ил. 9, библиогр. 17.

Литература:
  1. Karasek J. An overview of warehouse optimization // J. Adv. Telecommun. Electrotech. Signals Syst. 2013. V. 2, No. 3. P. 111–117.
     
  2. Caron F., Marchet G., Perego A. Optimal layout in low-level picker-topart systems // Int. J. Prod. Res. 2000. V. 38, No. 1. P. 101–117.
     
  3. Gu J., Goetschalckx M., McGinnis L. F. Research on warehouse design and performance evaluation: A comprehensive review // Eur. J. Oper. Res. 2010. V. 203, No. 3. P. 539–549.
     
  4. De Koster R., Le-Duc T., Roodbergen K. J. Design and control of warehouse order picking: A literature review // Eur. J. Oper. Res. 2007. V. 182, No. 2. P. 481–501.
     
  5. Ратушный А. А., Кочетов Ю. А. Матэвристика для минимизации времени ожидания трейлеров при неточных временах прибытия // Дискрет. анализ и исслед. операций. 2022. Т. 29, № 3. С. 85–101.
     
  6. Ratliff H. D., Rosenthal A. S. Order-picking in a rectangular warehouse: A solvable case of the traveling salesman problem // Oper. Res. 1983. V. 31, No. 3. P. 507–521.
     
  7. Roodbergen K. J., de Koster R. Routing order pickers in a warehouse with a middle aisle // Eur. J. Oper. Res. 2001. V. 133, No. 1. P. 32–43.
     
  8. Brynzer H., Johansson M. I. Storage location assignment: Using the product structure to reduce order picking times // Int. J. Prod. Econ. 1996. V. 46, No. 1. P. 595–603.
     
  9. Mantel R. J., Schuur P. C., Heragu S. S. Order oriented slotting: A new assignment strategy for warehouses // Eur. J. Ind. Eng. 2007. V. 1, No. 3. P. 301–316.
     
  10. Koopmans T. C., Beckmann M. Assignment problems and the location of economic activities // Econometrica. 1957. V. 25, No. 1. P. 53–76.
     
  11. Bui T. N., Chaudhuri S., Leighton F. T., Sipser M. Graph bisection algorithms with good average case behavior // Combinatorica. 1987. V. 7, No. 2. P. 171–191.
     
  12. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. M.: Мир, 1982. 416 с.
     
  13. Misevicius A., Kilda B. Comparison of crossover operators for the quadratic assignment problem // Inf. Technol. Control. 2005. V. 34, No. 2. P. 109–119.
     
  14. Misevicius A. An implementation of the iterated tabu search algorithm for the quadratic assignment problem // OR Spectrum. 2012. V. 34. P. 665–690.
     
  15. Glover F. Future paths for integer programming and links to artificial intelligence // Comput. Oper. Res. 1986. V. 13, No. 5. P. 533–549.
     
  16. Glover F., Laguna M. Tabu search // Modern heuristic techniques for combinatorial problems. New York: Halstead Press, 1993. P. 70–150.
     
  17. Lourenço H. R., Martin O. C., Stützle T. Iterated local search // Handbook of metaheuristics. New York: Kluwer Acad. Publ., 2003. P. 321–353.

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

Моторин Кирилл Олегович
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: k.motorin@g.nsu.ru

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

E-mail: artem@math.nsc.ru

Статья поступила 15 июля 2024 г.
После доработки — 5 августа 2024 г.
Принята к публикации 22 сентября 2024 г.

Abstract:

A warehouse goods placement problem is considered, where the aim is to minimize the total time of fulfillment of orders from a given list. NP-hardness of this problem even in the simplest special case is proved. An ILP model is suggested for this problem. Two heuristic algorithms are developed for solving this problem; their effectiveness is analyzed using randomly generated instances. 

Tab. 3, illustr. 9, bibliogr. 17.

References:
  1. J. Karasek, An overview of warehouse optimization, J. Adv. Telecommun. Electrotech. Signals Syst. 2 (3), 111–117 (2013).
     
  2. F. Caron, G. Marchet, and A. Perego, Optimal layout in low-level pickerto-part systems, Int. J. Prod. Res. 38 (1), 101–117 (2000).
     
  3. J. Gu, M. Goetschalckx, and L. F. McGinnis, Research on warehouse design and performance evaluation: A comprehensive review, Eur. J. Oper. Res. 203 (3), 539–549 (2010).
     
  4. R. de Koster, T. Le-Duc, and K. J. Roodbergen, Design and control of warehouse order picking: A literature review, Eur. J. Oper. Res. 182 (2), 481–501 (2007).
     
  5. A. A. Ratushnyi and Yu. A. Kochetov, Matheuristics for waiting time minimization for trailers with uncertain arrival times, Diskretn. Anal. Issled. Oper. 29 (3), 85–101 (2022) [Russian] [J. Appl. Ind. Math. 16 (3), 540–549 (2022)].
     
  6. H. D. Ratliff and A. S. Rosenthal, Order-picking in a rectangular warehouse: A solvable case of the traveling salesman problem, Oper. Res. 31 (3), 507–521 (1983).
     
  7. K. J. Roodbergen and R. de Koster, Routing order pickers in a warehouse with a middle aisle, Eur. J. Oper. Res. 133 (1), 32–43 (2001).
     
  8. H. Brynzer and M. I. Johansson, Storage location assignment: Using the product structure to reduce order picking times, Int. J. Prod. Econ. 46 (1), 595–603 (1996).
     
  9. R. J. Mantel, P. C. Schuur, and S. S. Heragu, Order oriented slotting: A new assignment strategy for warehouses, Eur. J. Ind. Eng. 1 (3), 301–316 (2007).
     
  10. T. C. Koopmans and M. Beckmann, Assignment problems and the location of economic activities, Econometrica 25 (1), 53–76 (1957).
     
  11. T. N. Bui, S. Chaudhuri, F. T. Leighton, and M. Sipser, Graph bisection algorithms with good average case behavior, Combinatorica 7 (2), 171–191 (1987).
     
  12. M. R. Garey and D. S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982 [Russian]).
     
  13. A. Misevicius and B. Kilda, Comparison of crossover operators for the quadratic assignment problem, Inf. Technol. Control. 34 (2), 109–119 (2005).
     
  14. A. Misevicius, An implementation of the iterated tabu search algorithm for the quadratic assignment problem, OR Spectrum 34, 665–690 (2012).
     
  15. F. Glover, Future paths for integer programming and links to artificial intelligence, Comput. Oper. Res. 13 (5), 533–549 (1986).
     
  16. F. Glover and M. Laguna, Tabu search, in Modern Heuristic Techniques for Combinatorial Problems (Halstead Press, New York, 1993), pp. 70–150.
     
  17. H. R. Lourenço, O. C. Martin, and T. Stützle, Iterated local search, in Handbook of Metaheuristics (Kluwer Acad. Publ., New York, 2003), pp. 321– 353.