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

 
Код статьиS000523100002862-2-1
DOI10.31857/S000523100002862-2
Тип публикации Статья
Статус публикации Опубликовано
Авторы
Аффилиация: Московский авиационный институт (национальный исследовательский университет)
Адрес: Российская Федерация, Москва
Аффилиация: Московский авиационный институт (национальный исследовательский университет)
Адрес: Российская Федерация, Москва
Аффилиация: Московский авиационный институт (национальный исследовательский университет
Адрес: Российская Федерация, Москва, Российская Федерация
Название журналаАвтоматика и телемеханика
ВыпускВыпуск 12
Страницы142-166
Аннотация

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

Ключевые словадекомпозиция, ориентированный граф, сильно связный граф, алгоритм, назначение локомотивов
Дата публикации11.12.2018
Цитировать   Скачать pdf Для скачивания PDF необходимо авторизоваться
Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной.

всего просмотров: 1503

Оценка читателей: голосов 0

1. Лазарев А.А. Оценки абсолютной погрешности и схема приближенного решения задач теории расписаний // Журн. вычислит. матем. и мат. физики. 2009. Т. 49. № 2. C. 14–34.

2. Лазарев А.А., Мусатова Е.Г., Гафаров Е.Р., Кварацхелия А.Г. Теория расписаний. Задачи железнодорожного планирования. М.: ИПУ РАН, 2012.

3. Лазарев А.А., Мусатова Е.Г. Целочисленные постановки задачи формирования железнодорожных составов и расписания их движения // Управление большими системами. 2012. № 38. С. 161–169.

4. Gainanov D.N., Rasskazova V.A. An Inference Algorithm for Monotone Boolean Functions Associated with Undirected Graphs // Bulletin of the SUSU. 2016. No. 9 (3). P. 17–30.

5. Кузнецов Н.А., Пащенко Ф.Ф., Рябых Н.Г., Захарова Е.М., Минашина И.К. Алгоритмы оптимизации в задачах планирования на рельсовом транспорте // Информационные процессы. 2014. № 4 (14). С. 307–318.

6. Такмазьян А.К., Шелудяков А.В. Мультиагентное решение методом аукционов многопродуктовой транспортной задачи с объединенными потребностями // ИСУЖТ. 2015. № 1. C. 110–112.

7. Piu F., Speranza M.G. The Locomotive Assignment Problem: A Survey on Optimization Models // Intl. Trans. in Op. Res. 2014. No. 21. P. 327–352.

8. Азанов В.М., Буянов М.В., Гайнанов Д.Н., Иванов С.В. Алгоритмическое и программное обеспечение для назначения локомотивов с целью перевозки грузовых составов // Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование. 2016. № 9. С. 73–85.

9. Иванов С.В., Кибзун А.И., Осокин А.В. Оптимизационная стохастическая мо- дель назначения локомотивов для перевозки грузовых составов // АиТ. 2016. № 11. С. 80–95.

10. Матюхин В.Г., Кузнецов Н.А., Шабунин А.Б., Жилякова Л.Ю., Такмазьян А.К. Графовая динамическая модель задачи подбора тяговых ресурсов для грузовых железнодорожных перевозок // ИСУЖТ–2017. М.: АО “НИИАС”, 2017. С. 14–18.

11. Гайнанов Д.Н., Коныгин А.В., Рассказова В.А. Математическое моделирование грузовых железнодорожных перевозок методами теории графов и комбинатор- ной оптимизации // АиТ. 2016. № 11. С. 60–79.

12. Matyukhin V.G., Shabunin A.B., Kuznetsov N.A., Takmazian A.K. Rail Transport Control by Combinatorial Optimization Approach // 11th Int. Conf. on Application of Information and Communication Technologies. 2017. No. 1. P. 419–422.

13. Гайнанов Д.Н., Кибзун А.И., Рассказова В.А. Алгоритм покрытия вершин ори- ентированного графа множеством ориентированных путей в задаче оптималь- ного назначения и перемещения локомотивов // Вестн. компьют. и информац. технологий. 2017. № 5. С. 51–56.

14. Тышкевич Р.И., Суздаль С.В., Максимович О.В., Петрович Р.А. Алгебраиче- ская теория декомпозиции графов // Вестн. БГУ. 2011. No. 1 (3). С. 126–138.

15. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. М.: МЦНМО, 2014.

16. Корте Б., Фиген Й. Комбинаторная оптимизация. Теория и алгоритмы. М.: МЦНМО, 2015.

17. Gardiner E., Willett P., Artymiuk P. Graph-Theoretic Techniques for Macromolecular Docking // J. Chem. Inf. Comput. 2000. No. 40. P. 273–279.

18. Быкова В.В. О разложении гиперграфа кликовыми минимальными сепараторами // Журн. Сиб. федерального ун-та. 2012. № 1 (5). С. 36–45.

19. Харари Ф. Теория графов. М.: Мир, 1973.

20. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

Система Orphus

Загрузка...
Вверх