Алгоритмическое и программное обеспечение для назначения локомотивов с целью перевозки грузовых составов

Предлагается математическая модель назначения локомотивов для перевозки грузовых составов. Целью оптимизации в модели является минимизация числа задействованных для перевозки составов локомотивов за счёт выбора маршрутов составов и локомотивов. Предполагается, что составы могут перевозиться в определённые промежутки времени, которые называются нитками, для каждого локомотива установлены допустимые варианты передвижения, называемые плечами. Учитывается необходимость периодического проведения технического осмотра локомотивов. Для формулировки задачи используется аппарат теории графов и целочисленной оптимизации. Формализуются железнодорожные понятия плеча, нитки, рейса состава и маршрута оборота локомотива. Предлагается эвристический алгоритм поиска приближённого решения задачи. Основной идеей предлагаемого алгоритма является максимальное использование локомотивов с ранним началом движения. Алгоритм состоит из трех этапов, на каждом из которых улучшается предыдущее найденное решение. Улучшение решения осуществляется за счет перегонок локомотивов. Приводится описание разработанных программных средств для оптимизации данной модели. Проведены численные эксперименты на примере исторических данных Московской железной дороги.

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

теория графов; целочисленная оптимизация; назначение локомотивов.

Литература

1. Белый, О.В. Организация грузовых железнодорожных перевозок: пути оптимизации / О.В. Белый, И.М. Кокурин // Транспорт Российской Федерации. - 2011. - № 4 (35). - С. 28-30.
2. Кибзун, А.И. Двухуровневая задача оптимизации деятельности железнодорожного транспортного узла / А.И. Кибзун, А.В. Наумов, С.В. Иванов // Управление большими системами. - 2012. - № 38. - С. 140-160.
3. Лазарев, А.А. Целочисленные постановки задачи формирования железнодорожных составов и расписания их движения / А.А. Лазарев, Е.Г. Мусатова // Управление большими системами. - 2012. - № 38. - С. 161-169.
4. Теория расписаний. Задачи железнодорожного планирования / А.А. Лазарев, Е.Г. Мусатова, Е.Р. Гафаров, А.Г. Кварацхелия. - М.: ИПУ РАН, 2012.
5. Экономика железнодорожного транспорта / Н.П. Терешина, В.Г. Галабурда, М.Ф. Трихунков и др. - М.: УМЦ ЖДТ, 2006.
6. Шапкин, И.Н. Организация железнодорожных перевозок на основе информационных технологий / И.Н. Шапкин. - М.: Учебно-методический центр по образованию на железнодорожном транспорте, 2011.
7. Модель оптимального назначения локомотивов при формировании грузовых составов / Д.Н. Гайнанов, С.В. Иванов, А.И. Кибзун, А.В. Осокин // Труды четвертой научно-технической конференции 'Интеллектуальные системы управления на железнодорожном транспорте'. - М.: НИИАС, 2015. - С. 45-47.
8. Floyd, R.W. Algorithm 97 - Shortes Path / R.W. Floyd // Communications of the ACM. - 1962. - V. 5, № 6. - P. 345.