УДК 656.42:656.25-52:656.22.05

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

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

МЕТРОПОЛИТЕН, ПЛАНОВЫЙ ГРАФИК ДВИЖЕНИЯ ПОЕЗДОВ, КРИТЕРИИ РАВНОМЕРНОСТИ, АВТОМАТИЗИРОВАННОЕ ПОСТОЕНИЕ, УРОВНИ РАВНОМЕРНОСТИ

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

Methodology of the underground train planned schedule automated construction
Safronov A.I., Sidorenko V.G.

UNDERGROUND, TRAIN PLANNED SCHEDULE, UNIFORMITY CRITERIA, AUTOMATED CONSTRUCTION, UNIFORMITY LEVELS

In article processes of the underground train planned schedule automated construction and the features of lines influencing these processes are considered. Problem statement is formulated, optimality criteria are formalized, uniformity levels are allocated.

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

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

В работе рассмотрим два критерия равномерности:

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

Автоматизированное построение ПГД распадается на ряд частных задач, в каждой из которых для определения оптимального решения используется только один из рассматриваемых критериев.

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

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

С учетом выбранного способа формализации критерий равномерности интервалов по отправлению поездов со станций RI определяется следующим образом:



где ni - i-я «нитка» графика, i = 1, 2, ..., Np;
Np - количество учитываемых «ниток», которое на единицу больше максимального количества составов на линии в рассматриваемый промежуток времени;
n1 - первая в рассматриваемой последовательности «нитка»;
nNp - последняя в рассматриваемой последовательности «нитка»; это «нитка», по которой будет двигаться маршрут «нитки» n1 после совершения полного оборота. Для радиальной линии это «нитка» n1.nnn.nnn , где n.nnn – компонент последовательности «нитка» n – следующая «нитка» к «нитке» n, то есть «нитка», по которой маршрут будет двигаться после окончания движения по «нитке» n (после оборота). Для кольцевой линии это «нитка» n1.nnn;
Ns - количество станций на линии;
Me(Ss) - элемент массива элементов расписания, начинающийся на станции Ss;
Me(Ss).totpr - время отправления со станции Ss;
fNPS(ni,k,Ss,True) - операция, в результате выполнения которой определяется k-й следующий поезд (в формуле (1) k=1) после «нитки» ni по отправлению со станции Ss.

Приведённая числовая характеристика достигает своего минимума при равномерном расположении всех рассматриваемых «ниток» на всех станциях. Введенный критерий аналогичен критериям, сформулированным в [2, 3].

Критерий равномерности расположения вводимых/снимаемых составов, RN формализуется следующим образом:



где Mвв(сн) - множество вводимых/снимаемых составов, которое включает в себя «нитки», которые выбираются из последовательности «ниток», определенной для вычисления критерия равномерности интервалов по отправлению поездов со станций RI, по признаку отсутствия предыдущей «нитки» при вводе составов или следующей «нитки» при снятии составов;
Nвв(сн) - количество «ниток» множества Mвв(сн);
ni.npn - компонент последовательности «нитка» n - предыдущая «нитка» к «нитке» n, то есть «нитка», по которой маршрут двигался до начала движения по «нитке» n (до оборота).
FCN (nu, nw) - операция , в результате выполнения которой определяется количество «ниток» между двумя заданными nu, nw.

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

Решению задач автоматизированного построения ПГД посвящено значительное число работ, основными среди которых являются [1, 3-5]. Для каждой линии метрополитена строится свой ПГД. На вид графиков влияют особенности линий (рис. 1). Рассмотрим различные признаки линий метрополитена. Под географией линии будем понимать конструктивное расположение линии в пространстве. По этому признаку линии делятся на радиальные и кольцевые. Последовательно рассмотрим ряд особенностей этих линий. Порядка 93% «ниток» графика кольцевой линии метрополитена соответствует движению поездов по одному пути. Переход с одного пути на другой реализуется в настоящее время достаточно редко: только в связи с необходимостью организации расположения поездов, соответствующего последовательности ночной расстановки составов. Отсюда можно сделать вывод, что на значительном временном интервале первый и второй пути рассматриваются как независимые [6].



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

Способ построения ПГД радиальных линий с оборотом по конечным станциям (традиционный способ) изложен в [1, 3]. Вместе с тем, оборот составов по промежуточным станциям необходимо реализовывать в случае нехватки ресурсов линии (пропускной способности конечных станций, единиц электроподвижного состава) для реализации заданной парности движения на всем протяжении линии или в связи с резким изменением пассажиропотока на протяжении линии, что соответствует организации зонного движения. Построение графиков зонного движения (ГЗТ) изложено в [7].

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

Способ построения графика зависит от расположения и количества депо на линии. На коротких линиях, как правило, имеется одно депо. Существенен при построении графика как кольцевой, так и радиальной линии выбор пути, на который выходят составы из депо. В связи с этим, для линий с одним физическим депо, выдающим составы на разные пути, авторами введено понятие «виртуального» депо, дополняющего на графике физическое [6]. На длинных линиях предусматриваются два депо, за каждым из которых закреплены составы. Два депо, как правило, располагаются на одной линии, но имеются случаи, когда одно из двух депо находится на другой линии, а обслуживает данную.

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

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

Исторически сложилось, что создание алгоритмов автоматизированного построения ПГД начиналась с разработок для радиальных линий, рассматриваемых как кольцевые [4]. В дальнейших работах рассматривалось решение частных задач. В связи с этим, учёт особенностей автоматизированного построения для радиальных линий требует своего развития. Актуальным является обобщение всего накопленного опыта в рамках единого подхода к построению ПГД.

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

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

В соответствии с технологией работы метрополитена ПГД в рабочие дни описывает следующие процессы:

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

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

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

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

Подробно каждый из процессов будет рассмотрен позже.

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



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

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



Наличие зеркальной симметрии позволяет рассматривать лишь отдельно взятый процесс, а построение симметричного ему процесса проводить аналогично, используя зеркальные операции.

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

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

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

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

- число снимаемых составов для каждого из главных путей определяется в отдельности;
- оптимальные по критерию равномерности расположения вводимых/снимаемых составов варианты снятия составов и назначения маршрутов на «нитки» определяются в зависимости от заданных графиком оборота подвижного состава ремонтов и осмотров;
- рассогласования межпоездных интервалов устраняются согласно критерию равномерности интервалов по отправлению поездов со станций (на каждой станции линии для текущей «нитки» рассчитывается «расстояние по времени» до соседних «ниток» справа и слева, затем полученное рассогласование компенсируется путём ввода сверхрежимной выдержки на рассматриваемой станции) [2, 11].

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

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

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

Процесс ухода на ночную расстановку строится в прямом времени, при этом для обеспечения правильного расположения составов у указателей ночной расстановки проводятся следующие операции [8]:

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

Согласно выбранным критериям, признаком качества построения ПГД является равномерность, которая имеет несколько аспектов рассмотрения (рис. 4):

- равномерность интервалов по отправлению поездов со станций;
- равномерность ввода/снятия составов за время полного оборота состава на линии по каждому из путей;
- равномерность ввода/снятия составов за время полного оборота состава на линии в целом;
- равномерность ввода/снятия составов за время, равное нескольким полным оборотам состава на линии в целом.

Каждый следующий аспект равномерности является «внешним», то есть более общим по отношению к предыдущему.

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

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

В общем случае, процесс равномерного снятия составов может быть описан следующим алгоритмом:

1. Из всего множества M составов на линии выбирается множество равномерно расположенных составов Mсум, количество элементов множества Мсум равно суммарному количеству снимаемых составов за весь переходный процесс.
2. При выполнении i-го снятия из множества равномерно расположенных составов Mсум выбираются Мвв(сн)i равномерно расположенных составов, подлежащих снятию.
3. Если снятие производится по двум путям, то из множества Мвв(сн)i выбираются равномерно расположенные составы, подлежащие снятию по каждому из главных путей в заданном пользователем количестве.
4. После выполнения снятия из множества Мсум исключаются элементы множества Mi: Мсум \ Мвв(сн)i = Мсум ∩ НЕ(Мвв(сн)i).
5. Если выполнены не все снятия, то происходит переход к пункту 2.
6. Если все снятия выполнены, выполняется выравнивание межпоездных интервалов по критерию равномерности интервалов по отправлению поездов со станций RI.



В основе выбора равномерно расположенных вводимых/снимаемых составов лежит алгоритм поиска наибольшего общего делителя (НОД) двух чисел, базирующийся на алгоритме деления Евклида [12-14]. В качестве этих чисел в рассматриваемом случае принимаются количество составов в исходном установившемся процессе и количество составов, заданное для следующего установившегося процесса.

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

Согласно изложенным выше принципам авторами были разработаны алгоритмы построения ПГД для линий разной географии. Они реализованы в автоматизированной системе построения планового графика движения пассажирских поездов метрополитена (АСП ПГД ППМ).

Литература

1. Сидоренко В.Г. Автоматизация построения планового графика движения поездов метрополитена // Автоматизация и современные технологии, 2003, №2. – С. 6–10.
2. Сеславин А.И., Воробьева Л.Н. Градиентный способ централизованного управления городскими транспортными системами. - М.: Наука и техника транспорта, № 4, 2004.
3. Василенко М.Н., Дегтярев Д.П., Максименко О.А. Проблемы визуального анализа графика движения поездов на метрополитене и методы их решения // Неделя науки-2002. СПб.: ПГУПС, 2002.
4. Баранов Л.А., Жербина А.И. Построение на ЭВМ графиков движения поездов метрополитена // Вестник ВНИИЖТа, 1981, №2. - С. 17-20.
5. Феофилов А.Н. Математическая модель составления графиков движения поездов на линиях метрополитена // Вестник ВНИИЖТ. 1991, № 7. - С. 10-13.
6. Сидоренко В.Г., Сафронов А.И. Применение критерия равномерности в больших транспортных системах // Проблемы управления безопасностью сложных систем: Труды XVII Международной конференции. - С. 289-292.
7. Сидоренко В.Г., Новикова М.В. Синтез планового графика движения зонного типа // Мир транспорта. 2009, № 4. - С. 128-134.
8. Сидоренко В.Г., Пискунов А.С. Процедуры организации ночной расстановки составов на линии метрополитена // ВЕСТНИК МИИТа // Научно-технический журнал. М.: МИИТ. 2008, вып. 18. - С. 3-7.
9. Сидоренко В.Г., Сафронов А.И. Синтез сценариев построения планового графика движения пассажирских поездов Кольцевой линии метрополитена // Проблемы регионального и муниципального управления. Сборник докладов международной научной конференции Москва, 21 апреля 2010 г. - С. 166-170.
10. Сидоренко В.Г., Власова И.А., Рындина Е.Ю. Подсистема автоматизированного построения выхода составов метрополитена из расстановки на ночь // Труды научно-практической конференции «Неделя науки-2008. Наука МИИТа транспорту». М.: МИИТ. 2008. - C. VII-38.
11. Сидоренко В.Г., Рындина Е.Ю. Методы выравнивания интервалов движения поездов метрополитена // ВЕСТНИК МИИТа // Научно-технический журнал. М.: МИИТ. 2008, вып. 18. - С. 8-10.
12. Концевич М.Л. Равномерные расположения // Квант. 1987, № 7. - С. 51-52, 59.
13. Виноградов И.М. Основы теории чисел. М.: Наука. 1972.
14. Сеславин А.И., Сеславина Е.А. Принципы равномерности в задачах управления потоками пассажирского транспорта // Прикладная информатика. 2009, № 2(20). С. 91-95.

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

Сафронов, А. И. Построение планового графика движения для метрополитена / А. И. Сафронов, В. Г. Сидоренко // Мир транспорта. - 2011. - № 3. - С. 98-105.

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

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

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