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

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

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

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

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

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

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

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

Созданная авторами процедура автоматизированного построения ПГД и предложенная многоуровневая структура равномерности ПГД позволяют не только просматривать множество вариантов построения ПГД без изменения исходных данных, но и проводить варьирование исходных данных, не противоречащее целям управления [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

Вложение: 13420023_2012_uki.pdf