Укр
Eng
Журнал
Автору

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

Васянін Володимир Олександрович, кандидат технічних наук, старший науковий співробітник Інституту телекомунікацій та глобального інформаційного простору НАН України, м. Київ

pages 144-159

DOI: 10.1615/JAutomatInfScien.v47.i2.60

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

  1. Васянин В.А. Обобщенная задача упаковки и распределения мелкопартионных потоков в многопродуктовых иерархических сетях и ее последовательная декомпозиция // Еколо-
    гічна безпека та природокористування. — 2012. — Вип. 11. — С. 136–154. 
  2. Васянин В.А., Трофимчук А.Н. Линейные целочисленные модели распределения потоков в задачах проектирования и анализа многопродуктовых коммуникационных сетей // Там же. — 2013. — Вип. 12. — С. 147–165.
  3. Васянин В.А. Справочная матрица слияния потоков в задачах оптимизации упаковок на многопродуктовых сетях // Системні дослідження та інформаційні технології. — 2014. — № 3. — С. 42–49. 
  4. Васянин В.А., Трофимчук А.Н. Выбор пропускных способностей дуг при оптимизации упаковок мелкопартионных потоков в многопродуктовых коммуникационных сетях // Екологічна безпека та природокористування. — 2012. — Вип. 9. — С. 181–200. 
  5. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М. : Мир, 1982. — 416 с. 
  6. Аssad A.A. Modeling of rail networks: Toward a routing / makeup model // Transportation Research. — 1980. — 148, N 1–2. — P. 101–114.
  7. Аssad A.A. Multicommodity network flows. A survey // Networks. — 1978. — N 8. — P. 37–91. 
  8. Kennington J.L. A survey of linear cost multicommodity networks flows // Oper. Res. — 1978. — 26. — P. 206–236.
  9. Михалевич B.C., Трубин В.А., Шор H.З. Оптимальные задачи производственно-транспортного планирования. Модели, методы и алгоритмы. — М. : Наука, 1986. — 264 с. 
  10. Сергиенко И.В. Математические модели и методы решения дискретных задач оптимизации. — Киев: Наук. думка, 1988. — 472 с. 
  11. Васильева Е.М., Левит Б. Ю., Лившиц B. H. Нелинейные транспортные задачи на сетях. — М. : Финансы и статистика, 1981. — 104 с. 
  12. Левит Б.Ю., Лившиц B.H. Нелинейные сетевые транспортные задачи. — М. : Транспорт, 1972. — 144 с. 
  13. Клейнрок Л. Коммуникационные сети. Стохастические потоки и задержки сообщений. — М. : Наука, 1970. — 256 с. 
  14. Клейнрок Л. Вычислительные системы с очередями. — М. : Мир, 1979. — 600 с.
  15. Courtois P.J., Semal P. An algorithm for the optimization of nonbifurcated flows in computer communication networks // Performance Evaluation. — 1981. — 1. — P. 139–152.
  16. Gavish B., Hantler S.L. An algorithm for optimal route selection in SNA networks // IEEE Trans. Commun. — 1983. — COM-31, N 10. — P. 1154–1161.
  17. Зайченко Ю.П., Гонта Ю.В. Структурная оптимизация сетей ЭВМ. — Киев : Техніка, 1986. — 168 с. 
  18. Бертсекас Д., Галлагер Р. Сети передачи данных: Пер. с англ. — М. : Мир, 1989. — 544 с. 
  19. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. — М. : Техносфера, 2003. — 512 с.
  20. Адельсон-Beльcкий Г.М., Диниц E.A., Карзанов А.B. Потоковые алгоритмы. — М. : Наука, 1975. — 119 с.
  21. Папернов Б.A. Реализуемость многопродуктовых потоков // Исследования по дискретной оптимизации. — М. : Наука, 1976. — C. 230–261.
  22. Комбинаторные методы в потоковых задачах: Сборник трудов. Вып. 3 / Под ред. А.B. Карзанова. — М. : Всесоюз. НИИ системных исследований, 1979. — 160 с. 
  23. Малашенко Ю.Е. Нормативный подход к анализу многопродуктовых сетей // Изв. АН СССР. Техн. кибернетика. — 1988. — № 3. — С. 117–122.
  24. Малашенко Ю.Е., Новикова Н.М. Обобщенная задача анализа многопродуктовой сети // Там же. — 1989. — № 4. — С. 137–152. 
  25. Малашенко Ю.Е. Математические модели анализа потоковых сетевых систем. — М. : ВЦ РАН, 1993. — 56 с.
  26. Ahuja R. K., Magnanti T. L., Orlin J. B. Network flows: theory, algorithms, and applications. — Upper Saddle River (New Jersey ) : Prentice-Hall, Inc., 1993. — 846 p.
  27. Задачі оптимального проектування надійних мереж / Н.З. Шор, І.В. Сергієнко, В.П. Шило, П.І. Стецюк та ін. — Київ : Наук. думка, 2005. — 229 с. 
  28. Yaghini M., Akhavan R. Multicommodity network design problem in rail freight transportation planning // 8th Intern. Conf. on Traffic and Transportation Studies. Changsha, China, August 1–3. — 2012. — N 3. — P. 728–739.
  29. A survey of transportation problems / O. Díaz-Parra, J.A. Ruiz-Vanoye, B.B. Loranca, A. Fuentes-Penna, R.A. Barrera-Cámara // Journal of Applied Mathematics. — 2014. — Article ID 848129. — 17 p. 
  30. Васянин В.А. Двухкритериальный лексикографический алгоритм построения всех кратчайших путей в сети // Кибернетика и системный анализ. — 2014. — № 5. — С. 122–131. 
  31. Васянин В.А., Ушакова Л.П. Структуры данных и процедуры редукции маршрутов в задачах распределения потоков в коммуникационных сетях // Екологічна безпека та природокористування. — 2014. — Вип. 14. — С. 192–205.