К ВОПРОСУ ОБ ОЦЕНКЕ БЫСТРОДЕЙСТВИЯ МЕТОДА ВЫРАВНИВАНИЯ ВРЕМЕННЫХ ИНТЕРВАЛОВ

CONSIDERING THE EVALUATION OF TIME INTERVALS ALIGNING METHOD PERFORMANCE ISSUE

Сидоренко Валентина Геннадьевна / Sidorenko Valentina G.,
доктор технических наук, профессор кафедры «Управление и информатика в технических системах» Московского государственного университета путей сообщения МГУПС (МИИТ) / Moscow State University of Railway Engineering, Doctor of Science, professor of the department "Management and Information Technology in Engineering systems,

Сафронов Антон Игоревич / Safronov Anton I.,
ассистент кафедры «Управление и информатика в технических системах» Московского государственного университета путей сообщения МГУПС (МИИТ) / Moscow State University of Railway Engineering, assistant of the department "Management and Information Technology in Engineering systems,

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

Abstract
А proof of sequentially moving objects intervals aligning method performance on example of the Moscow metro is presented. The proof is carried out by the method of mathematical induction in following cases: single train insertion/removal, multiple trains insertion/removal in regular intervals, multiple trains insertion/removal in a row. An analytical expression, which allows to calculate the transition process associated with the change of parity movement duration, considering the selected vehicle position in the sequence is obtained. The maximum duration of transition process since the signal for trains insertion/removal giving by dispatcher is evaluated.

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

Keywords: metro, evaluation of performance, time intervals aligning method, uniformity, Euclid division algorithm, mathematical induction, system analysis.


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

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

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

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

В соответствии с технологией работы метрополитена имеется определённая последовательность процессов ПГД [4].

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

Равномерный ввод/снятие составов определяется в соответствии с формулировкой, данной в [5]. Равномерными расположениями исключаемых элементов из множества N[S] элементов называются такие расположения, при которых длины двух соседних серий элементов отличаются не более, чем на один элемент. При этом серией называется последовательность элементов, начинающаяся с исключаемого элемента, и заканчивающаяся элементом, предшествующим следующему исключаемому.

Найдём потенциальную оценку длительности переходного процесса выравнивания интервалов движения D(N[S], K) после того, как снятие K составов было завершено.

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

Одновременно предполагается, что до начала снятия составов все N[S] поездов двигались с равными интервалами движения Тпо/N[S], где Тпо - время полного оборота.

Для определения времени, необходимого для выравнивания интервалов движения у всех поездов на линии после снятия составов, воспользуемся методом математической индукции. Сначала рассмотрим снятие одного состава с линии. После выполнения этого действия у поезда, следующего за снятым, интервал движения удвоится (2*Тпо)/N[S]. У остальных поездов он останется неизменным. При этом все поезда должны перейти на новый интервал движения равный Tпо/(N[S]-1).

Для перехода к новому интервалу движения J(N[S], 1, 1) последний перед снятым составом поезд должен остановиться на время, определяемое следующим выражением:



Ввод сверхрежимной выдержки (СРВ), длительность которой определяется выражением (1), позволяет уменьшить интервал движения между поездами, являвшимися соседями снятого состава, до требуемого значения.

Послевыполнения этой СРВ интервал движения между предпоследним и последним перед снятым составом поездами станет равным:



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



После этого интервал движения между третьим и вторым перед снятым составом поездами станет равным:



Пусть интервал движения между (i-1)-м поездом, который выполнил СРВ, и предыдущим определяется следующим выражением:



Пусть для перехода к новому интервалу движения i-й предшествующий снятому составу поезд должен остановиться на время, определяемое следующим выражением:



Тогда для (i+1)-го поезда верно утверждение, что интервал движения между i-ми (i+1)-м поездами будет равен:



В этом случае (i+1)-му поезду для перехода к новому интервалу движения необходимо остановиться на время, определяемое следующим выражением:



Таким образом, методом математической индукции показано, что для случая снятия с линии одного состава длительности СРВ, которые должны выполнить все поезда для выравнивания интервалов движения на линии, и интервалы движения между поездом, который выполнил СРВ, и предыдущим определяются зависимостями (6) и (5), соответственно. Выражение (6) достигает своего максимального значения при заданном N[S] при i=1 и не превышает величины исходного интервала движения. Зависимость (6) при Тпо=1 проиллюстрирована Рисунком 1.

Значение функции Т(N[S], 1, i) достигает нулевого значения при i=N[1]-1, что соответствует тому факту, что для выравнивания интервалов движения СРВ должны выполнить все поезда на линии, кроме поезда, который следует непосредственно за снятым составом. Одновременно, после выполнения СРВ (N[S]-2)-м поездом интервал между ним и (N[S]-1)-м поездом в соответствии с выражением (5) сразу становится равным плановому:



Так как все поезда могут остановиться одновременно, длительность переходного процесса определяется максимальной длительностью вводимой СРВ, то есть значением T(N[S], 1, i) при i=1:



Из анализа графика (рис. 1) видно, что чем больше поездов на линии, тем меньше длительность необходимой для выравнивания интервалов движения СРВ при N[S]>=4.


Рис. 1 - Длительности СРВ, которые выполняют i-е поезда при различном исходном количестве поездов на линии N[S]

Зависимость (10) при Тпо=1 проиллюстрирована рисунком 2.


Рис. 2 - Длительность переходного процесса выравнивания интервалов движения при снятии одного состава

Рассмотрим ситуацию, когда с линии производится равномерное снятие K составов. Пусть K является делителем N[S]. В этом случае все серии поездов будут одной длины N[S]/K, и поезда, следующие непосредственно за снимаемыми, не должны будут выполнять СРВ для выравнивания интервалов движения, так как интервалы между ними будут равны изначально. Внутри каждой серии переходный процесс будет аналогичен рассмотренному выше. Его длительность, как и ранее, будет определяться длительностью СРВ, выполняемой поездом, непосредственно предшествующим снятому составу. Для перехода к новому интервалу движения, равному J(N[S], K, 1)=Тпо/(N[S]-K), последний перед снятым поезд должен остановиться на время, определяемое выражением:



Проиллюстрируем полученную зависимость рисунком 3. По технологии работы метрополитена снятие более половины составов не производится, что определяет приведённый на рисунке 3 диапазон изменения переменной K. При K=N[S]/2 в соответствии с формулой (11) длительность переходного процесса равна нулю. Действительно, в этом случае при чётном значении N[S] равномерное снятие осуществляется через один состав, и интервалы движения поездов автоматически становятся равными плановым интервалам движения [6].


Рис. 3 - Длительность переходного процесса выравнивания интервалов движения при равномерном расположении K снимаемых составов

Полученное выражение (11) не противоречит приведённому в [6] утверждению, что при наилучшем способе снятия составов, которым является равномерное снятие, длительность переходного процесса выравнивания интервалов не превысит исходного интервала следования поездов Тпо/N[S].

Пусть осуществляется равномерное снятие K+1 состава, K+1 - делитель N[S]. Для перехода к новому интервалу движения последний перед снятым поезд должен остановиться на время, определяемое выражением:



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

В случае, когда K не является делителем N[S] и их наибольший общий делитель НОД(N[S], K) равен единице, в соответствии с алгоритмом деления Евклида числа N[S] и K связаны выражением:



где Z - частное от деления N[S] на K, равное длине коротких серий при равномерном расположении снимаемых составов;
Pmax - остаток от деления N[S] на K, равный количеству длинных серий при равномерном расположении снимаемых составов, длина которых равна Z+1.

Рассмотрим поезд, стоящий на i-м месте в исходной последовательности. Счёт поездов начинается со снимаемого состава i=1. Поезд, предшествующий первому из снятых, имеет номер 2: i=2. Если i-му поезду предшествовало снятие Y(i)+1 составов, то из Y(i) предшествующих серий P(Y(i)) были длинными. В Y(i)+1 серии i-й поезд будет находиться на месте U(i):



при



В этом случае необходимая для перехода к новому интервалу длительность СРВ для поезда, находящегося на i-м месте, равна разности между его текущей временной координатой и требуемой:



Ноль выражения (19) получается в том случае, если K/N[S]=(Y(i)+1)/i. Иными словами, если Y(1)=K-1 и i=N[S] , то ноль выражения (19) может быть получен для поезда, следующего за первым из снятых. Выполнив подстановку в (19) выражения (14), при учёте (13) получим:



Рассмотрим пример. Пусть производится равномерное снятие 7–ми составов из множества, состоящего из 45–ти составов. В этом случае НОД(45,7)=1. Проиллюстрируем эту ситуацию (рис. 4) согласно [5]. Снимаемые составы пронумерованы, начиная с максимально длинной последовательности серий меньшей длины.


Рис. 4 - Равномерное расположение 7-ми элементов из 45-тиэлементного множества

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


Рис. 5 – График времён стоянки каждого из элементов 45-тиэлементного множества
Длительность СРВ достигает своего максимального значения, определяющего длительность всего переходного процесса, в начале серии большей длины, следующей за максимально длинной последовательностью серий меньшей длины (в нашем случае, при i=14). Полученное значение совпадает со значением, определяемым по формуле (1), приведенным в [6]. Покажем это:



Если числа K и N[S] имеют наибольший общий делитель НОД(N[S], K), не равный единице, то длительность переходного процесса выравнивания интервалов движения уменьшится в НОД(N[S], K) раз по сравнению с длительностью переходного процесса снятия K1=K/НОД(N[S], K) составов из множества N1=N[S]/НОД(N[S], K).

Рассмотрим наиболее неблагоприятное неравномерное расположение составов. Это случай, когда K составов снимаются подряд. Длительность переходного процесса, как и раньше, определяется продолжительностью СРВ поезда, перед которым было выполнено такое снятие. Для перехода к новому интервалу движения поездов F(N[S], K, 1)=Tпо/(N[S]-1) последний перед снятым составом поезд должен остановиться на время, определяемое следующим выражением:




Проведём дальнейшие расчёты при Тпо=1.
Продифференцируем полученную зависимость (21) по N[S]:



Найдём экстремум (21), для этого приравняем к нулю выражение (22):



После преобразований получим:



Решая квадратное уравнение относительно N[S] получаем:



После подстановки одного из корней уравнения в зависимость (21) получаем верхнюю Lnu[nr](N[S], K) границу длительности переходного процесса выравнивания интервалов движения поездов:



Результаты проведённых выше расчётов приведены на графике (рис. 6).


Рис. 6 - Длительности переходного процесса выравнивания интервалов движения поездов при неравномерном расположении K снимаемых составов

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

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



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

Литература

1. Баранов Л.А., Жербина А.И. Построение на ЭВМ графиков движения поездов метрополитена // Вестник ВНИИЖТа, №2, 1981. – С. 17–20.
2. Феофилов А.Н. Математическая модель составления графиков движения поездов на линиях метрополитена // Вестник ВНИИЖТ, № 7, 1991. – С. 10–13.
3. Василенко М.Н., Дегтярев Д.П., Максименко О.А. Проблемы визуального анализа графика движения поездов на метрополитене и методы их решения // Неделя науки-2002. – СПб.: ПГУПС, 2002.
4. Сафронов А.И., Сидоренко В.Г. Построение планового графика движения для метрополитена // Мир транспорта, №3, 2010. – С. 98–105.
5. Концевич М.Л. Равномерные расположения // Квант, №7, 1985. – С. 51–52, 59.
6. Сеславин А.И., Сеславина Е.А. Принципы равномерности в задачах управления потоками пассажирского транспорта // Прикладная информатика, № 2(20), 2009. – С. 91–95.
7. Сидоренко В.Г., Рындина Е.Ю. Методы выравнивания интервалов движения поездов метрополитена, ВЕСТНИК МИИТа // Научно-технический журнал, Вып. 18, 2008. — С. 8-10.
8. Сеславин А.И., Воробьева Л.Н. Градиентный способ централизованного управления городскими транспортными системами // Наука и техника транспорта, №4, 2004.

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

Сафронов, А. И. К вопросу об оценке быстродействия метода выравнивания временных интервалов / А. И. Сафронов, В. Г. Сидоренко // Научно-методический журнал «Информатизация образования и науки». - М: ФГАУ ГНИИ ИИТ «Информика». - 2014. - № 1 (21) - С. 120-130. - ISSN 2073-7572.

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

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

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