Cybernetics And Systems Analysis logo
Інформація редакції Аннотації статей Автори Архів
Кібернетика та Системний Аналіз
Міжнародний Науково-Теоретичний Журнал
Том 58 >>> № 6 ЛИСТОПАД — ГРУДЕНЬ 2022
-->

УДК 519.168; 519.854.3

В.О. ВАСЯНІН,
Інститут телекомунікацій і глобального інформаційного простору НАН України, Київ, Україна,  archukr@meta.ua

О.М. ТРОФИМЧУК,
Інститут телекомунікацій і глобального інформаційного простору НАН України, Київ, Україна,  itgis@nas.gov.ua

Л.П. УШАКОВА,
Інститут телекомунікацій і глобального інформаційного простору НАН України, Київ, Україна,  archukr@meta.ua


ЗАДАЧА МАРШРУТИЗАЦІЇ ЗБІРНИХ ВАНТАЖІВ У БАГАТОПРОДУКТОВІЙ
ТРАНСПОРТНІЙ МЕРЕЖІ ІЗ ЗАДАНИМИ ТАРИФАМИ
І ОБМЕЖЕННЯМИ НА ЧАС ДОСТАВКИ

Анотація. Розглянуто мережеве формулювання задачі оптимізації маршрутизації потоків збірних вантажів у транспортній мережі із заданими тарифами на транспортування й оброблення потоків та обмеженнями на пропускні спроможності дуг, вузлів і час доставки окремих вантажів одержувачу. Для розрахунку часу доставки запропоновано спосіб формування довідкової матриці об’єднання потоків окремих вантажів і ефективні алгоритми, що дають змогу визначати вузли об’єднання та об’єднані потоки для всіх пар, що кореспондуються в багатопродуктовій мережі. Доведено, що задачу з тарифами в мережевій постановці можна за поліноміальний час перетворити у задачу цілочислового лінійного програмування з блочною структурою та зв’язувальними обмеженнями. Наведено особливості розв’язання перетвореної задачі з використанням відомих методів цілочислового програмування та пакетів прикладних програм.

Ключові слова: математичні моделі розподілу та маршрутизації потоків у багатопродуктових мережах, задачі оптимізації з дискретними потоками та параметрами.


ПОВНИЙ ТЕКСТ

СПИСОК ЛІТЕРАТУРИ

  1. Васянин В.А. Методология проектирования многопродуктовых коммуникационных сетей с дискретными потоками: дис. ... докт. техн. наук. 01.05.02. Киев, 2017. 497 с. URL: https://itgip.org/wp-content .

  2. The freight story: A national perspective on enhancing freight transportation. Federal Highway Administration. 2005. Freight Management and Operations. URL: http://ops.fhwa.dot.gov/ freight .

  3. US international trade and freight transportation trends. United States Department of Transportation: Bureau of Transportation Statistics. 2003. URL: www.bts.gov .

  4. Barnhart C., Hane C.A., Vance P.H. Integer multicommodity flow problems. In: Network Optimization. Pardalos P.M., Hearn D.W., Hager W.W. (Eds.). Lecture Notes in Economics and Mathematical Systems. 1997. Vol. 450. P. 17–31. doi.org/10.1007/978-3-642-59179-2_2.

  5. Barnhart C., Hane C.A., Vance P.H. Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Operations Research. 2000. Vol. 48, N 2. P. 318–326. doi.org/10.1287/opre.48.2.318.12378 .

  6. Encyclopedia of optimization. Second Ed. Floudas C.A., Pardalos P.M. (Eds.). New York: Springer, 2009. 4626 p.

  7. Wang I-L. Multicommodity network flows: a survey, part I: applications and formulations. International Journal of Operations Research. 2018. Vol. 15, N 4. P. 145–153. doi.org/10.6886/IJOR.201812_15(4).0001.

  8. Wang I-L. Multicommodity network flows: a survey, part II: solution methods. International Journal of Operations Research. 2018. Vol. 15, N 4. P. 155–173. doi.org/10.6886/IJOR.201812_15(4).0002.

  9. Cohn A., Root S., Wang A., Mohr D. Integration of the load matching and routing problem with equipment balancing for small package carriers. Transportation Science. 2007. Vol. 41, Iss. 2. P. 238–252. doi.org/10.1287/trsc.1060.0174 .

  10. Hellsten E., Koza D.F., Contreras I., Cordeau J.F., Pisinger D. The transit time constrained fixed charge multi-commodity network design problem. Computers & Operations Research. 2021. Vol. 136. 105511. doi.org/10.1016/j.cor.2021.105511.

  11. Trivella A., Corman F., Koza D.F., Pisinger D. The multi-commodity network flow problem with soft transit time constraints: Application to liner shipping. Transportation Research Part E: Logistics and Transportation Review. 2021. Vol. 150. 102342. doi.org/10.1016/j.tre.2021.102342.

  12. Trofymchuk O.M., Vasyanin V.A. Simulation of packing, distribution and routing of small-size discrete flows in a multicommodity network. Journal of Automation and Information Sciences. 2015. Vol. 47, Iss. 7. P. 15–30. doi.org/10.1615/JAutomatInfScien.v47.i7.30 .

  13. Trofymchuk O.M., Vasyanin V.A., Kuzmenko V.N. Optimization algorithms for packing of small-lot correspondence in communication networks. Cybernetics and Systems Analysis. 2016. Vol. 52, N 2. P. 258–268. doi.org/10.1007/s10559-016-9822-5.

  14. Трофимчук А.Н., Васянин В.А. Компьютерное моделирование иерархической структуры коммуникационной сети с дискретными многопродуктовыми потоками. УСиМ. 2016. № 2. С. 48–57. doi.org/10.15407/usim.2016.02.048.

  15. Трофимчук А.Н., Васянин В.А., Ушакова Л.П. Исследование задачи оптимизации иерархической структуры разреженной и плотной коммуникационной сети. Проблемы управления и информатики. 2021. № 1. С. 5–21.

  16. Vasyanin V.A. Problem of distribution and routing of transport blocks with mixed attachments and its decomposition. Journal of Automation and Information Sciences. 2015. Vol. 47, Iss. 2. P. 56–69. doi.org/10.1615/JAutomatInfScien.v47.i2.60 .

  17. Васянин В.А. Компьютерное моделирование распределения и маршрутизации дискретных многопродуктовых потоков в коммуникационной сети. УСиМ. 2016. № 3. С. 43–53. doi.org/10.15407/usim.2016.03.043.

  18. Васянин В.А., Трофимчук А.Н., Ушакова Л.П. Экономико-математические модели задачи распределения потоков в многопродуктовой коммуникационной сети. Математичне моделювання в економіці. 2016. № 2. С. 5–21. URL: http://dspace.nbuv.gov.ua .

  19. Trofymchuk O.M., Vasyanin V.A., Kuzmenko V.N. Complexity of one packing optimization problem. Cybernetics and Systems Analysis. 2016. Vol. 52, N 1. P. 76–84. doi.org/10.1007/ s10559-016-9802-9.

  20. Васянин В.А. Справочная матрица слияния потоков в задачах оптимизации упаковок на многопродуктовых сетях. Системні дослідження та інформаційні технології. 2014. № 3. С. 42–49. URL: http://dspace.nbuv.gov.ua .

  21. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Москва: Мир, 1982. 416 с.

  22. Even S., Itai A., Shamir A. On the complexity of timetable and multicommodity flow problems. SIAM J. Comput. 1976. Vol. 5, Iss. 4. P. 691–703. doi.org/10.1137/0205048.

  23. NVIDIA Developer. URL: https://developer.nvidia.com/cuda-zone .

  24. Best Practices Guide (PDF) — v11.6.2 (older) — Last updated March 24, 2022. URL: https://docs.nvidia.com/cuda .




Інформація редакції Аннотації статей Автори Архів
Журнал Тематичні Розділи Редакція Редакційна колегія Приклади документів Передплата Контакти
© 2022 Kibernetika.org. All rights reserved.