Оптимизация процессов управления движением поездов и содержания инфраструктуры железнодорожного транспорта на основе прогнозных технологий Д.В. Ежов, О.В. Коваленко ФГУП «РФЯЦ-ВНИИЭФ» г.Саров Аннотация. Рассматривается применение методов оптимизации и прогнозных технологий в применении к процессам организации железнодорожных перевозок. Рассматриваются проблемы, связанные с указанными процессами в т.ч. устранение сбойных ситуаций, нарушения графика движения, предлагаются способы и методы их решения. Ключевые слова: имитация, моделирование, прогнозирования, математическая модель, автоматизированная система Railway movement and infrastructure process optimization based on forecast technologies D.V. Ezhov, O.V. Kovalenko RFNC-VNIIEF Abstract. The application of optimization methods and predictive technologies in application to the processes of organization of railway transportation is considered. The problems associated with these processes, including the elimination of faulty situations, violations of the traffic schedule are considered. The ways and methods of their solution are proposed. Keywords: simulation, modeling, forecasting, mathematical model, automated system 1. Описание проблем В быстроизменяющихся условиях хозяйствования, рыночных и нерыночных факторов, растущих требований к скорости перевозок, существующая технология взаимоотношений между всеми участниками перевозочного процесса требует непрерывной адаптации. 167 Недостаточная гибкость и эффективность существующей технологии перевозочного процесса происходит из нескольких объективных причин: − сосредоточенность на локальных задачах; − человеческий фактор при принятии решений в режиме реального времени; − дефицит и/или недоступность каких-либо ресурсов. В настоящее время не удаётся снизить негативное влияние вышеперечисленных факторов, что отражается, в том числе, и на скорости движения грузовых поездов и росту непроизводительных эксплуатационных потерь. Предпринимаемые ранее усилия для улучшения технологии взаимодействия участников перевозочного процесса не привели к желаемому результату. Попытка повысить прогнозируемость и согласованность действий смежных отраслевых хозяйств на различных этапах перевозочного процесса за счёт организации движения грузовых поездов по твёрдым «ниткам» также не дает большого эффекта в связи с отказами технических средств, имеющими стохастический характер. Уменьшить влияние этих отказов на соблюдение графика движения требует наличия резервов пропускной способности железнодорожных участков, а их практически не осталось. 2. Предлагаемый вариант решения проблем Выходом из сложившейся ситуации является создание некоего программного комплекса (супервизора, Автоматизированной Системы, далее АС), позволяющего отслеживать оперативную ситуацию в эксплуатационной работе на всей сети железных дорог РЖД, объединять все сведения обо всех объектах управления и ресурсах, а также объединять работу всех участников перевозочного процесса для выполнения оптимальных действий и операций, вытекающих из решения общей оптимизационной задачи. Соответственно система, способная реализовать подобный комплекс, должна основываться на постоянном оперативном анализе динамической модели сети железных дорог, а её управленческие решения, предлагаемые специалистам, управляющим перевозочным процессом, должны возникать как результат решения оптимальных задач в этой модели. Планируемые результаты работы модели: − формирование в режиме «онлайн» оптимальных с точки зрения использования дефицитных ресурсов решений по составообразованию, подвязке локомотивов и локомотивных бригад, плану формирования и маршрутам следования поездов с учётом загруженности инфраструктуры; − генерация вариантных графиков движения поездов; − прогноз состояния объектов инфраструктуры; 168 − выбор наиболее оптимальных и устойчивых к случайным задержкам вариантов пропуска поездов. В самых общих чертах алгоритм работы системы выглядит следующим образом (рис.1). Рис.1. Координация использования ресурсов в перевозочном процессе В планируемой АС одним из основных заданных условий является безусловный приоритет по использованию ресурсов перевозочного процесса пассажирскими поездами, которые движутся по заранее известному расписанию. Исходя из этого, в первую очередь осуществляется обеспечение продвижения по сети пассажирских поездов. Поэтому если вдруг по какой-то причине в распоряжении конкретной станции нет пассажирских локомотивов, то подходящий локомотив (по заданным правилам отбора) берется из локомотивов грузового движения. Поэтому укрупнено в каждом временном такте алгоритм функционирования системы выглядит следующим образом (рис.2): Рис. 2. Укрупненная блок-схема функционирования АС 169 Подход к оптимизации в предлагаемой АС существенно отличается от тех, которые традиционно применялись в отрасли. Обычно для всех мест возникновения ресурсов (например, для локомотивов – это депо, сортировочные станции и станции смены локомотивов) строятся прогнозы образования ресурсов и прогнозы их потребления (для локомотивов – составы без локомотивов на станциях, готовые к отправлению). Затем происходит оптимизация распределения ресурсов по максимально возможному совмещению времени его появления в конкретно заданных пунктах с временами начала его потребления. Существенным моментом в данном подходе является тот факт, что для уже распределенного ресурса прогноз его последующего высвобождения не строится, что существенно снижает горизонт планирования. АС будет строить совмещенные прогнозы с учетом построения цепочек подвязки ресурсов в пунктах их потребления. Система планирует эксплуатационную работу с некоторым опережением, формируя для этого прогнозы продвижения поездов по участкам и прогнозы появления груженых и порожних вагонов на грузовых станциях. С учетом этих вагонов и наличием составов и вагонов на станциях, системой также строится прогноз составообразования на сортировочных и/или грузовых станциях. Далее решается еще один сложный оптимизационный расчет, согласующий в себе распределение загрузки инфраструктуры за счет отклонения маршрутов проследования грузовых поездов от оптимальных, которые получаются без учета текущей загруженности инфраструктуры. 3. Применяемые алгоритмы оптимизации В виду того, что число возможных состояний дискретной системы увеличивается со временем экспоненциальным образом, применяется эвристический алгоритм, построенный на следующих принципах: 1. Перевозочный процесс состоит из множества разномасштабных подпроцессов. Для адекватного описания системы перевозочного процесса оптимизационно-прогнозная расчётная модель состоит из двух основных проходов от начального момента t0 до конечного момента времени tend. Первый проход служит для определения усреднённых характеристик перевозочного процесса, а второй проход служит для оптимизации мелкомасштабных процессов. 2. Для обрезания ветвления возможных вариантов (ограничения вариационного пространства) во втором проходе используется динамическое программирование. Величина шага по времени ограничивается минимальным временем движения поезда от сортировочной станции до другой сортировочной станции. То есть выбирается промежуток времени, в течение которого не происходит ветвления (появления новых вариантов в процессе расчёта) источников прибывающих вагонов на сортировочные станции с 170 других сортировочных станций в течение текущего временного шага динамического программирования. Это позволяет рассчитывать все сортировочные станции независимо друг от друга в рамках каждого шага по времени. Таким образом, во втором проходе алгоритма временная ось разбивается на временные интервалы динамического программирования. Внутри каждого промежутка времени количество возможных состояний, принимаемых системой, приемлемо для задачи дискретной оптимизации на современных компьютерах. 3. Характерное время шага динамического программирования второго прохода разбивает реальные процессы перевозок на два множества: первое - с характерными временами больше, чем шаг динамического программирования, второе – с характерными временами меньше, чем шаг динамического программирования. 3.1 Для определения характеристик процессов с характерными временами большими шага динамического программирования используется первый проход, в котором характеристики процессов с временами меньшими, чем шаг динамического программирования, учитываются интегрально. Первая категория процессов определяет объемные показатели планирования и цели для календарных показателей планирования. 3.2 Для определения характеристик процессов с характерными временами меньшими, чем шаг динамического программирования используется второй проход. При этом насчитанные характеристики процессов с большими характерными временами во втором проходе выступают неизменными и неподлежащими вариации. То есть, во втором проходе производится ранее насчитанная имитация (имитационное моделирование) процессов с характерными временами большими, чем шаг динамического программирования. Как правило, такие процессы определяют цели для объектов рассматриваемой динамической системы перевозочного процесса, которые формируют процессы с меньшими характерными временами. Вторая категория процессов определяет календарные показатели планирования и конкретные шаги, подлежащие исполнению диспетчерами и линейными работниками. 4. Для возможного внедрения предлагаемого алгоритма в существующую технологию перевозочного процесса, многие характеристики процессов с большими характерными временами берутся из текущей нормативной документации. К таковым относятся характеристики: плана формирования, нормативный график движения, план ремонтных работ инфраструктуры (плановые «окна»), график движения пассажирских поездов, среднее количество локомотивов и локомотивных бригад, необходимое на каждой из дорог (или 171 полигонах) и др. В принципе, в первом проходе эти показатели могут быть рассчитаны при решении оптимизационных задач, и далее насчитанные показатели должны использоваться во втором проходе. Так как не все характеристики объёмных показателей планирования определяются из нормативных документов, и их также необходимо подвергать перерасчету, то первый проход алгоритма не может быть исключен. 5. В качестве математического аппарата оптимизации и моделирования в первом и втором подходе выбраны метаэвристические популяционные алгоритмы оптимизации с полной имитацией каждого экземпляр а популяции (отражающего определенную ветвь ветвления возможных процессов). При имитации по конкретным сценариям используются принципы мультиагентного моделирования. 6. В качестве оптимизационного функционала принята полная стоимость всех технологических цепочек, обеспечивающих перевозочный процесс. Стоимость подлежит минимизации. Оптимизационная задача во втором проходе решается внутри каждого шага по времени. 7. Во время второго прохода алгоритма концы временных шагов могут «рвать» мелкомасштабные технологические цепочки. Поэтому, все незавершенные на предыдущем шаге технологические цепочки перевозочного процесса на последующем шаге динамического программирования должны быть пересчитаны. В этом смысле временные интервалы динамического программирования T1,…,Tn-1,Tn,… должны пересекаться. Выбрано следующее правило наложения временных интервалов. Пусть все временные интервалы алгоритма имею одинаковую продолжительность. n-й интервал первой своей половиной пересекается с n-1 –м, второй половиной с n+1 –м интервалом. То есть n-1 –й интервал и n+1 интервал образуют непрерывный отрезок, поверх которого накладывается n-й интервал. Из вышесказанного алгоритм можно представить иерархической структурой, на нулевом уровне которой находится пять линейно соединённых крупных блоков алгоритмов первого уровня (рис. 3). 172 Алгоритм работы на нулевом уровне Занятие путевой инфраструктуры утвержденными окнами, расстановка предупреждений Занятие путевой инфраструктуры расписанием пассажирских поездов и поездов с твердыми нитками графика Алгоритм восстановления поездной обстановки, состояний локомотивов и локомотивных бригад на начальный момент времени оптимизационного моделирования из данных информационных систем ОАО «РЖД» Первый проход от t0 до tend для определения оптимальных характеристик крупномасштабных по времени процессов, определяющих перевозочный процесс. Второй проход от t0 до tend для определения оптимальных характеристик мелкомасштабных по времени процессов, определяющих перевозочный процесс. Рис. 3. Алгоритм нулевого уровня 4. Выводы Данные принципы и алгоритмы были реализованы при создании системы АС «ИнфраПрогноз». Система была принята в опытную эксплуатацию. Где созданные алгоритмы показали свою работоспособность. По решению расширенного заседания секции «Информационные технологии на железнодорожном транспорте» НТС ОАО «РЖД» 8 апреля 2016 года было признано дублирование функционала систем ИСУЖТ и АС «ИнфраПрогноз». На основании этого заключения дальнейшая разработка АС «ИнфраПрогноз» была прекращена. После прошествии нескольких лет нам становится очевидным ошибочность этого решения. АС «ИнфраПрогноз» не только составил конкуренцию более дорогому проекту ИСУЖТ, но требовал изменения технологии пропуска поездов. Если бы система АС «ИнфраПрогноз» реально заработала на всей сети (или на её полигоне), все службы должны были бы выполнять её предписания, то есть работать не по своим частным показателям эффективности, а по показателю, который был заложен в АС «ИнфраПрогноз». Это кардинально «ломало» привычный ход вещей. Современные технологии и использующиеся в настоящее время в РЖД информационно-справочные системы позволяют создать АС для поддержки принятия решений в рамках оптимизации перевозочного процесса. Предложенный алгоритм показал свою работоспособность и может адаптивно изменять планы в ходе перевозочного процесса для всех служб 173 перевозочного процесса. Кроме того, в созданной АС «ИнфраПрогноз» использовались алгоритмы метаэвристической оптимизации, которые показали не только свою работоспособность, но и хорошие технические показатели. Литература 1. P. Tormos et al. A Genetic Algorithm for Railway Scheduling Problems – URL: http://www.springerlink.com 2. Ralf Borndörfer at al. Handbook of Optimization in the Railway Industry – URL: http://www.springer.com/series/6161 3. Caprara A, Fischetti M, Toth P. A heuristic method for the set covering problem. – URL: https://doi.org/10.1287/opre.47.5.730 4. Charnes A, Miller MH. A model for the optimal programming of railway freight train movements. – URL: https://doi.org/10.1287/mnsc.3.1.74 5. M. Carey and D. Lockwood. A model, algorithms and strategy for train pathing // The Journal of the Operational Research Society, 46(8):988–1005, 1995 6. Frank Geraets, Leo Kroon, Anita Schoebel, Dorothea Wagner, Christos D. Zaroliagis. Algorithmic Methods for Railway Optimization // International Dagstuhl Workshop Dagstuhl Castle, Germany, June 20-25, 2004 7. Wang Zhuo1, Jia Li-min. The Theory And Method Of Design And Optimization For Railway Intelligent Transportation Systems // School of Traffic and Transportation, Beijing Jiaotong University, Beijing, China, 2011 8. Yihui Wang, Bin Ning, Ton van den Boom, Bart De Schutter. Optimal Trajectory Planning and Train Scheduling for Urban Rail Transit System // Springer International Publishing Switzerland, 2016 174