М Притула, Р Шпакович - Алгоритм побудови графіка руху поїздів - страница 1

Страницы:
1  2 

УДК 656.222.4

М. Притула, Р. Шпакович

Центр математичного моделювання ІППММ ім. Я.С. Підстригача НАН України

АЛГОРИТМ ПОБУДОВИ ГРАФІКА РУХУ ПОЇЗДІВ

© ПритулаМ., Шпакович Р., 2008

Розглянуто питання розвитку теорії і практики побудови графіків руху поїздів. Розраховано основні елементи графіка та результати апробації розроблених алгоритмів побудови графіків руху на реальних даних.

The work is devoted to the questions of development of theory and practice of train schedule building. The calculation of basic schedule elements and approbation's results of the developed algorithms are offered in the work.

Вступ

Теорія побудови графіків та розкладів як наука виникла при складанні розкладів заванта­ження роботою одно- чи багатоопераційних машин (станків) [1]. Кожна робота складається з операцій, які виконуються в певному порядку. При виконанні заданих умов вимагається знайти розклад виконання робіт. У різних випадках якість розкладу оцінюють по-різному. Часто вима­гають, щоб «довжина розкладу» набувала мінімального значення. До теорії побудови графіків та розкладів належать задачі календарного планування [2, 3], формування розкладів руху транспорту, проведення занять тощо. Всі перераховані і багато інших задач настільки відрізняються, що говорити про єдині підходи до їх розв'язування сьогодні не доводиться. Практично всі задачі теорії розкладів належать до класу так званих важкорозв'язних задач. І тому в кожному конкретному випадку потрібно розробляти алгоритми формування графіків та розкладів, виходячи із комбінаторної складності задачі і необхідної точності досягнення критерію оптимальності.

Постановка проблеми

Автоматизація розроблення графіка руху поїздів є доволі складною проблемою, яка перед­бачає розв'язування комплексу задач, які визначають технологію всього перевізного процесу. Сьогодні процес побудови графіка руху складається з таких основних етапів. На першому етапі проводять тягові розрахунки. Незалежно від тягових розрахунків розраховують міжпоїзні і станційні інтервали. Після цього при відповідному інформаційному забезпеченні можна починати будувати графіки руху. Для виконання всіх цих етапів задіяна велика кількість різних спеціалістів і необхіний час на розроблення графіка руху поїздів на сезон становить кілька місяців кожного року. Це повязано з великим обсягом ручної роботи, оскільки автоматизована незначна частина розрахункових задач. На проведення вказаних робіт витрачаються значні кошти, при цьому якість розроблених графіків є невисокою. І тому автоматизація процесу побудови графіків руху поїздів зекономить значні матеріальні ресурси, дасть змогу перейти на формування оперативних графіків і забезпечити високі якісні показники.

Постановка задачі

Для формування графіка руху поїзда відомим є тип його локомотива, інформація про вагони, послідовність слідування через станції і мінімальні часи стоянок на станціях. Такий набір

інформації для p-го поїзда в графіку позначимо Dp = (ap ,Vp, Sp) —, тут a — тип локомотива, V = (v1,..., vm) — склад поїзда (набір вагонів), S = (^,..., sn) — послідовність станцій, через якірухається    поїзд.    Для    вказаного    поїзда   графік   його    руху   записується    у вигляді

p = ((,p , t2,P , t2,p ^ Tn-1,p , Tn-1,p , Tn p ) , дЄ  Tn p  - час прибуття р-го поїзда на П-ну станцію,  Тп,p -

час відправлення p-го поїзда з n-ї станції.

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

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

• безпеку руху - забезпечується розрахунком міжпоїзних і станційних інтервалів руху;

• оптимальність, економність - забезпечується побудовою критеріїв оптимальності прокла­дання поїзда, наборів поїздів; максимальним використання пропускної і переробної спроможностей станцій, перегонів; прокладанням поїзда без додаткових зупинок і простоїв; використання додаткового часу не на збільшення стоянок, а на економію енергоресурсів;

• максимальний ступінь автоматизації побудови - забезпечується введенням системи пріо­ритетів прокладання різних типів поїздів та розпаралеленням процесу побудови графіків руху;

• адаптивність - забезпечується гнучкою взаємодією задач розрахунку елементів графіка руху;

• максимальну стабільність графіка порівняно з минулорічним - забезпечується алгоритмом побудови, який надає критерію близькості двох графіків руху високий пріоритет;

• стійкість графіка - забезпечується врахуванням впливу на розраховані параметри елемен­тів графіка можливих випадкових факторів.

Оптимальний графік руху поїзда. Після формування графіка руху розраховують його параметри. Маючи витратні ставки для його забезпечення, легко знайти його вартість. Графік руху поїзда є оптимальним, якщо його вартість є мінімальною.

Оптимальний графік руху поїздів. Оптимальний графік руху для всіх поїздів в одному напрямку не завжди збігається з оптимальним прокладення кожного поїзда зокрема. Досить часто в звязку з існуванням обмеження пропускної спроможності накладають вимогу на максимізацію залишкової пропускної спроможності. Можливі ще додаткові вимоги щодо забезпечення підви­щеної стійкості графіка руху поїздів.

Для забезпечення системи прокладання графіка руху розроблені системи: графоаналітична; тягово-енергетичних розрахунків [4]; розрахунків станційних та міжпоїзних інтервалів; прив'язки локомотива до графіка руху; прокладання поїзда в графіку руху поїздів. Всі системи в процесі прокладання графіка руху взаємодіють між собою. В основу графоаналітичної системи покладено зважену граф-схему залізниць України, включаючи станції. Вершини і ребра граф-схеми можуть мати різний тип. Кожному типу вершин і ребер відповідає конкретний об'єкт залізниці, або певний інформаційний об'єкт. Всі вони параметрично описані. Параметричний опис є достатнім для розв' язування задач побудови графіка руху. Система тягово-енергетичних розрахунків, викорис­товуючи дані про властивості та стан колій і рухомого складу залізниці, розраховує перегінні часи руху певного поїзда, додаткові часи за розгін/сповільнення поїзда на кожній станції/платформі, показники витрат електроенергії/палива. Також система аналізує режим руху поїзда та оптимізує ведення поїзда з метою зменшення витрат за рахунок можливого збільшення часу руху.

Система розрахунків станційних та міжпоїздних інтервалів, беручи дані про станції та перегони з графоаналітичної системи та результати тягово-енергетичних розрахунків, обчислює параметри безпеки руху для заданих поїздів на певній ділянці руху. Система прокладання поїзда в графіку руху поїздів використовує графоаналітичну систему для отримання інформації про мережу залізниці, топологію станцій, дані про вже прокладені поїзди. Додаткова вхідна інформація (окрім опису поїзда та його маршруту), яка потрібна для прокладання поїзда - «прив' язка поїзда до станції». Щоб задати цю інформацію, потрібно вказати, прибуває чи відправляється поїзд, з якої саме станції та в який момент часу. Також вказується, чи часи стоянок поїзда є фіксованими, чи ні.

Алгоритм побудови графіка руху

В алгоритмі використовуються такі поняття:

станція — підграф граф-схеми залізниці; основні об'єкти: вершини входу-виходу (межі станції), світлова сигналізація, стрілки різних типів, станційні колії, які є спеціалізованими і, в основному, орієнтованими;

горловини станції — вершини входу-виходу станції, наборів вершин входу-виходу може бути декілька (> 2);

перегони — ребра (дуги), які з'єднюють входи-виходи різних станцій;

«сусідні» поїзди — поїзди, між якими виникають інтервали.

Перед прокладанням поїзда з номером P, відомі графіки руху всіх поїздів з номерами від 1 до P-1. Якщо поїзд з номером P на час 70 повністю сформований, то з цього часу починаємо формувати графік

його руху, який би задовольняв умови безпеки його руху на перегоні і на станціях, тобто сусідні поїзди повинні бути розділені часовими інтервалами. Система формує графік з вказаного часу і з довільної станції слідування поїзда (станції прив'язки) в напрямку руху і напрямку станції відправлення. Також перевіряється наявність вільних станційних колій. Якщо умови безпеки руху не виконуються, то сис­тема збільшує час стоянки на потрібній станції (якщо є така можливість і це забезпечить прокладання поїзда). Якщо прокласти поїзд для заданих умов неможливо, то система змінює час «прив'язки» (залежно від того, прибуває поїзд чи відправляється, час зменшується або збільшується відповідно).

Введемо такі позначення:

1, ..., n, ..., N - номери станцій ділянки;

n -ний перегін з'єднює n -ну та (n +1)-шу станції;

Rn - кількість колій на станції n ;

Rn   1 ) - кількість прокладених поздів, що знаходяться на станції n в інтервалі часу (t0, t1) ;

Kn - кількість горловин станції n ;

1, ..., p, ..., P-1 - номери прокладених в графіку поїздів;

tn - час руху поїзда на n -му перегоні;

Тр - додатковий час на розгін з n -ї станції;

T°n - додатковий час на сповільнення при в'їзді на n -ту станцію;

Тп  - тривалість стоянки поїзда на n -й станції;

- тривалість стоянки поїзда на j платформі n-го перегону;

Тпр - час прибуття p-го поїзда (вже прокладеного) на n-ну станцію;

np - час відправлення p-го поїзда (вже прокладеного) на n-ну станцію;

I'nP та       - інтервали відповідно прибуття та відправлення на n станції між поїздом, що прокладається, та p поїздом. Вхідні дані:

•   1, ..., n, ..., N - номери станцій ділянки, по якій рухається поїзд;

1, ., p, ., P - номери прокладених в графіку поїздів;

дані про вже прокладені в графіку поїзди:      ,      , (1 < n < N, 1 < p < P -1);

• тягово-енергетичні розрахунки руху поїзда: tn , Тр , T, (1 < n < N — 1) ;

інформація про тривалості стоянок поїзда: Tn , Tn, j;

інформація про кількість колій на станціях дільниці: Rn , (1 <n <N) ;

• «прив'язка поїзда до станції»: n   - номер станції прив'язки, Тв!д (або T"?) - час відправлення (або прибуття) поїзда з станції n .

Алгоритм прокладання поїзда

Розглянемо випадок відправлення поїзда зі станції прив'язки п .

1. Перевіряємо, чи є вільна станційна колія на станції п в інтервалі часу (т"д - т™, т"д).

R* < R

n',(Tf -тТ jf )

Якщо нерівність не виконується, то збільшуємо Твд і переходимо до пункту 1.

2. Прокладаємо поїзд через станції п +1,...,N . Нехай t = Твд . Для кожного п (п +1 < п < N) виконуємо наступне:

2.1. Перевіряємо чи виконуються умови відправлення поїзда зі станції п-1.

У множині прокладених в графіку поїздів знаходимо «сусідні» для даного на цій станції. Це поїзди, які прибувають на станцію (чи відправляються з неї) до і після відправлення даного поїзда;

по парі поїздів на кожну горловину станції. Нехай p'~-1 k та p'r+-1 k (1 < k < Кп-1) - номери цих

поїздів відповідно.

Для кожного p є {p'~-hk 1 < k < Кп-1} перевіряємо умову Tn-lpp +     p < t.

Для кожного p є{p'n+-hk 1 < k < Kn-1} перевіряємо умову t < Tn-hp + Гпp .

Зауваження. Між поїздами з деяких горловин (незалежних з даною) і даним поїздом може і не виникати інтервалів (станційних; міжпоїздні взагалі виникають тільки між поїздами, що слідують через одну горловину). У таких випадках ці поїзди не розглядаються (Іп-1   = 0).

У випадку невиконання однієї з цих умов переходимо до пункту 3.1.

Збільшуємо t на tn-1 + тгп_х + тсп (додаткові часи враховуються тільки у випадку зупинок на

відповідних станціях).

2.2. Перевіряємо виконання умов прибуття поїзда на станцію п.

Знаходимо поїзди p'~k та p'n+k (1 < k < Кп) (див. п.2.1).

Для кожного p є {pp~k 1 < k < Кп} перевіряємо умову Tnp + IlPp < t.

Для кожного p є {p'i+k 1 < k < Кп} перевіряємо умову t < Тп p + Іпрр .

У випадку невиконання однієї з цих умов переходимо до пункту 3.2.

2.3. Перевіряємо, чи є вільна станційна колія на станції п.

n,(t,t+fnm ) п .

Якщо ця умова не виконується, то переходимо до пункту 3.3. Збільшуємо t на .

Якщо для кожного п (п +1 < п < N) всі підпункти пункту 2 виконуються, то переходимо до пункту 4.

3. У випадку невиконання однієї з умов в пункті 2:

Якщо часи стоянок поїзда на станціях фіксовані, то збільшуємо Твд і переходимо до пункту 1.

Якщо часи стоянок можна збільшувати, то переходимо до одного з підпунктів (залежно від того, яка з умов пункту 2 не виконується).

3.1. (не виконується умова відправлення поїзда зі станції п.) Якщо ця станція не є станцією «прив'язки»:

п Ф п

і є можливість збільшити час стоянки на ній на Аст (є вільна станційна колія):

R < R

n,(t,t+тспт +Аст) п

то збільшуємо час стоянки.

Якщо одна з цих умов не виконується, то збільшуємо Твд . Переходимо до пункту 1.

3.2. (не виконується умова прийняття поїзда на станцію п.) Якщо ця станція не є наступною після станцієї «прив' язки»:

п Ф п +1

і є можливість збільшити час стоянки на попередній станції на Аст (є вільна станційна колія):

R* < R

n-1,(t,t+тст1+Аст)        п-1 ,

то збільшуємо час стоянки.

Якщо одна з цих умов не виконується, то збільшуємо Твд .

Переходимо до пункту 1.

3.3. (немає вільної колії на станції п.) Дії, аналогічні до пункту 3.2.

4. Прокладаємо поїзд через станції 1,...,п -1.

Нехай t = 7\    п' .

Для кожного п від п -1 до 1 виконуємо наступне:

4.1. Перевіряємо умови прибуття на станцію п +1 . Перевірка аналогічна до перевірки у пункті 2.2.

У випадку невиконання умов переходимо до пункту 5.1.

Зменшуємо t на tn +тр + тсп (додаткові часи враховуються тільки у випадку зупинок на

відповідних станціях).

4.2. Перевіряємо умови відправлення зі станції п. Перевірка аналогічна до перевірки у пункті 2.1.

У випадку невиконання умов переходимо до пункту 5.2.

4.3. Перевіряємо, чи є вільна колія на на станції п.

Якщо ця умова не виконується, то переходимо до пункту 5.3. Зменшуємо t на тс™ .

5. У випадку невиконання однієї з умов в пункті 4:

Якщо часи стоянок поїзда на станціях фіксовані, то збільшуємо Твд і переходимо до пункту 1.

Якщо часи стоянок можна збільшувати, то переходимо до одного з підпунктів (залежно від того, яка з умов пункту 4 не виконується).

5.1. (не виконується умова прийняття поїзда на станцію п.)

Якщо є можливість збільшити час стоянки на даній станції на Аст (є вільна станційна колія):

R* < R

n,(t-(-Г™ +Аст ),t)        п ,

то збільшуємо час стоянки.

Якщо ні, то збільшуємо Твд . Переходимо до пункту 1.

5.2. (не виконується умова відправлення поїзда зі станції п.)

Якщо є можливість збільшити час стоянки на наступній станції на Аст (є вільна станційна колія):

п+1,(t-(іП™ +Аст ),t ^    n+1 ,

то збільшуємо час стоянки.

Якщо одна з цих умов не виконується, то збільшуємо Твд .

Переходимо до пункту 1.

5.3. (немає вільної колії на станції п.) Дії аналогічні до пункту 5.2.

Рис. 1. Алгоритм прокладання поїзда у випадку, коли "станція прив'язки" є початковою

Процес повторюється доти, доки всі кроки не будуть успішними (поїзд прокладено) або час відправлення не занадто збільшиться (поїзд не вдолось прокласти).

Алгоритм прокладання поїзда у випадку прибуття на станцію п є аналогічним до описаного вище. Істотною відмінністю є те, що час прив'язки у цьому випадку зменшують, а не збільшують.

Страницы:
1  2 


Похожие статьи

М Притула, Р Шпакович - Алгоритм побудови графіка руху поїздів