Моделювання залежних від часу проблем пошуку оптимальних маршрутів: огляд
Розглянуто задачі пошуку оптимальних маршрутів мережами громадського транспорту. Наведено підходи до подання розкладу за допомогою графів у залежних від часу задачах пошуку оптимальних шляхів для залізничних і авіамереж. Проаналізовано типові задачі пошуку оптимальних шляхів у залежних від часу мере...
Saved in:
| Published in: | Математичне моделювання в економіці |
|---|---|
| Date: | 2017 |
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут телекомунікацій і глобального інформаційного простору НАН України
2017
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/131908 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Моделювання залежних від часу проблем пошуку оптимальних маршрутів: огляд / Л.Ф. Гуляницький, А.І. Павленко // Математичне моделювання в економіці. — 2017. — № 1-2(8). — С. 102-116. — Бібліогр.: 10 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860247103099371520 |
|---|---|
| author | Гуляницький, Л.Ф. Павленко, А.І. |
| author_facet | Гуляницький, Л.Ф. Павленко, А.І. |
| citation_txt | Моделювання залежних від часу проблем пошуку оптимальних маршрутів: огляд / Л.Ф. Гуляницький, А.І. Павленко // Математичне моделювання в економіці. — 2017. — № 1-2(8). — С. 102-116. — Бібліогр.: 10 назв. — укр. |
| collection | DSpace DC |
| container_title | Математичне моделювання в економіці |
| description | Розглянуто задачі пошуку оптимальних маршрутів мережами громадського транспорту. Наведено підходи до подання розкладу за допомогою графів у залежних від часу задачах пошуку оптимальних шляхів для залізничних і авіамереж. Проаналізовано типові задачі пошуку оптимальних шляхів у залежних від часу мережах.
Рассмотрены задачи поиска оптимальных маршрутов сетями общественного транспорта. Приведены подходы для представления расписания с помощью графов в зависимых от времени задачах поиска оптимальных путей для железнодорожных и авиасетей. Проанализированы типовые задачи поиска оптимальных путей в зависимых от времени сетях.
We consider the problem of optimal dynamic time-dependent route planning in public transport networks. The paper describes approaches to represent schedule within graphs for the time-dependent shortest path problems in rail and air networks. Common types of timedependent shortest path problems in dynamic networks are reviewed.
|
| first_indexed | 2025-12-07T18:38:19Z |
| format | Article |
| fulltext |
~ 102 ~
Математичне моделювання в економіці, №1-2, 2017
УДК 004.8:519.85:656.7
Л.Ф. ГУЛЯНИЦЬКИЙ, А.І. ПАВЛЕНКО
МОДЕЛЮВАННЯ ЗАЛЕЖНИХ ВІД ЧАСУ ПРОБЛЕМ ПОШУКУ
ОПТИМАЛЬНИХ МАРШРУТІВ: ОГЛЯД
Анотація. Розглянуто задачі пошуку оптимальних маршрутів
мережами громадського транспорту. Наведено підходи до подання
розкладу за допомогою графів у залежних від часу задачах пошуку
оптимальних шляхів для залізничних і авіамереж. Проаналізовано
типові задачі пошуку оптимальних шляхів у залежних від часу
мережах.
Ключові слова: динамічна задача пошуку, найкоротший шлях,
оптимальний маршрут, мережі громадського транспорту, time-
dependent model, time-expanded model.
Вступ
Перші електронні системи розкладу з’явились наприкінці 80-х років
минулого століття у Німеччині. До того часу планування маршрутів
відбувалось «вручну» з використанням друкованих довідників. Такий підхід
прийнятний для невеликих транспортних мереж, проте довідник розкладів
німецьких залізниць “Kursbuch”у 1957 році вже налічував 1272 сторінки, що
спонукало до розробки більш ефективних пошукових систем [1]. До сучасних
представників таких систем належать HAFAS [2], яка використовується
багатьма європейськими залізницями, EFA [3], яка в основному
використовується локальними перевізниками Європи. Досвід роботи з ними
показав, що системи видають задовільні результати в більшості випадків,
хоча інколи запропоновані маршрути є неоптимальними. Основною
причиною цього явища є використання простих евристичних алгоритмів, які
здійснюють частковий перегляд простору розв’язків для отримання
результатів за прийнятний час, що не гарантує отримання оптимальних
розв’язків. Останніми роками активно ведуться дослідження моделей і
алгоритмів розв’язування практичних задач пошуку оптимальних шляхів із
врахуванням наявних обмежень. Метою роботи є дослідження підходів до
розв’язування типових задач пошуку оптимальних шляхів громадським
транспортом з урахуванням розкладу. Для цього розглянуто підходи до
подання розкладу руху громадського транспорту у вигляді графа для
подальшого застосування розроблених методів пошуку оптимальних шляхів
у графах.
Далі наведено огляд підходів до пошуку найкоротших шляхів у заданому
графі з урахуванням інформації про розклад руху.
1. Загальна постановка задачі пошуку оптимального шляху громадським
транспортом
Зазвичай для таких задач у заданій мережі відомі початковий пункт
відправлення sp та кінцевий tp і необхідно знайти оптимальний шлях із sp
Ó Л.Ф. Гуляницький, А.І. Павленко, 2016
~ 103 ~
Математичне моделювання в економіці, №1-2, 2017
в tp . Причому, якщо для (статичних) мереж автомобільного транспорту
поняття оптимальності є доволі прозорим (мінімізація часу подорожі), то для
розгалужених мереж громадського транспорту критерій зазвичай включає
кілька факторів. Маршрути для громадського транспорту повинні
враховувати часові параметри, оскільки шуканий оптимальний шлях
залежить від часу його реалізації.
Ключовою відмінністю мереж громадського транспорту від автомобільних
є наявність залежності від часу, адже деякі сегменти мережі стають
досяжними тільки у визначені моменти часу. Тому початковим завданням
при розв’язуванні залежних від часу задач пошуку найкоротших шляхів є
подання розкладу у графі задачі. Існують два основні підходи для подання
розкладів у мережах – time-expanded (розширений за часом) і time-
dependent (залежний від часу) [4, 5].
Розклад руху транспорту подається множиною зупинок (автобусні
зупинки, залізничні платформи, аеропорти тощо), множиною маршрутів
слідування (автобусні, трамвайні, залізничні маршрути тощо). Маршрут
слідування – послідовність зупинок, які повинен відвідати транспортний
засіб в конкретний час, являє собою множину елементарних сполучень.
Елементарне сполучення визначається двома зупинками, між якими курсує
транспортний засіб, а також часом відправлення і прибуття.
Розклад подамо п’ятіркою ),,,,( FTS ÂP=Á , де 0³ÌP Z – період події
(визначається як часовий інтервал протягом дня), 0³Z – множина цілих
невід'ємних чисел, S – множина зупинок (автобусних, аеропортів,
залізничних платформ), T – упорядкована множина елементарних сполучень
(сегментів) маршруту слідування транспортного засобу, Â – множина
маршрутів слідування, F – множина додаткових переходів (трансферів або
пересадок). Елементи PÎt називають моментами часу. Кожній зупинці p в
маршруті t відповідає час прибуття PÎ),( ptarrt і відправлення
транспортних засобів PÎ),( ptdept , ),(),( ptpt deparr tt £ . Кожний трансфер
містить дві зупинки 1p і 2p з відповідним заданим часом переходу ),( 21 ppl .
Кожній зупинці p відповідає мінімальний час посадки )(pcht (наприклад,
процедура посадки на рейс в межах аеропорту займає деякий час).
Елементарні сполучення. Із заданого розкладу Á , як зазначалося, можна
визначити множину елементарних сполучень C . Елементарні сполучення є
найменшими елементами, на які можна декомпозувати розклад. Більш
формально, елементарне сполучення CcÎ є кортежем
),,,,( arrdeparrdep pptc tt= , що позначає проїзд TtÎ із зупинки Spdep Î
в час PÎdept до зупинки Sparr Î з прибуттям в час PÎarrt . Для
спрощення, функція )(cx визначає компонент x кортежу с (наприклад,
)(cdept позначає час відправлення сполучення с ).
Маршрути. Результатом роботи алгоритмів пошуку оптимального шляху
є множина маршрутів J . Маршрут – впорядкована послідовність
~ 104 ~
Математичне моделювання в економіці, №1-2, 2017
елементарних сполучень (сегментів) і пересадок у певній подорожі. Кожному
сегменту послідовності відповідає пара зупинок – посадки і висадки.
Маршрут з k сегментами має 1-k трансферів. Маршрутам відповідають
деякі критерії оптимальності. Вважатимемо, що маршрут 1J домінує над 2J
в сенсі заданого критерію ефективності, якщо 1J не гірший ніж 2J , 21 JJ p .
На рис. 1 зображено приклад трьох маршрутів із зупинки sp в tp . Час
відправлення 00:9=t . Надписи позначають час відправлення і прибуття
між деякими сегментами маршрутів слідування. В наступних розділах
наведено опис типових задач для подібних розкладів.
Рисунок 1 – Схема трьох маршрутів з зупинки sp в tp і часом відправлення
00:9=t
2. Типові задачі пошуку оптимального шляху громадським транспортом
Наведемо огляд деяких типових задач пошуку маршрутів із урахуванням
розкладу громадського транспорту, базуючись на роботах [4, 6, 7].
2.1 Задача пошуку маршруту з найранішим часом прибуття (earliest
arrival problem)
Дано розклад громадського транспорту, початковий пункт sp і кінцевий
пункт tp , час відправлення t . Необхідно знайти маршрут, який
відправляється з пункту sp не раніше t і прибуває в tp якомога раніше.
Якщо замість моменту часу задано часовий інтервал, то необхідно знайти усі
оптимальні шляхи з відправленням у межах заданого інтервалу. Така задача
називається range problem. Окрім критерію тривалості маршруту, інколи
важливим критерієм є загальна вартість проїзду. Таким чином, намагаються
знаходити Паретівську множину маршрутів.
2.2. Задача пошуку маршруту з найменшим загальним часом подорожі і
найранішим часом прибуття (tight earliest arrival problem)
На рис. 1 зображено три маршрути з відправленням з 9:00 з однаковим
мінімальним часом прибуття в кінцевий пункт о 20:20. Проте на практиці
маршрути не вважають рівноцінними, адже в деяких з них є значний час
очікування між пересадками, що збільшує загальний час подорожі.
~ 105 ~
Математичне моделювання в економіці, №1-2, 2017
Якщо необхідно знайти маршрут з найранішим часом прибуття і
мінімальним часом подорожі, то говорять про tight earliest arrival problem –
задачу з «найщільнішим» маршрутом і найранішим прибуттям.
Дано розклад громадського транспорту, початковий пункт sp і кінцевий
пункт tp , час відправлення t . Необхідно знайти маршрут, який
відправляється з sp якомога пізніше, але не раніше t , і прибуває в tp
якомога раніше. На рис. 1 найщільніший маршрут – відправитись о 18:45,
продовжити подорож з пересадкою о 19:00, пересадкою о 20:00.
Якщо, окрім часу подорожі, необхідно враховувати інші критерії при
визначенні оптимального шляху (кількість трансферів, вартість проїзду
тощо), то говорять про багатокритеріальну задачу.
2.3. Задача пошуку маршруту в заданому періоді (range problem)
Як вхідні дані замість часу відправлення з початкового пункту задається
часовий інтервал, в рамках якого розраховуються оптимальні маршрути.
Дано розклад громадського транспорту, початковий пункт sp і кінцевий
пункт tp , часовий інтервал подорожі PÍD . Необхідно знайти маршрут,
який відправляється з sp не раніше t і прибуває в tp якомога раніше, тобто
необхідно знайти множину оптимальних маршрутів, причому для кожного
моменту відправлення DÎt існує маршрут JJ Ît з відправленням
з пункту sp не раніше t і прибуттям в tp якомога раніше. Якщо період
подорожі D співпадає з періодом розкладу, то говорять про задачу
профілювання (profile problem).
2.4. Обернені задачі
Для всіх викладених вище задач можна сформулювати обернені задачі.
Наприклад, для задачі пошуку маршруту з найранішим часом прибуття
оберненою є задача з найпізнішим часом відправлення. Дано розклад руху
громадського транспорту, початковий пункт sp і кінцевий пункт tp , а також
час прибуття t . Необхідно знайти маршрут, який прибуває в tp не пізніше
t , а відправляється з sp якомога пізніше. Аналогічно можна сформулювати
інші задачі.
3. Моделі подання графів для задач пошуку оптимальних шляхів на
залізниці
Існує два основних підходи до подання розкладу у графі для розв’язування
залежних від часу задач – розширений за часом граф (time-expanded) і
залежний від часу граф (time-dependent). Ідея першого підходу полягає у
створенні вершини для кожної події розкладу (подія – відправлення або
прибуття транспорту); це призводить до графів великої розмірності.
~ 106 ~
Математичне моделювання в економіці, №1-2, 2017
У залежному від часу графі сегменти подорожі подаються однією дугою. Для
деяких методів пошуку шляхів у графі на етапі будується модель із
урахуванням зупинок – так звана модель зупинок (stop model).
3.1. Модель зупинок (Stop Model)
Найпростішою моделлю для подання розкладу є модель зупинок –
відображення графа станцій або топологічне подання транспортної мережі.
Будується граф ),( AVG = , V – множина вершин, А – множина дуг, де кожна
вершина з множини з V відповідає зупинці SpÎ з розкладу. Для
спрощення, вважатимемо VpÎ . В множину А додається дуга )( ji pp з
вершини ip в jp , якщо розклад містить елементарне сполучення з вершини
ip в jp , тобто якщо існує елементарне сполучення CcÎ , для якого
idep pсp =)( і jarr pсp =)( . Вартість ),( ji ppl дуги )( ji pp – мінімальний
час подорожі серед усіх елементарних сполучень з ip в jp , тобто:
{ }jarrideparrdepji pcpіpcpіCcccppl ==Î= )()(|))(),((min),( ttd ,
де ))(),(( cc arrdep ttd – тривалість руху елементарним сполученням.
Модель зупинок є дуже простою, але, на жаль, вона не враховує часову
залежність розкладу. Вартість дуг визначається мінімальним часом подорожі
між зупинками, тому знайдені у такому графі найкоротші шляхи є лише
нижньою межею для реального часу подорожі. Описані залежні від часу
задачі не можуть бути розв’язані з застосуванням моделі зупинок, але її
використовують для етапів попередньої обробки з метою пришвидшення
пошуку.
3.2. Розширена за часом модель (Time-Expanded Model)
Проста модель. Дано розклад Á і множину елементарних сполучень C . Для
кожного сполучення СсÎ будується пара вершин, з’єднаних дугою; )(cudep
і )(cuarr – пункти відправлення і прибуття сполучення с . Вершинам завжди
неявно відповідають значення часу )(ut . В нашому випадку час у вершині
відправлення )(cudep задається часом відправлення відповідного сполучення
)(cdept , а час у вершині прибуття )(cuarr задається величиною )(carrt .
Аналогічно, кожній вершині може відповідати значення простою )(up .
Між вершинами )(cudep і )(cuarr додається дуга ))(),(( cucu arrdep . Для
кожної зупинки SpÎ для врахування можливості здійснення пересадки
(очікування) створюються додаткові дуги в порядку зростання часу. Тобто,
дуга пересадки ( , )u v (або очікування – transfer arc) існує між відповідними
~ 107 ~
Математичне моделювання в економіці, №1-2, 2017
вершинами тільки тоді, коли )()( vpup = , )()( vu tt £ і не існує іншої
вершини w , для якої )()( upwp = і )()()( vwu ttt << . Пересадочним
дугам відповідають значення різниці часу інцидентних їм вершин,
))(),((),( vuvul ttd= . Якщо для деякої зупинки існує кілька сполучень
з відправленням в один час, тоді вершини відправлення можна об’єднати
в одну. Таким чином, розширений за часом граф G є ациклічним. В тому
випадку, коли розклад є періодичним, для кожної зупинки додається дуга
( , )u v з найпізнішої до найранішої вершини зупинки, дозволяючи переходи
з одного періоду розкладу до іншого. Звичайно, в такому випадку граф стає
циклічним.
Зазвичай така модель приводить до дуже великого, але розрідженого
графу. На рис. 2 зображено просту розширену за часом мережу з однією
зупинкою, чотирма сполученнями для трьох сегментів 1t , 2t , 3t . Вершина
з горизонтальною штриховкою є вершиною прибуття, а вершини
з вертикальною штриховкою – відправлення. Вершини зображені в порядку
зростання часу зверху донизу.
Рисунок 2 – Проста розширена за часом модель графу
Незважаючи на розмірність графу, така модель може застосовуватись для
розв’язування задач пошуку оптимальних шляхів класичними методами для
графів малих розмірностей.
Реалістична модель. На відміну від простої моделі, в моделі, яка
в літературі отримала назву реалістичної моделі, враховується необхідність
мінімального часу для пересадки на станціях. Для подання розкладу у вигляді
графу використовуються три типи вершин: вершини відправлення )(cudep ,
прибуття )(cuarr та пересадки )(cutransfer . Тобто для кожної події
відправлення створюється одна пересадочна вершина )(cutransfer , з’єднана
з відповідною вершиною відправлення )(cudep (зупинка, що відповідає
вершині пересадки співпадає з зупинкою, що відповідає вершині
відправлення )())(( cpcup deptransfer = ). Вага дуги, що відображує сполучення
між пересадочною вершиною і вершиною відправлення, рівна нулю.
~ 108 ~
Математичне моделювання в економіці, №1-2, 2017
Для забезпечення мінімального часу пересадки на станціях створюються
додаткові дуги між кожною парою вершин прибуття depu і вершиною
першого можливого трансферу v , причому )()()( vpu transfer ttt £+ , де
)( ptransfert – час пересадки.
Для забезпечення можливості залишатися в тому ж транспортному засобі
(наприклад, потязі) на проміжних зупинках створюється додаткова дуга, яка
з’єднує вершину прибуття і відповідну вершину відправлення, які
відповідають маршруту одного потягу.
На рис. 3 подано реалістичну модель розширеного за часом графу. Він
містить такі ж рейси і сполучення, як і на рис. 2. Вершини прибуття позначені
горизонтальною штриховкою, вершини відправлення позначені
вертикальною штриховкою, пересадочні вершини позначені діагональною
штриховкою. Очевидно, що пересадка між 1t і 2t неможлива за критерієм
мінімального часу пересадки (хоча продовження подорожі рейсом 1t
можливе). Таку ситуацію не можна подати графом простої моделі.
Рисунок 3 – Реалістична модель розширеного за часом графу
Основною перевагою розширеного за часом графу є його незалежність від
часу, тобто дуги мають фіксовану вагу. Ця перевага робить можливим
застосування класичних методів пошуку найкоротших шляхів.
3.3. Залежна від часу модель (Time-Dependent Model)
У даному підході граф містить по одній вершині на кожну зупинку. Якщо
між зупинками є сполучення, то в графі між відповідними вершинами
додається дуга. В якості вартості дуг використовуються залежні від часу
функції тривалості подорожі (time-dependent travel time functions). Аналогічно
попередній моделі, існують два варіанти – проста і реалістична.
В реалістичній моделі береться до уваги час пересадок.
3.4. Залежні від часу функції тривалості подорожі (Travel Time Functions)
Ключова ідея залежної від часу моделі (time-dependent model) – побудова
залежного від часу графу [8] шляхом комбінації кількох елементарних
~ 109 ~
Математичне моделювання в економіці, №1-2, 2017
сполучень в єдину дугу за допомогою залежних від часу функцій тривалості
(вартості) подорожі. Вартість дуг, що відображають сполучення, залежить
від часу запиту. На рис. 4 зображена функція тривалості подорожі: кожна
точка відображує елементарне сполучення; лінійні сегменти (з нахилом o45-
до горизонтальної осі) відображують не тільки час подорожі, а і час
очікування до наступного відправлення. Введемо простір функцій F , який
складається з функцій часу подорожей у вигляді: 0: ³®P Zf . Кожна
функція FÎf переводить час відправлення у час подорожі (або вартість).
Час відправлення обирається з інтервалу P – період операції у розкладі, час
подорожі може приймати довільні невід’ємні цілі числа (з огляду на прибуття
після півночі).
Функції розкладу. Таким чином, кожне елементарне сполучення CcÎ ,
якому відповідає функція f , створює точку сполучення
)))(),((),(( cccq arrdepdepc ttdt= , причому оцінка f в час відправлення
)(cdeptt = відповідає часу подорожі ))(),(()( ccf arrdep ttdt = . Для простоти
час відправлення і час подорожі точки сполучення q позначимо )(qdept
і )(qtransfert . Нехай fP – множина точок сполучення функції f . Значення f
між послідовними точками сполучення отримують шляхом інтерполяції через
очікування. Нехай PÎt – довільний час відправлення і q – наступна точка
сполучення, тобто точка сполучення з мінімальним ))(,( qdepttd . Для
визначення значення функції f в час t застосовують формулу:
))(,()()( qqf deptransfer ttdtt += .
Зазначимо, що якщо точки сполучення функції f впорядковані за часом
відправлення, оцінка f має трудомісткість )(log fPO при бінарному
пошуці та )( fPO – при простому лінійному пошуці.
Щоб моделі були коректними, функції часу подорожі повинні
задовольняти принципу FIFO ("first in – first out") – "першим пройшов –
першим обслуговується". В контексті точок сполучення це інтерпретується
так: не повинно існувати жодних послідовних точок сполучень Pqq Î21, ,
таких щоб виконувалась умова )()())(),(( 1211 qqqq transittransitdepdep ttttd £+ .
Іншими словами, пропуск 1q і очікування в пункті 2q не повинні зменшувати
загальний час подорожі.
На рис. 4 зображено вісім точок сполучення. Крайня права точка
сполучення порушує властивість FIFO і тому не включається в f .
~ 110 ~
Математичне моделювання в економіці, №1-2, 2017
Рисунок 4 – Типова форма подання функції тривалості подорожі
Операцію з’єднання (link operation) двох функцій 1f і 2f можна
ефективно реалізувати лінійним алгоритмом розгортання (linear sweep
algorithm). Для кожної точки сполучення 1q з 1f шукається така точка
сполучення 2q з 2f , щоб мінімізувати ))(),()((ˆ
211 qqqd deptradep tttd += ,
і додається точка сполучення ))(ˆ),(( 21 qdqq tradep tt += . Якщо не існує
належної 2q , то додаткова точка сполучення не створюється. Також не
додаються точки сполучення, які порушують властивість FIFO.
Операція злиття (merge operation) двох функцій 1f і 2f може бути
реалізована лінійним пошуком. Результуюча функція базується на об’єднанні
21 ff PP U кожної точки сполучення функції, окрім тих, що порушують
властивості FIFO.
Проста модель. Розглянемо просту залежну від часу модель мережі. Дано
розклад Á і відповідна множина елементарних сполучень C . Модель
використовує направлений граф ),( AVG = , в якому кожна вершина Vup Î
відповідає зупинці SpÎ . До множини A додаються дуги ),( 21 pp тільки
в тому випадку, якщо існує елементарне сполучення з 1p в 2p , тобто
1)( pсpdep = і 2)( pсparr = . Вартості дуг визначаються в термінах функцій
часу подорожі, тобто FAl ®: . Отже, кожна дуга App Î),( 21 містить саме
ті точки сполучення, які відповідають елементарним сполученням з 1p в 2p .
Точки сполучення, які порушують FIFO властивість, можуть бути відкинуті
або розташовані на окремій паралельній дузі. На рис. 5 зображена проста
модель графу, залежного від часу з трьома зупинками 1p , 2p , 3p , а також
рейсами 1r , 2r , 3r .
~ 111 ~
Математичне моделювання в економіці, №1-2, 2017
Рисунок 5 – Проста залежна від часу модель
Реалістична модель. Замість створення єдиної вершини для кожної
зупинки, в такій моделі створюються декілька. Модель ґрунтується на тому
судженні, що пересадки на одному і тому ж рейсі не бувають оптимальними.
Таким чином, модель групує елементарні сполучення по рейсу. Нехай p –
множина маршрутів, що проходять через зупинку SpÎ . В моделі
створюються вершини зупинок VpÎ (як і раніше), але додатково
створюються вершини маршрутів pr для кожної вершини маршруту з p .
Для кожного маршруту (рейсу) ÂÎr і двох послідовних задіяних по
маршруту зупинок Spp ji Î. створюється залежна від часу дуга маршруту
Arr
ji pp Î),( . Залежна від часу функція часу подорожі по створеній дузі
містить точку сполучення, причому для кожного її елементарного сполучення
CcÎ виконуються умови idep pсp =)( , jarr pсp =)( , rсr =)( . Аналогічно
до попередніх моделей, не-FIFO точки сполучення відхиляються або
розміщуються на окремих паралельних дугах. Для відображення пересадок
між різними маршрутами додаються дуги пересадок, які поєднують вершини
зупинок і усі відповідні вершини маршруту. Отже, додаються дуги ),( prp і
),( prp з постійним значенням вартості для кожної зупинки ppr ÂÎ . Модель
враховує мінімальний час пересадки, при цьому встановлюється
)(),( prpl chp t= для усіх дуг, що ведуть з вершини зупинки до вершин
маршруту, де )(pcht – мінімальний час пересадки на зупинці p . Відповідно,
0),( =prl p для усіх дуг, що ведуть з вершин маршруту до вершини зупинки.
На рис. 6 зображена реалістична залежна від часу модель графу. Вершини
маршруту позначені кружечками і ромбами, числа над стрілками показують
час пересадки на інший маршрут.
~ 112 ~
Математичне моделювання в економіці, №1-2, 2017
Рисунок 6 – Реалістична модель
3.5. Модель розфарбування (Coloring Model)
Реалістична залежна від часу модель застосовується для гарантії того, що
кінцевий маршрут не матиме некоректних пересадок в рамках одного рейсу.
Проте таку поведінку можна забезпечити, ввівши поняття конфліктуючих
сегментів. Нехай є два елементарні сегменти 1t і 2t , які відносяться до
зупинки p . Нехай ),( 1 ptarrt – час прибуття на зупинку p транспортом
із сегменту 1t , ),( 2 ptdept – час прибуття на зупинку p транспортом
із сегменту 2t . Ці сегменти є конфліктуючими в тому і тільки тому випадку,
коли 2t прибуває після відправлення 1t або часовий резерв для пересадки
менший необхідного. Формально, 1t і 2t є конфліктуючими тоді і тільки тоді,
коли виконуються нерівності ),(),( 12 ptpt arrdep tt ³ і
),()(),( 21 ptppt depcharr ttt ³+ . В такому випадку об’єднання 1t і 2t в одній
вершині маршруту призведе до появи некоректного маршруту, чого потрібно
уникати.
В результаті перевірки конфліктності всіх пар сегментів подорожі, які
відповідають зупинці p , створюється ненаправлений граф конфліктів
))(),(()( *** pApVpG = . Множина вершин TpV Í)(* містить саме ті
сегменти TtÎ , які відповідають зупинці p . Дві пари вершин )(, * pVtt ji Î
поєднуються дугою { } )(, * pAtt ji Î тільки тоді, коли it і jt є
конфліктуючими.
Розфарбування вершин графу )(* pG (тобто кожній вершині надається
деякий колір), в якому у жодних двох суміжних вершин не співпадає колір,
породжує набір вершин зупинки p в моделі графу G . Нехай K –
мінімальна кількість унікальних кольорів, використаних для розфарбування
)(* pG , тоді для кожного кольору Kk ,...,1= створюється вершина u в графі
~ 113 ~
Математичне моделювання в економіці, №1-2, 2017
G і до неї додаються ті сегменти, що мають присвоєний колір k в ).(* pG
Приклад графу конфліктів і породженого ним підграфу залежної від часу
моделі наведено на рис. 7.
Рисунок 7 – Граф конфліктів (зліва), модель результуючого графу (справа)
4. Моделі подання графів в задачах пошуку оптимальних шляхів
авіаперельотів
4.1. Вхідні дані
Подання розкладів для авіамереж подібне мережам залізничних шляхів –
в обох випадках використовується періодичний графік руху транспорту,
а оптимальні сполучення залежать від часу відправлення. Однак застосування
розглянутих в попередньому розділі моделей для авіамереж призводить до
побудови надлишково великих графів. На відміну від залізничних мереж,
авіамережі сполучення (маршрути) між аеропортами є елементарними, тобто
літаки не мають проміжних зупинок в інших аеропортах. Тому було
доцільним розробити специфічні моделі для авіа мереж [9].
Авіарозклад подається вектором ),,,,( zÂP=Á CS , де 0³ÌP Z –
часовий період, S – множина аеропортів, С – множина елементарних
сполучень (сегментів, рейсів) між аеропортами, Â – множина маршрутів,
ZS ®:z – функція співставлення часового поясу для кожного аеропорту.
Елементарне сполучення CcÎ – вектор ),,,,( arrdeparrdep pprc tt= , тобто
літак маршруту ÂÎr відправляється з аеропорту Spdep Î в час dept і
прибуває в аеропорт Sparr Î в час arrt . Час dept і arrt повинні відповідати
часовим поясам аеропортів Spdep Î і Sparr Î .
Часто маршрут і елементарне сполучення (рейс) є еквівалентними, проте
в деяких випадках існують рейси з пересадками. Вони відрізняються від
послідовності незалежних рейсів тим, що пасажирам необхідно перейти
в інший літак, а перевірки безпеки і вихід з аеропорту зазвичай не
передбачуються. Довжина авіамаршрутів є значно меншою, ніж для
залізничних напрямів.
Недоліки застосування моделей залізничного транспорту до
авіамереж. Якщо застосовувати реалістичну залежну від часу модель
залізничних мереж для подання авіамережі, то для кожного елементарного
~ 114 ~
Математичне моделювання в економіці, №1-2, 2017
сполучення необхідно додати дві вершини маршруту при побудові дуги між
вершинами аеропортів.
Окрім того, на відміну від залізничних мереж з відносно невеликою
кількістю суміжних станцій для кожної зупинки (рис. 1), для авіамереж
характерна велика кількість суміжних аеропортів. Таким чином, для подання
кожного аеропорту в граф додаються надлишкові вершини маршруту.
Відмінність умов реалістичних моделей. Реалістичні події, що
враховуються для залізниць на станціях, не відповідають реалістичним
подіям в аеропортах. Наприклад, в аеропортах, окрім часу трансферу,
необхідно враховувати реєстрацію і перевірки безпеки перед відправленням,
перевірки документів після прибуття, отримання багажу тощо.
Часові функції авіамереж. Розглянемо часові функції, що відповідають
реалістичним подіям авіамереж:
0: ³® RScit – необхідний час на чекін (всі обов’язкові процедури
з моменту прибуття в аеропорт до моменту відправлення літака – перевірки
документів, посадка на борт тощо);
0: ³® RScot – необхідний час на чекаут (всі обов’язкові процедури
з моменту посадки літака);
0: ³® RStransfert – необхідний час на трансфер в разі пересадки на інший
літак,
де 0³R – множина дійсних невід’ємних чисел.
4.2 Реалістична модель авіамереж зі сталим часом специфічних процедур
Для подання кожного аеропорту SpÎ в граф додається одна термінальна
вершина, а для кожної термінальної вершини додається вершина прибуття
і відправлення. Таким чином, кількість додаткових вершин зменшується
порівняно із застосуванням попередніх моделей. Також для кожного
аеропорту SpÎ додаються три дуги: дуга чекіну з вагою )( pcit між
термінальною вершиною і вершиною відправлення, дуга чекауту з вагою
)(pcot між вершиною прибуття і термінальною вершиною, дуга трансферу
з вагою )( ptransfert між вершинами прибуття і відправлення. Власне, для
кожного рейсу додається дуга перельоту із залежною від часу вагою )(cl
з вершини відправлення depp до вершини прибуття arrp .
Приклад моделі наведено на рис. 8. Термінальні вершини позначені
більшими кружечками (щільна штриховка), вершини відправлення мають
вхідну дугу з термінальної вершини (вертикальна штриховка), вершини
прибуття мають вихідну дугу до термінальної вершини (горизонтальна
штриховка). Дуги зі сталою вагою позначені тонкими лініями, а із залежною
від часу (дуги перельотів) – товстими лініями.
~ 115 ~
Математичне моделювання в економіці, №1-2, 2017
Рисунок 8 – Модель авіамережі зі сталим часом для процедур чекіну, чекауту,
трансферу
4.3 Реалістична модель авіамереж із врахуванням класу рейсів
В попередній моделі вважається, що час чекіну, чекауту і трансферу для всіх
рейсів однаковий. Насправді для різних авіакомпаній і типу рейсів (регіональні
або міжнародні) час деяких процедур суттєво відрізняється. Для врахування
цього факту введемо поняття класу рейсу. Множину класів рейсів позначимо
Q . Тоді 0: ³®Q´ RScit , 0: ³®Q´ RScot , 0: ³®Q´Q´ RStransfert .
Для кожної термінальної вершини додаються Q пар вершин прибуття
і відправлення з міткою класу (рис. 9). Якщо деякому класу не відповідає
жоден рейс, тоді відповідні вершини і дуги можна відкинути. Таким чином,
дуги між вершинами прибуття, відправлення і термінальними вершинами
матимуть різні вартості в залежності від класу.
Рисунок 9 – Модель авіамережі з трьома аеропортами, двома класами a і b
Висновки
Розглянуто моделі для подання мереж громадського транспорту на прикладі
залізничних доріг і авіаліній у вигляді графів з можливістю подальшого
застосування класичних методів розв’язування. Описані приклади реальних
систем пошуку оптимальних шляхів для залізниць та поширені задачі, які
розв’язують для мереж громадського транспорту. Розглянуті прості та
~ 116 ~
Математичне моделювання в економіці, №1-2, 2017
реалістичні моделі подання графів для мереж громадського транспорту
і авіаліній. Очевидно, що при введенні деяких умов, які виникають у тих чи
інших застосуваннях, графові моделі і підходи до розв’язування задач
можуть суттєво змінюватись. Зазвичай при побудові реалістичних моделей
з додатковими умовами постає проблема надлишковості і надто великих
розмірностей графів, що не дозволяють розв’язувати такі задачі класичними
методами.
Метою подальших досліджень є розробка моделі подання розкладу для
розв’язання залежної від часу задачі пошуку оптимального маршруту між
заданими пунктами з додатковими умовами на мережі авіасполучень певного
регіону [10]. Модель має враховувати розклад, бажаність простою у деяких
проміжних пунктах для економії коштів або туристичного огляду міста,
небажаність відвідування деяких проміжних пунктів тощо.
СПИСОК ЛІТЕРАТУРИ
1. Schulz F. Timetable Information and Shortest Paths [Text]: Dissertation. Doktors der
Natürwissenschaften / Frank Schulz. – 2005. – 136 p.
2. HAFAS - die perfekte Verbindung zum Kunden. [Електронний ресурс]: [Веб-сайт]. –
Електронні дані. – Hannover, Germany. – Режим доступу: http://www.hacon.de/hafas
(дата звернення 18.03.2016) – Назва з екрана.
3. EFA - The Electronic Journey Planner. [Електронний ресурс]: [Веб-сайт]. – Електронні
дані. – Munich, Germany. – Режим доступу: https://www.mentz.net/en/verkehrsauskunft/efa-
journey-planner/ (дата звернення 18.03.2016) – Назва з екрана.
4. Pajor T. Algorithm Engineering for Realistic Journey Planning in Transportation
Networks [Text]: Dissertation. Doktors der Naturwissenschaften / Thomas Pajor. –
Potsdam, 2013. – 266 p.
5. Павленко А. Розв’язання залежних від часу задач пошуку найкоротшого шляху. /
Павленко А.І. // Журнал обчислювальної та прикладної математики. – 2015. –
No 1(118). – С. 24-37.
6. Schulz F. Using multi-level graphs for timetable information in railway systems /
F. Schulz, D. Wagner, C. Zaroliagis / Proceedings of the 4th Workshop on Algorithm
Engineering and Experiments (ALENEX’02). Lecture Notes in Computer Science,
Springer. – 2002. – Vol. 2409. – P. 43–59.
7. Muller-Hannemann M. Timetable information: Models and algorithms. / M. Muller-
Hannemann, F. Schulz, D. Wagner, C. Zaroliagis / Algorithmic Methods for Railway
Optimization. Lecture Notes in Computer Science, Springer. – 2007. – Vol. 4359. – P. 67–90.
8. Brodal G. Time-dependent networks as models to achieve fast exact time-table queries. /
G. Brodal, R. Jacob. – Proceedings of the 3rd Workshop on Algorithmic Methods and
Models for Optimization of Railways (ATMOS’03), Electronic Notes in Theoretical
Computer Science. – 2004. – Vol. 92. – P. 3–15.
9. Delling D., Pajor T., Wagner D., Zaroliagis C. Efficient route planning in flight networks /
Proceedings of the 9th Workshop on Algorithmic Approaches for Transportation Modeling,
Optimization, and Systems (ATMOS’09), OpenAccess Series in Informatics (OASIcs). –
2009. – 17 p.
10. Гуляницький Л.Ф. Динамічна задача пошуку найкоротшого шляху з додатковими
умовами для задачі побудови маршруту авіаперельотів. / Гуляницький Л.Ф.,
Павленко А.І. // Математичне моделювання в економіці. – 2015. – № 2 (3). – С. 39–50.
Стаття надійшла до редакції 30.11.16.
http://www.hacon.de/hafas/
https://www.mentz.net/en/verkehrsauskunft/efa-journey-planner/
https://www.mentz.net/en/verkehrsauskunft/efa-journey-planner/
Вступ
1. Загальна постановка задачі пошуку оптимального шляху громадським транспортом
2. Типові задачі пошуку оптимального шляху громадським транспортом
3. Моделі подання графів для задач пошуку оптимальних шляхів на залізниці
4. Моделі подання графів в задачах пошуку оптимальних шляхів авіаперельотів
4.2 Реалістична модель авіамереж зі сталим часом специфічних процедур
4.3 Реалістична модель авіамереж із врахуванням класу рейсів
СПИСОК ЛІТЕРАТУРИ
|
| id | nasplib_isofts_kiev_ua-123456789-131908 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 2409-8876 |
| language | Ukrainian |
| last_indexed | 2025-12-07T18:38:19Z |
| publishDate | 2017 |
| publisher | Інститут телекомунікацій і глобального інформаційного простору НАН України |
| record_format | dspace |
| spelling | Гуляницький, Л.Ф. Павленко, А.І. 2018-04-05T18:38:58Z 2018-04-05T18:38:58Z 2017 Моделювання залежних від часу проблем пошуку оптимальних маршрутів: огляд / Л.Ф. Гуляницький, А.І. Павленко // Математичне моделювання в економіці. — 2017. — № 1-2(8). — С. 102-116. — Бібліогр.: 10 назв. — укр. 2409-8876 https://nasplib.isofts.kiev.ua/handle/123456789/131908 004.8:519.85:656.7 Розглянуто задачі пошуку оптимальних маршрутів мережами громадського транспорту. Наведено підходи до подання розкладу за допомогою графів у залежних від часу задачах пошуку оптимальних шляхів для залізничних і авіамереж. Проаналізовано типові задачі пошуку оптимальних шляхів у залежних від часу мережах. Рассмотрены задачи поиска оптимальных маршрутов сетями общественного транспорта. Приведены подходы для представления расписания с помощью графов в зависимых от времени задачах поиска оптимальных путей для железнодорожных и авиасетей. Проанализированы типовые задачи поиска оптимальных путей в зависимых от времени сетях. We consider the problem of optimal dynamic time-dependent route planning in public transport networks. The paper describes approaches to represent schedule within graphs for the time-dependent shortest path problems in rail and air networks. Common types of timedependent shortest path problems in dynamic networks are reviewed. uk Інститут телекомунікацій і глобального інформаційного простору НАН України Математичне моделювання в економіці Математичні та інформаційні моделі в економіці Моделювання залежних від часу проблем пошуку оптимальних маршрутів: огляд Моделирование зависимых от времени проблем поиска оптимальных маршрутов: обзор Modelling of time-dependent problems of search of optimal routes: оverview Article published earlier |
| spellingShingle | Моделювання залежних від часу проблем пошуку оптимальних маршрутів: огляд Гуляницький, Л.Ф. Павленко, А.І. Математичні та інформаційні моделі в економіці |
| title | Моделювання залежних від часу проблем пошуку оптимальних маршрутів: огляд |
| title_alt | Моделирование зависимых от времени проблем поиска оптимальных маршрутов: обзор Modelling of time-dependent problems of search of optimal routes: оverview |
| title_full | Моделювання залежних від часу проблем пошуку оптимальних маршрутів: огляд |
| title_fullStr | Моделювання залежних від часу проблем пошуку оптимальних маршрутів: огляд |
| title_full_unstemmed | Моделювання залежних від часу проблем пошуку оптимальних маршрутів: огляд |
| title_short | Моделювання залежних від часу проблем пошуку оптимальних маршрутів: огляд |
| title_sort | моделювання залежних від часу проблем пошуку оптимальних маршрутів: огляд |
| topic | Математичні та інформаційні моделі в економіці |
| topic_facet | Математичні та інформаційні моделі в економіці |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/131908 |
| work_keys_str_mv | AT gulânicʹkiilf modelûvannâzaležnihvídčasuproblempošukuoptimalʹnihmaršrutívoglâd AT pavlenkoaí modelûvannâzaležnihvídčasuproblempošukuoptimalʹnihmaršrutívoglâd AT gulânicʹkiilf modelirovaniezavisimyhotvremeniproblempoiskaoptimalʹnyhmaršrutovobzor AT pavlenkoaí modelirovaniezavisimyhotvremeniproblempoiskaoptimalʹnyhmaršrutovobzor AT gulânicʹkiilf modellingoftimedependentproblemsofsearchofoptimalroutesoverview AT pavlenkoaí modellingoftimedependentproblemsofsearchofoptimalroutesoverview |