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

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

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

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

PlumX

Метрики публикации