Метод декомпозиции для управления запасами в двухэшелонной системе складов

Метод декомпозиции для управления запасами в двухэшелонной системе складов

Юськов А. Д., Кулаченко И. Н., Мельников А. А., Кочетов Ю. А.
Дискретный анализ и исследование операций, 31, 4, 186-212 (2024)
Скачать статью

УДК 519.8 
DOI: 10.33048/daio.2024.31.794

Аннотация:

Склады первого эшелона в двухэшелонной системе предназначены для выполнения заказов клиентов. Во втором эшелоне находится центральный склад, пополняющий запасы на складах первого эшелона. Заказы клиентов можно выполнять частично, но общая доля выполненных заказов должна быть не меньше заданного порога. Требуется минимизировать общую стоимость хранения товаров на всех складах. Работа системы моделируется с помощью детерминированной имитационной модели, которая вычисляет долю удовлетворения заказов и стоимость хранения в течение планового периода в зависимости от параметров управления запасами на каждом складе по каждому типу товара. Разработан метод декомпозиции, основанный на решении подзадач для каждого типа товара. Предложены подходы для точного решения задачи. Приводятся результаты вычислительных экспериментов на примерах со 100 складами и 1000 типами товаров. На примерах с известным точным решением в двух случаях удалось найти оптимум, в остальных случаях отклонение от оптимума составило не более 1,9%. 
Табл. 5, ил. 1, библиогр. 23.

Литература:
  1. Wassick J. M., Agarwal A., Akiya N. [et al.]. Addressing the operational challenges in the development, manufacture, and supply of advanced materials and performance products // Comput. Chem. Eng. 2012. V. 47. P. 157–169. DOI: 10.1016/j.compchemeng.2012.06.041.
     
  2. Grossmann I. Enterprise-wide optimization: A new frontier in process systems engineering // AIChE J. 2005. V. 51, No. 7. P. 1846–1857. DOI: 10.1002/aic. 10617.
     
  3. Zhang S., Huang K., Yuan Y. Spare parts inventory management: A literature review // Sustainability (Switz.). 2021. V. 13, No. 5. Paper ID 2460. 23 p. DOI: 10.3390/su13052460.
     
  4. Lee H. L. A multi-echelon inventory model for repairable items with emergency lateral transshipments // Manag. Sci. 1987. V. 33, No. 10. P. 1302–1316. DOI: 10.1287/mnsc.33.10.1302.
     
  5. Axsäter S. Modelling emergency lateral transshipments in inventory systems // Manag. Sci. 1990. V. 36, No. 11. P. 1329–1338. DOI: 10.1287/mnsc. 36.11.1329.
     
  6. Wong H., van Houtum G. J., Cattrysse D., Van Oudheusden D. Simple, efficient heuristics for multi-item multi-location spare parts systems with lateral transshipments and waiting time constraints // J. Oper. Res. Soc. 2005. V. 56, No. 12. P. 1419–1430. DOI: 10.1057/palgrave.jors.2601952.
     
  7. Yue D., You F. Planning and scheduling of flexible process networks under uncertainty with stochastic inventory: MINLP models and algorithm // AIChE J. 2013. V. 59, No. 5. P. 1511–1532. DOI: 10.1002/aic.13924.
     
  8. Zapata J. C., Pekny J., Reklaitis G. V. Simulation-optimization in support of tactical and strategic enterprise decisions // Planning production and inventories in the extended enterprise. A state of the art handbook. V. 1. New York: Springer, 2011. P. 593–627. (Int. Ser. Oper. Res. Manag. Sci.; V. 151). DOI: 10.1007/978-1-4419-6485-4\_20.
     
  9. Peidro D., Mula J., Poler R., Lario F. C. Quantitative models for supply chain planning under uncertainty // Int. J. Adv. Manuf. Technol. 2009. V. 43. P. 400–420. DOI: 10.1007/s00170-008-1715-y.
     
  10. Köchel P., Nieländer U. Simulation-based optimisation of multi-echelon inventory systems // Int. J. Prod. Econ. 2005. V. 93–94. P. 505–513. DOI: 10.1016/j.ijpe.2004.06.046.
     
  11. Chu Y., You F., Wassick J. M., Agarwal A. Simulation-based optimization framework for multi-echelon inventory systems under uncertainty // Comput. Chem. Eng. 2015. V. 73. P. 1–16. DOI: 10.1016/j.compchemeng.2014. 10.008.
     
  12. Mele F. D., Guillén G., Espuña A, Puigjaner L. A simulation-based optimization framework for parameter optimization of supply-chain networks // Ind. Eng. Chem. Res. 2006. V. 45, No. 9. P. 3133–3148. DOI: 10.1021/ ie051121g.
     
  13. Moncayo-Martínez L. A., Zhang D. Z. Multi-objective ant colony optimisation: A meta-heuristic approach to supply chain design // Int. J. Prod. Econ. 2011. V. 131, No. 1. P. 407–420. DOI: 10.1016/j.ijpe.2010.11.026.
     
  14. Nikolopoulou A., Ierapetritou M. G. Hybrid simulation based optimization approach for supply chain management // Comput. Chem. Eng. 2012. V. 47. P. 183–193. DOI: 10.1016/j.compchemeng.2012.06.045.
     
  15. Blum C., Puchinger J., Raidl G. R., Roli A. Hybrid metaheuristics in combinatorial optimization: A survey // Appl. Soft Comput. 2011. V. 11, No. 6. P. 4135–4151. DOI: 10.1016/j.asoc.2011.02.032.
     
  16. Noordhoek M., Dullaert W., Lai D. S. W., de Leeuw S. A simulation–optimization approach for a service-constrained multi-echelon distribution network // Transp. Res. Part E: Logist. Transp. Rev. 2018. V. 114. P. 292–311. DOI: 10.1016/j.tre.2018.02.006.
     
  17. Chen H., Dai B., Li Y. [et al.]. Stock allocation in a two-echelon distribution system controlled by ($s, S$) policies // Int. J. Prod. Res. 2022. V. 60, No. 3. P. 894–911. DOI: 10.1080/00207543.2020.1845915.
     
  18. Rapin J., Teytaud O. Nevergrad — A gradient-free optimization platform. 2018. URL: GitHub.com/FacebookResearch/Nevergrad (accessed: 24.01.2024).
     
  19. Yuskov A. D., Kulachenko I. N., Melnikov A. A., Kochetov Yu. A. Decomposition approach for simulation-based optimization of inventory management // Mathematical optimization theory and operations research: Recent trends. Rev. Sel. Pap. 22nd Int. Conf. (Yekaterinburg, Russia, July 2–8, 2023). Cham: Springer, 2023. P. 259–273. (Commun. Comput. Inf. Sci.; V. 1881). DOI: 10.1007/978-3-031-43257-6\_20.
     
  20. Bajaj I., Arora A., Hasan M. M. F. Black-box optimization: Methods and applications // Black box optimization, machine learning, and no-free lunch theorems. Cham: Springer, 2021. P. 35–65. (Springer Optim. Its Appl.; V. 170). DOI: 10.1007/978-3-030-66515-9\_2.
     
  21. Bezanson J., Edelman A., Karpinski S., Shah V. B. Julia: A fresh approach to numerical computing // SIAM Rev. 2017. V. 59, No. 1. P. 65–98. DOI: 10.1137/141000671.
     
  22. Topan E., Bayındır Z. P., Tan T. Heuristics for multi-item two-echelon spare parts inventory control subject to aggregate and individual service measures // Eur. J. Oper. Res. 2017. V. 256. P. 126–138. DOI: 10.1016/j.ejor. 2016.06.012.
     
  23. Thonemann U. W., Brown A. O., Hausman W. H. Easy quantification of improved spare parts inventory policies // Manag. Sci. 2002. V. 48, No. 9. P. 1213–1225. DOI: 10.1287/mnsc.48.9.1213.173.

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

Юськов Александр Дмитриевич
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: a.yuskov@g.nsu.ru

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

E-mail: ink@math.nsc.ru

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

E-mail: melnikov@math.nsc.ru

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

E-mail: jkochet@math.nsc.ru

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

Abstract:

Warehouses of the first echelon in a two-echelon system are designed to satisfy customer orders. In the second echelon, we have a central warehouse for restocking the first echelon warehouses. Customer orders can be partially satisfied, but the total fraction of completed orders should not be less than the specified threshold. We need to minimize the total cost of storing the items in all warehouses. We use a deterministic simulation to calculate the order satisfaction ratio and the storage cost during the planning period. The simulation depends on inventory management policies at each warehouse for each type of items. We develop a decomposition method for solving the problem. It is based on solution of subproblems for each type of items. Also, we propose some approaches for exact solution of the problem. The results of numerical experiments with instances with 100 warehouses and 1000 types of items are presented. On instances with known exact solutions, we have the optimum in two cases, while in the other cases the deviation from the optimal values is at most 1.9%. 
Tab. 5, illustr. 1, bibliogr. 23.

References:
  1. J. M. Wassick, A. Agarwal, N. Akiya, [et al.]. Addressing the operational challenges in the development, manufacture, and supply of advanced materials and performance products, Comput. Chem. Eng. 47, 157–169 (2012), DOI: 10.1016/j.compchemeng.2012.06.041.
     
  2. I. Grossmann, Enterprise-wide optimization: A new frontier in process systems engineering, AIChE J. 51 (7), 1846–1857 (2005), DOI: 10.1002/aic. 10617.
     
  3. S. Zhang, K. Huang, and Y. Yuan, Spare parts inventory management: A literature review, Sustainability (Switz.) 13 (5), ID 2460 (2021), DOI: 10.3390/su13052460.
     
  4. H. L. Lee, A multi-echelon inventory model for repairable items with emergency lateral transshipments, Manag. Sci. 33 (10), 1302–1316 (1987), DOI: 10.1287/mnsc.33.10.1302.
     
  5. S. Axsäter, Modelling emergency lateral transshipments in inventory systems, Manag. Sci. 36 (11), 1329–1338 (1990), DOI: 10.1287/mnsc.36.11.1329.
     
  6. H. Wong, G. J. van Houtum, D. Cattrysse, and D. Van Oudheusden, Simple, efficient heuristics for multi-item multi-location spare parts systems with lateral transshipments and waiting time constraints, J. Oper. Res. Soc. 56 (12), 1419–1430 (2005), DOI: 10.1057/palgrave.jors.2601952.
     
  7. D. Yue and F. You, Planning and scheduling of flexible process networks under uncertainty with stochastic inventory: MINLP models and algorithm, AIChE J. 59 (5), 1511–1532 (2013), DOI: 10.1002/aic.13924.
     
  8. J. C. Zapata, J. Pekny, and G. V. Reklaitis, Simulation-optimization in support of tactical and strategic enterprise decisions, in Planning Production and Inventories in the Extended Enterprise. A State of the Art Handbook, Vol. 1 (Springer, New York, 2011), pp. 593–627 (Int. Ser. Oper. Res. Manag. Sci., Vol. 151), DOI: 10.1007/978-1-4419-6485-4\_20.
     
  9. D. Peidro, J. Mula, R. Poler, F. C. Lario, Quantitative models for supply chain planning under uncertainty, Int. J. Adv. Manuf. Technol. 43, 400–420 (2009), DOI: 10.1007/s00170-008-1715-y.
     
  10. P. Köchel and U. Nieländer, Simulation-based optimisation of multi-echelon inventory systems, Int. J. Prod. Econ. 93–94, 505–513 (2005), DOI: 10.1016/ j.ijpe.2004.06.046.
     
  11. Y. Chu, F. You, J. M. Wassick, and A. Agarwal, Simulation-based optimization framework for multi-echelon inventory systems under uncertainty, Comput. Chem. Eng. 73, 1–16 (2015), DOI: 10.1016/j.compchemeng.2014. 10.008.
     
  12. F. D. Mele, G. Guillén, Espuña A and L. Puigjaner, A simulation-based optimization framework for parameter optimization of supply-chain networks, Ind. Eng. Chem. Res. 45 (9), 3133–3148 (2006), DOI: 10.1021/ie051121g.
     
  13. L. A. Moncayo-Martínez and D. Z. Zhang, Multi-objective ant colony optimisation: A meta-heuristic approach to supply chain design, Int. J. Prod. Econ. 131 (1), 407–420 (2011), DOI: 10.1016/j.ijpe.2010.11.026.
     
  14. A. Nikolopoulou and M. G. Ierapetritou, Hybrid simulation based optimization approach for supply chain management, Comput. Chem. Eng. 47, 183–193 (2012), DOI: 10.1016/j.compchemeng.2012.06.045.
     
  15. C. Blum, J. Puchinger, G. R. Raidl, and A. Roli, Hybrid metaheuristics in combinatorial optimization: A survey, Appl. Soft Comput. 11 (6), 4135–4151 (2011), DOI: 10.1016/j.asoc.2011.02.032.
     
  16. M. Noordhoek, W. Dullaert, D. S. W. Lai, and S. de Leeuw, A simulation–optimization approach for a service-constrained multi-echelon distribution network, Transp. Res., Part E: Logist. Transp. Rev. 114, 292–311 (2018), DOI: 10.1016/j.tre.2018.02.006.
     
  17. H. Chen, B. Dai, Y. Li, [et al.]. Stock allocation in a two-echelon distribution system controlled by (s, S) policies, Int. J. Prod. Res. 60 (3), 894–911 (2022), DOI: 10.1080/00207543.2020.1845915.
     
  18. J. Rapin and O. Teytaud, Nevergrad — A gradient-free optimization platform. 2018. URL: GitHub.com/FacebookResearch/Nevergrad (accessed: 24.01.2024).
     
  19. A. D. Yuskov, I. N. Kulachenko, A. A. Melnikov, and Yu. A. Kochetov, Decomposition approach for simulation-based optimization of inventory management, in Mathematical Optimization Theory and Operations Research: Recent Trends (Rev. Sel. Pap. 22nd Int. Conf., Yekaterinburg, Russia, July 2–8, 2023) (Springer, Cham, 2023), pp. 259–273 (Commun. Comput. Inf. Sci., Vol. 1881), DOI: 10.1007/978-3-031-43257-6\_20.
     
  20. I. Bajaj, A. Arora, and M. M. F. Hasan, Black-box optimization: Methods and applications, in Black Box Optimization, Machine Learning, and No-Free Lunch Theorems (Springer, Cham, 2021), pp. 35–65 (Springer Optim. Its Appl., Vol. 170), DOI: 10.1007/978-3-030-66515-9\_2.
     
  21. J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, Julia: A fresh approach to numerical computing, SIAM Rev. 59 (1), 65–98 (2017), DOI: 10. 1137/141000671.
     
  22. E. Topan, Z. P. Bayındır and T. Tan, Heuristics for multi-item two-echelon spare parts inventory control subject to aggregate and individual service measures, Eur. J. Oper. Res. 256, 126–138 (2017), DOI: 10.1016/j.ejor.2016. 06.012.
     
  23. U. W. Thonemann, A. O. Brown, and W. H. Hausman, Easy quantification of improved spare parts inventory policies, Manag. Sci. 48 (9), 1213–1225 (2002), DOI: 10.1287/mnsc.48.9.1213.173.