Аунг Лвин Лвин (АУМ-611), Сафронов А.И. (аспирант)

ОРГАНИЗАЦИЯ ПЕЧАТИ И АНАЛИЗ ГРАФИКА ОБОРОТА ПОДВИЖНОГО СОСТАВА В АВТОМАТИЗИРОВАННОЙ СИСТЕМЕ ПОСТРОЕНИЯ ПЛАНОВОГО ГРАФИКА ДВИЖЕНИЯ ПАССАЖИРСКИХ ПОЕЗДОВ МЕТРОПОЛИТЕНА

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

В данной работе рассмотрены вопросы автоматизированного анализа и печати ГО на соответствие накладываемым ограничениям.

Проверка соответствия ГО ограничениям осуществляется по следующим критериям:

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

Авторами было разработано программное обеспечение, реализующее анализ ГО по приведённым выше критериям.
Задача анализа ГО не может быть решена без предварительного составления ПГД и соответствующего ему ГО. Составление ГО приводит к рассмотрению задачи печати его на бумажном носителе.

В состав автоматизированной системы построения планового графика движения пассажирских поездов метрополитена (АСП ПГД ППМ) входит модуль печати ГО на листе альбомной ориентации. Эти правила установлены заказчиком. В ходе бурного развития новой, Люблинско-Дмитровской линии Московского метрополитена, единственное, на сегодняшний день, электродепо Печатники стало содержать в себе большое количество составов. Таким образом, число соответствующих элементов перестало умещаться на листе формата, предусмотренного заказчиком. В работе предложены два пути решения проблемы:

- размещение ГО на нескольких листах альбомной ориентации;
- организация печати ГО на листе книжной ориентации.

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

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

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

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

Сафронов, А. И. Организация печати и анализ графика оборота подвижного состава в автоматизированной системе построения планового графика движения пассажирских поездов метрополитена / А. И. Сафронов, Аунг Лвин Лвин // Труды научно-практической конференции «Неделя науки-2012. Наука транспорту». - М.: МИИТ. - 2012. - C. III-99-III-100.

ИНТЕЛЛЕКТУАЛЬНАЯ АВТОМАТИЗИРОВАННАЯ СИСТЕМА ПЛАНИРОВАНИЯ ПЕРЕВОЗОЧНОГО ПРОЦЕССА НА МЕТРОПОЛИТЕНЕ

Сафронов А.И., Сидоренко В.Г., Филипченко К.М.

На сегодняшний день разветвлённая сеть Московского метрополитена претерпевает колоссальные перегрузки. Это связано с величиной пассажиропотока, который приходится ежедневно обслуживать. Метрополитен работает на пределе своих технических и человеческих возможностей и, вместе с этим, продолжает активно развиваться, наращивая протяжённость существующих и обрастая новыми линиями.

Принятая на период с 2012 по 2020 годы стратегия развития Московского метрополитена своей основной целью ставит увеличение численности станций на 67 объектов и протяжённости линий на 145 километров, что в среднем соответствует ежегодному приросту 7 станций и 16 километров перегонных тоннелей [1]. В этих условиях уже через пару лет человеческий ресурс начнёт давать сбои не только на эксплуатационно-техническом уровне, но и на уровне планирования перевозочного процесса. И это связано с тем, что не будет оставаться времени на адаптацию и привыкание к одним условиям работы линии, как они преобразуются в иные. Решить эту проблему поможет только создание интеллектуальных систем управления перевозочным процессом на метрополитене.

Средства планирования перевозочного процесса на метрополитене являются составной частью автоматизированной системы управления перевозочным процессом метрополитена (АСУ ППМ), которая реализуется в рамках концепции создания интегрированной автоматизированной системы управления метрополитена (ИАСУМ). Автоматизированная система планирования перевозочного процесса на метрополитене предназначена для автоматизированного построения графика оборота подвижного состава и планового графика движения пассажирских поездов.

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

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

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

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

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

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

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

1. За базовый уровень принять наиболее развитую, на момент разработки, микропроцессорную архитектуру.
2. Сохранить модульный принцип построения и оставить задел для разработки блока, ориентированного и на более продвинутую архитектуру после выхода таковой на рынки аппаратного обеспечения.
3. Разработать мультипоточность, ориентированную на базовый уровень.
4. Упростить базовое распараллеливание отдельно для четырёхядерной архитектуры, а после и для двуядерной.
5. Снабдить диалоговое окно с настройками пользовательского интерфейса переключателем количества ядер.

К архитектуре программного обеспечения также предъявляется ряд особых требований. Прежде всего, необходимо определиться с операционной системой, под управлением которой должна функционировать система. Сразу договоримся, что универсального (кроссплатформенного) подхода здесь достигать совершенно не обязательно, поскольку интеллектуальная автоматизированная система планирования перевозочного процесса на Московском метрополитене является узкоспециальным программным продуктом, пользователи которого обучены рабате только в операционных системах семейства Microsoft Windows. Более того, родственные системы, разработанные на кафедре УИТС и взаимодействующие с автоматизированной системой построения планового графика движения пассажирских поездов метрополитена, функционируют под управлением операционных систем Microsoft Windows. Соответственно, необходимо подобрать такую версию из этого семейства, которая поддерживает распараллеливание потоков. От среды программирования в этом случае требуются следующие возможности:

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

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

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

Движение поездов в соответствии с плановым графиком является примером реализации системы программного управления. Реализация управляющих воздействий в этом случае заключается в выполнении процедур, изменяющих свойства отдельных ниток: создание, удаление, изменение станции начала или конца, изменение расписания (перемещение нитки, ввод сверхрежимной стоянки), изменение связей между нитками, определение маневровых перемещение в начале и конце нитки. Более сложными процедурами являются те, в которых одно и то же действие применяется к группе ниток, например, создание или удаление ниток на заданном интервале времени, перемещение группы ниток, изменение способа отображения оборотов у группы ниток. Основой всей процедуры автоматизированного синтеза являются логико-трансформационные правила, которые представляют собой последовательное выполнение различных процедур коррекции ниток в соответствии с заданным алгоритмом и исходными данными с последующей оценкой результата выполнения [4]. К таким процедурам относятся алгоритмы выравнивания интервалов между поездами, размена через депо или линейные пункты технического осмотра для перехода маршрута на нужную нитку при организации ночной расстановки составов на линии, создания фрагментов равномерного ввода и снятия составов, ухода составов в ночную расстановку и выхода из нее утром.

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

Для удобства решения задача построения планового графика движения разбита на этапы. Эти этапы соответствуют режимам работы метрополитена в рабочие, а также субботние, воскресные и праздничные дни.

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

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

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

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

Для каждого из этапов, который соответствует тому или иному способу организации движения поездов, определены:

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

Условия реализуемости и реализации построения этапов планового графика движения вместе образуют переходный блок – связующее звено двух соседних процедур построения, объединённых причинно-следственными связями [5].

Особым образом следует выделить переменные состояния различных объектов графика. Именно благодаря наличию переменных состояния появляется возможность построения графика не только с чистого листа, но и с некоторого фиксированного этапа. Такой механизм предусмотрен, чтобы позволить оператору организовать:

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

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

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

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

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

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



где M[i, j] - количество составов, которые должны быть на j-м пути линии к началу рассматриваемого интервала времени (процесса построения ПГД) с порядковым номером i.
M[i+1, j] - количество составов, которые должны быть на j-м пути линии к началу следующего к рассматриваемому интервалу времени.
НОД(M[i+1, j], M[i+1, j] - M[i, 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, количество возможных вариантов значительно сокращается.

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

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



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



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

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

В настоящее время авторами проводятся разработки по следующим направлениям:

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

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

Литература:

1. Википедия. Свободная энциклопедия. Программа развития Московского метрополитена. [Электронный ресурс], http://ru.wikipedia.org/wiki/Программа_развития_Московского_метрополитена, (дата обращения: 13.ноябрь.2012).
2. Сафронов А.И., Сидоренко В.Г. Уровни успешной реализации автоматизированного построения плановых графиков движения пассажирских поездов метрополитена и критерии отбора эффективных результатов Проблемы управления безопасностью сложных систем: Труды XIX Международной конференции. Москва, декабрь 2011 г. / Под ред. Н.И. Архиповой, В.В. Кульбы. М.: РГГУ, 2011. С. 307 - 311.
3. Сафронов А.И., Сидоренко В.Г. "Построение планового графика движения для метрополитена", Мир транспорта, №3, 2011. - С. 98-105.
4. Сидоренко В.Г. Моделирование функционирования станции метрополитена с использованием сетей Петри // Международный межвузовский сборник научных трудов "Актуальные проблемы развития технических средств железнодорожной автоматики и телемеханики". - Ростов н/Д: РГУПС, 2002. - c. 89-95.
5. Сафронов А.И. Условия реализации и реализуемости при автоматизированном построении планового графика движения пассажирских поездов метрополитена // Труды научно-практической конференции "Неделя науки-2011. Наука транспорту". - М.: МИИТ, 2011. - c. III-157-III-158.

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

Сидоренко, В. Г. Интеллектуальная автоматизированная система планирования перевозочного процесса на метрополитене / А. И. Сафронов, В. Г. Сидоренко, К. М. Филипченко // ИСУЖТ–2012: труды I научно-технической конференции. - М.: ОАО «НИИАС», 2012. - С. 99-104 (92-96).

"ДАЛЕЕ..."

Сафронов А.И.

ВЗАИМОСВЯЗЬ ГРАФИКА ОБОРОТА ПОДВИЖНОГО СОСТАВА С ПЛАНОВЫМ ГРАФИКОМ ДВИЖЕНИЯ ПАССАЖИРСКИХ ПОЕЗДОВ МЕТРОПОЛИТЕНА

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

ГО является нормативным документом, над составлением которого работают как сотрудники Службы движения (Д), так и инженеры Службы подвижного состава (ТЧ) Московского метрополитена.

Для большинства линий Московского метрополитена различают следующие типы технических осмотров:

1. «ТО-0» - диагностика, проводимая перед выпуском состава на линию в начале рабочего дня. Осмотры этого типа должны проводиться не менее одного раза в сутки;
2. «ТО-1» - включает в себя наружный и внутренний осмотр оборудования вагонов, кабины машиниста, проверку уровня смазочных материалов, а также гигиеническую уборку салона. Длительность осмотра рассчитывается из условия – не менее 10 минут на вагон;
3. «ТО-2» - проводится спустя 10 000 километров пробега подвижного состава. Заключается в полной проверке всех пневматических и электромеханических систем (не менее 30 минут на вагон);
4. «ТО-3» - проводится спустя 30 000 километров пробега (не менее 40 минут на вагон). Состав работ тот же, что при ТО-2.

За распределение ТО-2 и ТО-3 отвечает ТЧ, а за распределение ТО-1 – Служба Д. Подобное распределение основывается на информации, которой оперирует каждая из служб. Так при построении ПГД с учётом ГО, в первую очередь, необходимо распределить заданные ТО-2 и ТО-3, выступающие в качестве ограничений для инженеров-графистов, далее распределить ТО-1.

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

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

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

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

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

В настоящее время проводится анализ полученных вариантов ПГД при учтённом ГО.

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

Сафронов, А. И. Взаимосвязь графика оборота подвижного состава с плановым графиком движения пассажирских поездов метрополитена / А. И. Сафронов // Труды XIII научно-практической конференции «Безопасность Движения Поездов». - М.: МИИТ. - 2012. - C. II-6.

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

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

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

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

В статье [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

"ДАЛЕЕ..."

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

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

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

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

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

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

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

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

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



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

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

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



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

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



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



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

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

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

Литература

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

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

Сафронов, А. И. Анализ быстродействия алгоритмов автоматизированного построения планового графика движения пассажирских поездов метрополитена / А. И. Сафронов, В. Г. Сидоренко // Программа конференции «Технические и программные средства систем управления, контроля и измерения» (УКИ’12): Конференция с международным участием (16-19 апреля 2012 г., Москва, Россия). Учреждение Российской академии наук Институт проблем управления им. В.А. Трапезникова РАН. - 2012. - С. 76.

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

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

"ДАЛЕЕ..."

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

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

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

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

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

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

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

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

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



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

Авторами выполнен анализ всех процессов ПГД и формализованы условия реализуемости и реализации этих процессов. Эта формализация составлена для линий двух типов: радиальных и кольцевых. Рассмотрим эту формализацию в естественном порядке следования процессов, согласно рассмотренному ранее режиму работы Московского метрополитена в рабочие дни. Сразу отметим, что для радиальных линий характерным для всех процессов построения ПГД условием реализуемости является контроль ограничений на организацию станционных оборотов с учетом числа маневровых бригад в рассматриваемом интервале времени [4]. Перейдём к непосредственному рассмотрению процессов автоматизированного построения ПГД.

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



где Nn - число «ниток» графика;
n[i] - «нитка» графика;
n[i]:flgStart - компонент последовательности «нитка» n – флаг начала, определяющий тип маневровой работы с маршрутом до начала движения по нитке графика;
n[i]:npn - предыдущая «нитка» к «нитке» n, то есть «нитка», по которой маршрут двигался до начала движения по «нитке» n (до оборота);
Npnr - общее число точек ночной расстановки на линии, используемых при заданной расстановке;
pnr[j]:C - ёмкость j-й точки ночной расстановки.

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



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



где d[j] - j-е депо линии;
Nd - количество депо линии;
d[j]:pnr:C - ёмкость j-го депо линии;
n:pnr[S] - компонент последовательности «нитка» n – точка выхода (S) из ночной расстановки.

Утренний и вечерний часы «пик» в отношении проверки условий реализуемости и реализации могут быть рассмотрены как аналогичные процессы. Это объясняется свойствами зеркальной симметрии ПГД [5] относительно дневного часа «непик». Для построения этого процесса необходимо, чтобы общее число составов, обслуживающих кольцевую линию, соответствовало распределению составов по главным путям. В случае радиальной линии необходимо знать, нужно ли проводить построение графика зонного типа (ГЗТ) или нет [6]. Общим условием реализуемости этапа является контроль соответствия заданной парности заданному числу составов, обслуживающих линию:



где Nm - общее количество маршрутов линии;
RD[j] - последовательность «размеры движения», компоненты которой задаются на один астрономический час. Основными компонентами последовательности являются: время начала размера движения, время завершения размера движения, парность, интервал, время полного оборота составов, количество составов на первом главном пути, количество составов на втором главном пути, общее количество составов на главных путях;
j - номер компонента последовательности «размеры движения», соответствующий определённому такту часа «пик». Номер компонента последовательности также является и порядковым номером такта;
RD[j]:Mнв - количество составов, которые по тем или иным причинам не участвуют в движении в j-м такте;
RD[j]:Mпотр - количество составов, необходимое для заданной парности в j-м такте движения.

Процессы построения часов «пик» отличаются тем, что условия реализуемости совпадают с условиями реализации (если процесс построения при упомянутых условиях реализуем, то он обязательно будет реализован).

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

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

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

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

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



где M[i] - i-й маршрут линии, назначенный на текущий день;
M[i]:Mn - маршрут, назначаемый составу маршрута M[i] на следующий день;
fFN(M[i]) - функция определения «нитки» начала движения маршрута M[i];
n[i]:pnr[E] - компонент последовательности «нитка» n – точка ухода (E) на ночную расстановку.

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

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



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

Как было отмечено ранее, ПГД обладает свойством зеркальной симметрии относительно дневного часа «непик» [5], в связи с чем, изменение парности в утренние часы сказывается на парности в вечерние часы и наоборот.

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

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

С уменьшением парности ситуация улучшается, при этом необходимо меньше составов выводить из депо во время переходного процесса.

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

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

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

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

Литература

1. Баранов Л.А., Жербина А.И. Построение на ЭВМ графиков движения поездов метрополитена // Вестник ВНИИЖТа, 1981, №2. - С. 17-20.
2. Феофилов А.Н. Математическая модель составления графиков движения поездов на линиях метрополитена // Вестник ВНИИЖТ. 1991, № 7. - С. 10-13.
3. Василенко М.Н., Дегтярев Д.П., Максименко О.А. Проблемы визуального анализа графика движения поездов на метрополитене и методы их решения // Неделя науки-2002. СПб.: ПГУПС, 2002.
4. Сидоренко В.Г. Автоматизация построения планового графика движения поездов метрополитена // Автоматизация и современные технологии, 2003, №2. – С. 6–10.
5. Сафронов А.И., Сидоренко В.Г. Синтез сценариев построения планового графика движения пассажирских поездов Кольцевой линии метрополитена // Проблемы регионального и муниципального управления: Сборник докладов международной научной конференции. 2010. С. 166-170.
6. Сидоренко В.Г., Новикова М.В. Синтез планового графика движения зонного типа // Мир транспорта. 2009, № 4. - С. 128-134.
7. Сидоренко В.Г., Пискунов А.С. Процедуры организации ночной расстановки составов на линии метрополитена // ВЕСТНИК МИИТа // Научно-технический журнал. М.: МИИТ. 2008, вып. 18. - С. 3-7.

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

Сафронов, А. И. Сценарное пространство построения планового графика движения поездов метрополитена / А. И. Сафронов, В. Г. Сидоренко // Наука и техника транспорта. - 2012. - №1. - С.51-56.

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

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

"ДАЛЕЕ..."

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

Уровни успешной реализации автоматизированного построения плановых графиков движения пассажирских поездов метрополитена и критерии отбора эффективных результатов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература:

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

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

Сафронов, А. И. Уровни успешной реализации автоматизированного построения плановых графиков движения пассажирских поездов метрополитена и критерии отбора эффективных результатов / А. И. Сафронов, В. Г. Сидоренко // Проблемы управления безопасностью сложных систем: Труды XIX Международной конференции. Москва, декабрь 2011 г. / Под ред. Н.И. Архиповой, В.В. Кульбы. - М.: РГГУ. - 2011. - С. 307-311.

"ДАЛЕЕ..."

Сафронов А.И.

АВТОМАТИЗИРОВАННОЕ ПОСТРОЕНИЕ ПРОЦЕССА УХОДА СОСТАВОВ НА НОЧНУЮ РАССТАНОВКУ ПРИ УЧЁТЕ УРОВНЕЙ РАВНОМЕРНОСТИ

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

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

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

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

Для ускорения перебора вариантов применяются два механизма сокращения:

- за счёт учёта проверки условий реализуемости;
- за счёт учёта многоуровневой структуры равномерности.

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

Второй механизм сокращения вариантов содержится внутри следующего алгоритма:

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

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

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

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

Сафронов, А. И. Автоматизированное построение процесса ухода составов на ночную расстановку при учёте уровней равномерности / А. И. Сафронов // Труды XII научно-практической конференции «Безопасность Движения Поездов». - М.: МИИТ. - 2011. - C. IX-12-IX-13.

УДК 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

"ДАЛЕЕ..."

Солдатов Н.Л. (АУИ-211), Ушаков К.А. (АУИ-311), Харчилин Д.И. (АУИ-211), Чайковский М.В. (АУИ-311), Сафронов А.И. (аспирант)

СОЗДАНИЕ ИНТЕРФЕЙСА И ИНФОРМАЦИОННОГО ОБЕСПЕЧЕНИЯ АВТОМАТИЗИРОВАННОГО РАБОЧЕГО МЕСТА ИНЖЕНЕРА ПО ЭКСПЛУАТАЦИИ ЭЛЕКТРОДЕПО МЕТРОПОЛИТЕНА

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

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

Потребителем результатов работы АРМ могут быть и другие службы метрополитена, в частности Служба подвижного состава при управлении локомотивными бригадами электродепо Московского метрополитена.

Ряд исходных данных, которые необходимы для расчётов, проводимых АРМ инженера по эксплуатации электродепо совпадает с величинами, хранящимися в базе данных (БД) АСП ПГД ППМ, таким образом, рационально брать за основу существующую БД и вносить в неё некоторые коррективы.

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

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

На протяжении нескольких лет Visual Basic 6.0 считали хорошим средством для разработки программного обеспечения (ПО). На базе статистики использования языков программирования, находящейся в открытом доступе в сети Интернет было принято решение о создании АРМ инженера по эксплуатации электродепо метрополитена на популярном современном языке программирования С#.

Язык основан на строгой компонентной архитектуре и реализует передовые механизмы обеспечения безопасности кода. Авторами выделены следующие особенности языка:

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

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

GDI – графический интерфейс Windows, необходимый для представления объектов и передачи их на устройства отображения.

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

В результате работ по созданию нового АРМ в среде Visual Studio 2010 было налажено информационное обеспечение среды, получаемое из БД, что позволило приступить к комплексной отладке графического интерфейса, а также к возможности изменения данных внутри ПО АРМ инженера по эксплуатации электродепо метрополитена.

Работа выполнена под руководством д.т.н., профессора Сидоренко В. Г.

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

Сафронов, А. И. Создание интерфейса и информационного обеспечения автоматизированного рабочего места инженера по эксплуатации электродепо метрополитена / А. И. Сафронов, Н. Л. Солдатов, К. А. Ушаков, Д. И. Харчилин, М. В. Чайковский // Труды научно-практической конференции «Неделя науки-2011. Наука транспорту». - М.: МИИТ. - 2011. - C. III-159.