Проблемы проектирования и строительства железных дорог.

Сборник научных трудов. – Хабаровск: Изд-во ДВГУПС, 2011. – С. 55-59

В.В. Анисимов

Дальневосточный государственный университет путей сообщения

 

ОПРЕДЕЛЕНИЕ ЧИСЛА ОДНОВРЕМЕННЫХ ПЕРЕДВИЖЕНИЙ ПО СТРЕЛОЧНОЙ ГОРЛОВИНЕ

 

Предложен способ определение числа одновременных передвижений по стрелочной горловине на основе алгоритма Брона-Кербоша.

 

Результативная пропускная способность станции зависит от пропускной способности ее парков, стрелочных горловин и пассажирских устройств [1].

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

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

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

Введем следующие обозначения:

- u – условная стрелка.

- М = {u1, u2, …, un} – перечень (множество) условных стрелок, входящих в маршрут следования. Так, маршрут № 1 на рис.1 может быть представлен M1 = {u2, u5, u4, u3};

- S = (M1, M2, …, Mm) – упорядоченное (по номерам) множество маршрутов.

Маршруты Mi и Mj будут считаться независимыми, если Mi ∩ Mj = Ø, в противном случае – враждебными.

Таким образом, требуется найти S* с максимальной мощностью max|S*| при соблюдении следующего условия

Mi, Mj S* : Mi ∩ Mj = Ø, i ≠ j.     (1)

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

На основе введенных обозначений алгоритм Брона-Кербоша, применительно к поставленной задаче, выглядит следующем образом.

 

Шаг 1. S* = Ø.

Шаг 2. Для i = 1 до |S|

Шаг 2.1. Если |S*| > |S| – i, то завершить поиск S*

Шаг 2.2. S+ = (Mi)

Шаг 2.3. S = Ø

Шаг 2.4. Для j = i+1 до |S|

Шаг 2.4.1. Если Mi ∩ Mj = Ø, то S = S U (Mj)

Шаг 2.5. Если |S*| ≥ |S+| + |S|, то перейти к шагу 2

Шаг 2.6. Пока S ≠ Ø

Шаг 2.6.1. S+ = S+ U (Mk)

Шаг 2.6.2. S = S \ (Mk)

Шаг 2.6.3. Для j = 1 до |S|

Шаг 2.6.3.1. Если Mk ∩ Mj ≠ Ø, то S = S \ (Mj)

Шаг 2.6.4. Если |S*| ≥ |S+| + |S|, то перейти к шагу 2

Шаг 2.7. Если |S+| > |S*|, то S* = S+

 

Некоторые замечания по предложенному алгоритму.

1. Маршрут Mk, используемый в шагах 2.6.x, является первым на текущий момент маршрутом в S.

2. Существенно сократить время поиска решения позволяют следующие приемы:

- проверка условий на шагах 2.1, 2.5 и 2.6.4, т.к. |S+| на шаге 2.7 будет заведомо меньше или равна |S*|;

- предварительная генерация матрицы враждебности маршрутов размером |S| х |S| для ускорения проверки условий 2.4.1 и 2.6.3.1;

- предварительное исключение из S маршрутов, составной частью которых являются другие маршруты. Очевидно, что из двух маршрутов Mi = {u6, u7, u8, u9} и Mj = {u6, u7} маршрут Mi может быть исключен из S, т.к. |S+Mi| будет заведомо меньше или равна |S+Mj|. Условие исключения маршрута Mi из множества S выражается следующим образом

Mj S : |Mi| > |Mj| & ( uj Mj, ui Mi : uj = ui).     (2)

Описанный в статье способ определения числа одновременных передвижений реализован в автоматизированной системе «Пропускная и перерабатывающая способность станций» (АС ППСС) [3, 4].

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

 

СПИСОК ЛИТЕРАТУРЫ

 

1. Инструкция по расчёту наличной пропускной способности железных дорог / отв. за выпуск Л.А. Канарская, О.А. Жаброва. – М.: Транспорт,1991. – 303с.

2. Н. Кристофидес. Теория графов. Алгоритмический подход. – М.: «Мир»,1978. – 432с.

3. Пропускная и перерабатывающая способность станций: автоматизация расчетов / Архангельский Е.В., Анисимов В.А., Анисимов В.В., Степанов А.В. // Железнодорожный транспорт – 2008. – № 3. – С.29-33.

4. http://sites.google.com/site/isystemgdt.