Перейти к основному содержанию

Моделирование и анализ данных
2020. Том 10. № 3. С. 60–68
https://doi.org/10.17759/mda.2020100305
ISSN: 2219-3758 / 2311-9454 (online)

Практическая реализация алгоритма декомпозиции путей ориентированного графа

 
Аудио генерируется искусственным интеллектом
694

,

PDF (RUS)
GS
Информация
в Google Scholar
Метрики

Резюме

Работа направлена на прояснение некоторых особенностей программной реализации алгоритма декомпозиции путей ориентированного графа. Разобраны алгоритмы для формирования таблицы M для декомпозиции множества путей, сортировки таблицы M по полю NΣ и расчета балансов. На основе данных алгоритмов и исходного алгоритма декомпозиции путей ориентированного графа разработан комплекс программ на языке программирования Python. Проведены расчеты для случайного графа размерности 100 вершин и приводится время работы предложенного алгоритма. Полученные результаты могут быть использованы при решении задачи организации грузовых железнодорожных перевозок на этапе назначения и перемещения локомотивов. Научная и практическая новизна работы заключается в существенном снижении размерности исходной задачи, что особенно важно в условиях транспортных сетей сложной топологии.

Общая информация

Ключевые слова: теория оптимизации, оптимизация на графах, алгоритм декомпозиции путей ориентированного графа, сильно связный граф, подграфы

Рубрика издания: Методы оптимизации

OpenAlex цитирования: 2

OpenAlex тренды: Инновации в области транспорта и логистики, Транспортные системы и логистика, Анализ систем городского транспорта

Информация о публикации в OpenAlex

Количество цитирований: 2

Темы публикации

Инновации в области транспорта и логистики

Этот кластер документов посвящен различным аспектам управления транспортом и логистикой, включая проектирование логистических систем, устойчивое управление человеческими ресурсами, цифровизацию, оптимизацию цепочки поставок и железнодорожные перевозки. В нем рассматриваются такие темы, как влияние управления людскими ресурсами на конкурентоспособность, устойчивость на глобализованном транспорте и применение цифровых технологий для обмена знаниями и разумного обслуживания. Тематический блок отражает междисциплинарный подход к решению проблем и использованию возможностей в секторе транспорта и логистики.

Количество публикаций: 51786  |  Общее количество цитирований: 39486

Подробнее о теме в OpenAlex

Транспортные системы и логистика

Этот блок документов посвящен разработке и совершенствованию систем и инфраструктуры безопасности дорожного движения, включая интеллектуальные транспортные системы, дорожную инфраструктуру, диагностику транспортных средств, управление движением и воздействие транспорта на окружающую среду. В нем рассматриваются такие темы, как реконструкция аварий, цифровые технологии на транспорте и влияние эксплуатационных факторов на экологическую безопасность.

Количество публикаций: 24013  |  Общее количество цитирований: 38397

Подробнее о теме в OpenAlex

Анализ систем городского транспорта

Этот кластер статей посвящен планированию, моделированию и управлению транспортными системами с акцентом на цифровые технологии, управление качеством, городской трафик, надежность, инфраструктуру, логистику и кибербезопасность.

Количество публикаций: 46745  |  Общее количество цитирований: 43271

Подробнее о теме в OpenAlex

Подробнее о публикации в OpenAlex

Тип материала: научная статья

DOI: https://doi.org/10.17759/mda.2020100305

Опубликована

Для цитаты: Золотарев, И.А., Рассказова, В.А. (2020). Практическая реализация алгоритма декомпозиции путей ориентированного графа. Моделирование и анализ данных, 10(3), 60–68. https://doi.org/10.17759/mda.2020100305

© Золотарев И.А., Рассказова В.А., 2020

Лицензия: CC BY-NC 4.0

Фрагмент статьи

Практическая реализация алгоритма декомпозиции путей ориентированного графа вызывает несколько побочных задач, требующих решения. Во-первых, нужно построить таблицу, которая будет использоваться в алгоритме.

Литература

  1. Гайнанов Д.Н., Коныгин А.В., Рассказова В.А. Моделирование грузовых железнодорожных перевозок методами теории графов и комбинаторной оптимизации // Автоматика и телемеханика. 2016. № 11. С. 60–79.
  2. Гайнанов Д.Н., Кибзун А.И., Рассказова В.А. Теоретико-графовый алгоритм решения задачи о назначении и перемещении локомотивов // Вестник компьютерных и информационных технологий. 2017. № 5. С. 51–56.
  3. Гайнанов Д.Н., Кибзун А.И., Рассказова В.А. Задача о декомпозиции множества путей ориентированного графа и ее приложение // Автоматика и телемеханика. 2018. № 12. С. 142–166.

Информация об авторах

Игорь Антонович Золотарев, студент магистратуры, Московский авиационный институт (НИУ МАИ), Москва, Российская Федерация, ORCID: https://orcid.org/0000-0002-6437-2212, e-mail: yngvar.antonsson@gmail.com

Варвара Андреевна Рассказова, кандидат физико-математических наук, доцент кафедры 804 «Теория вероятностей и компьютерное моделирование», Московский авиационный институт (НИУ МАИ), Москва, Российская Федерация, ORCID: https://orcid.org/0000-0003-4943-3133, e-mail: varvara.rasskazova@mail.ru

Метрики

 Просмотров web

За все время: 514
В прошлом месяце: 9
В текущем месяце: 14

 Скачиваний PDF

За все время: 180
В прошлом месяце: 3
В текущем месяце: 11

 Всего

За все время: 694
В прошлом месяце: 12
В текущем месяце: 25