Сафронов А.И., Сидоренко В.Г.

Автоматизированное построение планового графика движения пассажирских поездов метрополитена

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

Процесс составления планового графика движения пассажирских поездов по линии метрополитена (ПГД) – одна из таких задач. В ходе её решения необходимо учитывать многочисленные ограничения. Все эти ограничения, так или иначе, должны быть представлены в постановке задачи.

В статье [1] авторами была сформулирована постановка задачи автоматизированного построения ПГД в общем виде и записана следующим образом: разработать алгоритмы, согласно которым, в результате конечного числа ответов пользователя на общие вопросы (с вариантами ответов «Да/Нет») с промежуточным вводом исходных данных будет построен ПГД при учёте специфических параметров и ограничений, в первую очередь, определяемых графиком оборота подвижного состава (ГО), который регулирует проведение осмотров и ремонтов подвижного состава, и графиком работы локомотивных бригад. Построенный ПГД должен отвечать поставленным целям управления, быть рациональным с точки зрения выбранных критериев и устойчивым к возмущающим факторам.

Алгоритмы автоматизированного построения ПГД представляют собой сценарии управления объектами линии метрополитена. Эти алгоритмы реализуют рациональные управляющие воздействия для каждого из процессов ПГД.

Управляющими воздействиями являются императивы и логико-трансформационные правила (ЛТП) построения ПГД [2]. Определение объектов, к которым они применяются, и построение логики их выполнения проводится на базе предварительного расчета. В ходе расчёта используются введенные пользователем данные, проводится оценка графика по выбранным критериям, учитываются действующие ограничения.

К целям управления относятся:

- реализация заданной (изменяющейся во времени) парности движения в течение всего времени движения пассажирских поездов;
- правильность ночной расстановки (все маршруты должны завершить свое движение в той точке ночной расстановки, из которой на следующий день начинается движение следующего маршрута);
- реализация ГО.

Методика автоматизированного построения ПГД заключается в выделении процессов, происходящих на линии, и сопоставлении им фрагментов ПГД. Происходящие на линии процессы делятся на переходные и установившиеся. Установившимся процессом будем называть процесс, при котором число пар поездов в час (парность) остается постоянным в течение времени, большего, чем время полного оборота состава. Наибольшую сложность представляет переход от одного установившегося процесса к другому, и этот переход будем называть переходным процессом [2]. Переходный процесс должен быть построен таким образом, чтобы к заданному моменту времени создать все условия для работы в установившемся процессе. В соответствии с технологией работы метрополитена и изменением пассажиропотока в течение суток имеется определённая последовательность установившихся и переходных процессов. ПГД в рабочие дни описывает следующие процессы:

1. Выход составов из ночной расстановки (переходный процесс).
2. Движение поездов с заданной парностью в утренний час «пик» (установившийся процесс).
3. Движение поездов между утренним часом «пик» и движением в час «непик» (переходный процесс).
4. Движение в час «непик» (установившийся процесс).
5. Организация перехода к вечернему часу «пик» (переходный процесс).
6. Движение поездов с заданной парностью в вечерний час «пик» (установившийся процесс).
7. Переход от вечернего часа «пик» к непиковому движению (переходный процесс).
8. Организация перехода от непикового движения к ночной расстановке (переходный процесс).

В ряде случаев возможно изменение последовательности процессов в зависимости от проводимых в городе мероприятий. В выходные дни процессы 3-7 отсутствуют, так как в течение всего дня поддерживается постоянная парность движения. Сразу отметим, что все процессы, происходящие на линии, имеют свои характерные особенности [1].

Авторами предложено оценивать достижение поставленных целей управления при помощи условий реализации. Под условиями реализации понимается апостериорная информация, получаемая по итогам построения переходного/установившегося процесса путём проверки графика после завершения рассматриваемого процесса. Условия реализации позволяют определить, удалось ли построить процесс при заданных начальных условиях. В этом случае, термин «условия реализации» употребляется применительно к построению отдельных процессов ПГД, а термин «условия успешной реализации» – применительно к ПГД, составленному на весь день.

Опыт эксплуатации линий Московского метрополитена показал, что использование предельных, с точки зрения безопасности движения, значений парности движения может привести к частому возникновению сбоев в движении поездов. Это, как правило, связано с воздействием такого возмущающего фактора, как задержка поезда пассажирами. В связи с этим, принятие решений о реализации предельных значений парности движения, должно подкрепляться предварительным проведением имитационных экспериментов [3].

Ограничения, накладываемые на ПГД, обусловлены общими и технологическими требованиями обеспечения безопасности движения поездов, а также связями между объектами линии. К ним относятся:

- порядок заполнения точек ночной расстановки составов на линии;
- возможность проведения регулировочных действий на станциях с путевым развитием;
- частота ввода и снятия составов на промежуточных станциях в соответствии с правилами обслуживания пассажиров;
- правила функционирования станций с путевым развитием;
- время окончания движения;
- время отправления последних пассажирских поездов с начальных станций путей;
- организация движения последних пассажирских поездов [4].

Эти ограничения являются общими для всего ПГД. Одновременно для каждого процесса ПГД выделяются частные ограничения, которые авторами классифицируются как условия реализуемости. Условия реализуемости - это априорная информация, которая позволяет заранее определить, удастся ли с заданными начальными условиями построить процесс.

Авторы предлагают проводить сравнение вариантов построения ПГД по следующим критериям равномерности:

- критерий равномерности интервалов по отправлению поездов со станций;
- критерий равномерности расположения вводимых/снимаемых составов [1].

Кроме этих основных критериев, которые учитываются во всех процессах ПГД, можно выделить и дополнительные. Дополнительные критерии, в первую очередь, учитываются при выборе способа организации ночной расстановки составов:

- количество регулировочных отстоев на станционных путях линии;
- количество регулировочных отстоев в депо;
- длительность регулировочных отстоев на станционных путях линии;
- длительность регулировочных отстоев в депо;
- время начала проведения регулировочных отстоев в депо – нерационально их проведение во время движения с максимальной парностью и во время снятия напряжения с контактного рельса на соединительных ветках между депо и линией;
- время начала и окончания проведения регулировочных отстоев на линии – нерационально их проведение во время движения с максимальной парностью, а также до утреннего часа «пик» и после вечернего часа «пик» (это связано с графиком работы ремонтных бригад);
- отклонение от заданного ГО.

Выполнение дополнительных регулировочных действий, например, в процессе равномерного ввода или снятия составов, может внести неравномерность.

Поставленным целям управления может отвечать большое количество вариантов построения ПГД. Поэтому актуальной является задача ускорения перебора вариантов. Для сокращения количества рассматриваемых вариантов используются следующие подходы:

- проверка условий реализуемости ПГД;
- организация многоуровневой структуры равномерности ПГД.

В соответствии с первым механизмом, параметры и промежуточные расчётные данные каждого рассматриваемого варианта построения (до попытки его реализации) проверяются на соответствие ряду условий реализуемости. Невыполнение хотя бы одного из этих условий для рассматриваемого варианта даёт возможность сделать вывод о том, что построить ПГД не возможно, в связи с чем, вариант полностью исключается из рассмотрения.

Созданная авторами процедура автоматизированного построения ПГД и предложенная многоуровневая структура равномерности ПГД позволяют не только просматривать множество вариантов построения ПГД без изменения исходных данных, но и проводить варьирование исходных данных, не противоречащее целям управления [1].

Таким образом, можно выделить несколько уровней сокращения количества рассматриваемых вариантов построения ПГД:

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

Выполним оценку максимального количества вариантов реализации переходных процессов.

В общем виде максимальное количество вариантов ввода составов за переходный процесс max[Gвв] можно определить из следующего соотношения:



где M[i, j] - количество составов, которые должны быть на j-м пути линии к началу рассматриваемого интервала времени (процесса построения ПГД) с порядковым номером i.
M[i+1, j] количество составов, которые должны быть на j-м пути линии к началу следующего к рассматриваемому интервалу времени.
НОД(M[i+1, j], M[i+1, j] - M[i, j]) - наибольший общий делитель, определяемый между и изменением числа составов между двумя соседними часами.
i - номер рассматриваемого интервала времени;
j - путь линии, j = 1, 2.
I - количество итераций, необходимых для построения переходного процесса ПГД при переходе от одного стационарного процесса к другому. Значение количества итераций определяется:



tн[с.п.2] - время начала второго стационарного процесса (справа);
tк[с.п.1] - время конца первого стационарного процесса (слева);
Тпо - время полного оборота состава на линии.

В том случае, когда НОД(M[i+1, j], M[i+1, j] - M[i, j]) > 1, количество возможных вариантов значительно сокращается.

Максимальное количество вариантов снятия составов за переходный процесс можно определить из соотношения, зеркально симметричного приведённому ранее [1]:



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

Максимальное количество вариантов снятия составов за переходный процесс с учетом возможных вариантов назначения маршрутов определятся из соотношения:



где Nijkl - количество элементов множества маршрутов, которые могут быть назначены на l-ю снимаемую нитку при выполнении k-го варианта i-го снятия по j-му пути;
x[i, j] - количество вариантов реализации i-го снятия по j-му пути, вычисляемое по формуле:



На значение оказывает сильное влияние реализованный ранее вариант выхода из ночной расстановки.

Вариативность реализации выхода составов из ночной расстановки связана с тем, что допустимы различные последовательности выпуска составов из точек ночной расстановки, находящихся на станционных путях линии, на главные пути линии. Возможные варианты выхода составов от точек ночной расстановки задаются в качестве исходных данных [4].



На схеме (рис. 1) изображены процессы сокращения и увеличения вариантов построения ПГД. Стрелками, направленными вверх, отмечен рост числа вариантов, а стрелками, направленными по диагонали вниз вдоль ступеней, отмечено сокращение вариантов в процессе расчёта. Цифрами на схеме отмечен порядок проведения расчёта.

Рассмотрим этот расчёт подробнее. Автоматизированное построение ПГД начинается с создания равномерной сетки процесса утреннего часа «пик», далее следует переход к процессу ввода составов на утренний час «пик», сопровождающийся «лавинным» скачком количества вариантов построения (1), при этом, не каждый вариант может быть реализован и происходит последовательное исключение вариантов. При переходе к процессу выхода составов из ночной расстановки снова происходит скачкообразное увеличение числа вариантов построения (2). Рост числа вариантов происходит при переходе от утреннего часа «пик» к дневному часу «непик» (3), но число этих вариантов ограничиваются построением процесса выхода составов из ночной расстановки.

Аналогично рассматривается и вечерняя часть графика, где построение начинается с вечернего часа «пик» и сопровождается скачком количества вариантов построения при вводе составов на вечерний час «пик» (4). «Лавинный» скачок числа возможных вариантов происходит при переходе к построению процесса снятия составов к вечернему часу «непик» (5), а также после него при переходе к организации ночной расстановки составов(6).

Таким образом, число вариантов построения ПГД является не монотонной функцией от процесса и его состояния. Под состоянием процесса следует понимать степень его завершённости – начало или конец.



На схеме (рис. 2) изображён перебор вариантов построения ПГД. Стрелочками обозначены переходы между соседними вариантами построения процессов ПГД. Кругами на схеме обозначены наборы снимаемых или вводимых составов, квадратами – наборы маршрутов, назначаемых на «нитки» графика, треугольниками – наборы последовательностей заполнения точек ночной расстановки.

Авторами разработаны алгоритмы автоматизированного построения ПГД для ряда линий Московского метрополитена. В данной работе основное внимание уделено построению ПГД Кольцевой линии.

В таблице 1 представлены результаты проведенного авторами исследования характера изменения количества вариантов при построении отдельных процессов ПГД. Для оценки качества работы алгоритма необходимо детально рассматривать только переходные процессы, так как установившиеся процессы часов «пик» и «непик» имеют только один вариант построения.



Расчет числа потенциально возможных вариантов реализации следующих переходных процессов (вход в утренний час «пик», выход из утреннего часа «пик», вход в вечерний час «пик», выход из вечернего часа «пик») проводился только для частных случаев построения ПГД. Полученное число реализованных вариантов связано с успешной работой алгоритмов ускоренного перебора вариантов, учитывающих ограничения на построение ПГД.

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

Таким образом, процедура автоматизированного построения ПГД, содержащая в своём составе аппарат перебора вариантов, позволяет существенно сократить время на поиск и построение рационального ПГД. Эта процедура реализована в автоматизированной системе построения планового графика движения пассажирских поездов метрополитена (АСП ПГД ППМ), созданной на кафедре «Управление и информатика в технических системах» МИИТа и внедренной на Московском метрополитене [2].

Литература:

1. Сидоренко В.Г., Сафронов А.И. Построение планового графика движения для метрополитена // Мир транспорта. 2011, № 3. - С. 98-105.
2. Сидоренко В.Г. Автоматизация построения планового графика движения поездов метрополитена // Автоматизация и современные технологии, 2003, №2. С. 6–10.
3. Баранов Л.А., Сидоренко В.Г. Тренажер поездных диспетчеров линий Московского метрополитена // Железные дороги мира, 2002, №8. С. 64-69.
4. Пискунов А.С., Сидоренко В.Г. Процедуры организации ночной расстановки составов на линии метрополитена // ВЕСТНИК МИИТа // Научно-технический журнал. М.: МИИТ. 2008, вып. 18. - С. 3-7.

Библиографическая ссылка:

Сафронов, А. И. Автоматизированное построение планового графика движения пассажирских поездов метрополитена / А. И. Сафронов, В. Г. Сидоренко // Вестник Ростовского государственного университета путей сообщения (РГУПС). - 2012. - № 3. - С. 99-104.

Ссылка на elibrary.ru:

https://www.elibrary.ru/item.asp?id=17928789

Вложение: 13420164_elibrary.pdf