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

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

Ключевые слова

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

Дата публикации

11.12.2018

Цитировать Скачать pdf Для скачивания PDF необходимо авторизоваться

ГОСТ	Гайнанов Д. Н. , Кибзун А. И. , Рассказова В. А. Задача о декомпозиции множества путей ориентированного графа и ее приложение // Автоматика и телемеханика – 2018. – Выпуск 12 C. 142-166 [Электронный ресурс]. URL: http://ras.jes.su/ait/s000523100002862-2-1 (дата обращения: 21.04.2025). DOI: 10.31857/S000523100002862-2
MLA	Gainanov, D., Kibzun, A., Rasskazova, V. "The Decomposition Problem for the Set of Paths in a Directed Graph and Its Application." Avtomatika i Telemekhanika 12 (2018):142-166. DOI: 10.31857/S000523100002862-2
APA	Gainanov D., Kibzun A., Rasskazova V. (2018). The Decomposition Problem for the Set of Paths in a Directed Graph and Its Application. Avtomatika i Telemekhanika (12), pp.142-166 DOI: 10.31857/S000523100002862-2

Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной.

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

Оценка читателей: голосов 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.