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

Авторы

Гайнанов Д. Н.^*, Рассказова В. А.^**

Московский авиационный институт (национальный исследовательский университет), Волоколамское шоссе, 4, Москва, A-80, ГСП-3, 125993, Россия

*e-mail: damir.gainanov@gmail.com
**e-mail: varvara.rasskazova@mail.ru

Аннотация

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

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

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

Библиографический список

1. Малинина Н.Л. Противоречия в свойствах двух основных типов сетевых моделей и пути их разрешения // Труды МАИ, 2010, № 37: http://www.mai.ru/science/trudy/published.php?ID=13440

2. Кобко Л.И. Комплексный комбинаторный метод построения расписания работы рабочих мест первичных производственных систем // Труды МАИ, 2001, № 3: http://www.mai.ru/science/trudy/published.php?ID=34687

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

4. Гафаров Е.Р., Лазарев А.А. Преобразование сетевого графика задач теории расписаний с ограничениями предшествования // Доклады академии наук. 2008. Т.424. № 2. C. 7–9.

5. Burdett O., Kozan E.A Disjunctive Graph Model and Framework for Constructing New Train Schedules // Eur. J. Oper. Res. 2010. V. 200. P. 85–98.

6. Gholami O., Sotskov Y.N. Mixed Graph Model and Algorithms for Parallel‑Machine Job‑shop Scheduling Problems // Int. J. Production Research. 2015. V.8. P. 1–16.

7. Lusby R., Ryan D. Railway Track Allocation: Models and Methods // Oper. Res. Spektrum. 2011. V.33. P.843—883.

8. Осипов С.И, Осипов С.С. Основы тяги поездов. — М.: УМК МПС, 2000. —592 с.

9. Гайнанов Д.Н. Комбинаторная геометрия и графы в анализе несовместных систем и распознавании образов. — М.: Наука, 2014. —152 с.

10. Gainanov D.N., Rasskazova V.A. An inference algorithm for monotone boolean functions associated with undirected graphs. Bulletin SUSU. 2016. V.9. № 3. P.17—30.

Скачать статью