- •Лекція № 1. Формування багатогрупних составів на витяжних коліях
- •1.1. Комбінаторний метод формування составів.
- •1.2. Розподільний метод формування составів.
- •1.3 Умовна нумерація груп вагонів
- •Привласнення умовних номерів
- •Лекція № 2. Розподільна задача лінійного програмування і її використання для оптимізації технологічних процесів залізничних станцій
- •2.1. Задача о загрузке
- •3.2 Значення й економіко-математичне формулювання розподільної задачі
- •3.3 Розв’язання задачі розподілу вагонів під навантаження методом множників, що дозволяють
- •3.3.1 Алгоритм розв’язання розподільної задачі
- •Лекція № 3. Задача коммивояжера
Лекція № 1. Формування багатогрупних составів на витяжних коліях
Формування составів, особливо багатогрупних, є одним з найбільш трудомістких елементів технологічного процесу переробки вагонів на станціях. Ця задача широко вирішується під час закінчення формування збірних поїздів, коли вагони необхідно підібрати у порядку призначення на проміжні станції дільниці і у разі добірки вагонів по фронтах вантажної роботи на вантажних станціях.
Тривалість виконання сортування состава залежить від різних факторів: початкової упорядкованості состава, типу сортувального пристрою та маневрового локомотива; методу сортування (осаджуванням, одиночними або серійними поштовхами) та порядку виконання маневрів.
В оперативних умовах тривалість формування состава в основному залежить від порядку виконання маневрових напіврейсів. Цей порядок визначає складач поїздів, в основному спираючись на власний досвід. Природно, що тривалість формування може змінюватися в широких межах.
Тим часом є математичні методи, використання яких дозволяє досить ефективно виконувати формування.
Попередньо установимо деякі угоди та визначення. Будемо вважати, що для формування поїздів використовується сортувальний пристрій (гірка, витяжна колія) та певна кількість сортувальних колій m (2 m ). Формування состава здійснюється за N етапів, кількість яких залежить від методу формування, кількості сортувальних колій, що використовуються, m і кількості груп у невпорядкованому составі. Кожен етап формування незалежно від методу, який використовується, включає дві операції: збирання вагонів із mсб колій і їх сортування на mс колій.
Прийнято, що перед початком формування вагони состава знаходяться на одній із сортувальних колій, так що на першому етапі mсб1=1. На останньому етапі вагони знову повинні бути зібрані на одній колії (mсN=1). На інших етапах кількість колій, що використовується, залежить від методу формування та від їх наявної кількості M.
1.1. Комбінаторний метод формування составів.
Комбінаторний метод, який запропоновано у ВНІІЖТі, ґрунтується на представленні чисел у фібоначчиєвій системі числення.
Номери груп = 0, …, 16 у фібоначчиєвому записі наведено в табл. 1.1. У цій же таблиці вказано кількість етапів формування N, яка необхідна, якщо максимальний номер групи в составі дорівнює .
Ряд Фибоначчи составляют числа, каждое из которых представляет собой сумму m предшествующих чисел. Например при m =3 имеем следующий ряд:
m-1 |
|
|
|
|
|
|
| |
0 |
0 |
1 |
1 |
|
|
|
|
|
|
0 |
1 |
1 |
2 |
|
|
|
|
|
|
1 |
1 |
2 |
4 |
|
|
|
|
|
|
1 |
2 |
4 |
7 |
|
|
|
|
|
|
2 |
4 |
7 |
13 |
|
|
|
|
|
|
4 |
7 |
13 |
24 |
Для разработки схем формирования составов используется система кодировки чисел в двоичной форме.
Так при m=3 коды выглядят следующим образом:
|
Ряд Фибоначчи |
код Ф3() | ||||
13 |
7 |
4 |
2 |
1 | ||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
2 |
0 |
0 |
0 |
1 |
0 |
10 |
3 |
0 |
0 |
0 |
1 |
1 |
11 |
4 |
0 |
0 |
1 |
0 |
0 |
100 |
5 |
0 |
0 |
1 |
0 |
1 |
101 |
6 |
0 |
0 |
1 |
1 |
0 |
110 |
7 |
0 |
1 |
0 |
0 |
0 |
1000 |
8 |
0 |
1 |
0 |
0 |
1 |
1001 |
Номера групп = 0, …, 16 в фибоначчиевой записи приведены в табл. Error: Reference source not found; в этой же таблице показано число этапов формирования N, которое необходимо, если максимальный номер группы в составе равен .
Для определения логических номеров путей при сортировке номерам групп { = 0, 1, …, -1} ставятся в соответствие числа в фибоначчиевой записи, взятые из табл. Error: Reference source not found в обратном порядке: обратная последовательность указанных чисел используется для того, чтобы в сформированном составе группы были расположены в прямом порядке (0, 1,…,-1).
Таблиця 1.1
Фібоначчиєвий запис номерів груп
Номер групи |
Кількість сортувальних колій m | |||||||
2 |
3 |
4 |
5 | |||||
Ф2() |
N |
Ф3() |
N |
Ф4() |
N |
Ф5() |
N | |
0 |
0 |
2 |
0 |
2 |
0 |
2 |
0 |
2 |
1 |
1 |
1 |
1 |
1 | ||||
2 |
10 |
3 |
10 11 |
3 |
10 11 |
3 |
10 11 |
3 |
3 |
100 101 |
4 | ||||||
4 |
100 101 110 |
4 |
100 101 110 111 |
4 |
100 101 110 111 |
4 | ||
5 |
1000 1001 1010 |
5 | ||||||
6 | ||||||||
7 |
1000 1001 1010 1011 1100 1101 |
5 | ||||||
8 |
10000 10001 10010 10100 10101 |
6 |
1000 1001 1010 1011 1100 1101 1110 |
5 |
1000 1001 1010 1011 1100 1101 1110 1111 |
5 | ||
9 | ||||||||
10 | ||||||||
11 | ||||||||
12 | ||||||||
13 |
100000 100001 100010 100100 |
7 |
10000 |
6 | ||||
14 |
10001 | |||||||
15 |
10010 |
10000 10001 |
6 | |||||
16 |
10011 |
10000 |
6 |
Как видно в каждом столбце таблицы подряд находится не более m-1 единиц.
Числа используются для определения логического номера пути (ЛНП)i, на который нужно направить i- й отцеп с ЛНГ i при сортировке на каждом этапе формирования. Для определения ЛНП i на j- м этапе выполняется последовательный анализ цифр в записи :
i = k, если k+j=0, k+j-1 = …= j+1 = j = 1; (0 i m -1)
При комбинаторном методе после сортировки вагонов на j- м этапе на следующем (j+1)-м этапе сортируют вагоны, находящиеся на пути, который на j-м этапе имел ЛНП =0. Отсутствие операций сборки вагонов после каждой сортировки является существенным достоинством комбинаторного метода. При этом после каждого этапа логические номера всех используемых путей циклически изменяются; для определения ЛНП может использоваться рекуррентное выражение
mod m.
Числа використовуються для визначення логічного номера колії (ЛНК)i, на яку потрібно направити i- й відчеп з логічним номером групи (ЛНГ) i при сортуванні на кожному етапі формування.
При комбінаторному методі після сортування вагонів на j- му етапі на наступному (j+1)-му етапі сортують вагони, що знаходяться на колії, яка на j-му етапі мала ЛНК =0. Відсутність операцій збирання вагонів після кожного сортування є істотною перевагою комбінаторного методу. При цьому послу кожного етапу логічні номери усіх колій, які використовуються, циклічно змінюються.
Приклад:
Виконати формування состава комбінаторним методом на трьох коліях (групи розташувати по зростанню).
Порядок розташування вагонів у составі наступний:
3 |
5 |
1 |
3 |
2 |
3 |
5 |
6 |
0 |
4 |
1. Привласнюємо коди призначенням вагонів:
Номер групи (призначення) k |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
код (при - k-1) |
110 |
101 |
100 |
011 |
010 |
001 |
000 |
- загальна кількість груп. У разі сортування по убуванню k.
Надаємо логічні номери коліям сортувального парку:
0, 01 – у разі сортування на двох коліях;
0, 01, 011 – у разі сортування на трьох коліях;
0, 01,011, 0111 – у разі сортування на чотирьох коліях і т.д.
Відправляємо групи вагонів на ті колії, номером яких закінчується їх двоїчний код (див. рис. 1.1):
Для наступного сортування витягуємо вагони з колії, яка має логічний номер 0. Після кожного етапу логічні номери усіх колій, які використовуються, циклічно змінюються.
Рис. 1.1. Порядок сортування вагонів комбінаторним методом