ChSTU repository
ChSTU repository preserves and enables easy and open access to all types of digital content including text, images, moving images, mpegs and data sets
Learn More
Please use this identifier to cite or link to this item:
https://er.chdtu.edu.ua/handle/ChSTU/8778| Title: | Оптимізація мережі громадського транспорту в системі транспортного планування PTV Visum |
| Authors: | Рудь , Максим Петрович Жиляков, Андрій Миколайович |
| Issue Date: | 2023 |
| Abstract: | Об’єкт дослідження – макроскопічне моделювання мережі громадського транспорту. Предмет дослідження – методи оптимізації мережі громадського транспорту в системі транспортного планування PTV VISUM. Мета дослідження – створення ефективних маршрутних мереж для систем громадського транспорту (проблема маршрутизації міського транспорту (UTRP)) шляхом подолали розрив між теоретичними дослідженнями UTRP і плануванням транспорту в реальному світі. Для досягнення мети нам необхідно вирішити такі завдання: - Порівняльне дослідження мережевих структур, які використовуються в дослідженні UTRP і Visum, а також методологія з’єднання між ними. - процедури інтерфейсу між мережевими моделями Visum і UTRP для полегшення передачі та перекладу даних між ними. - Гіперевристичний алгоритм вибору, адаптований для оптимізації маршрутів громадського транспорту Visum за допомогою процедур інтерфейсу. - Інтеграція інструментів Visum для оцінки варіантів рішень. Методи дослідження – макроскопічне моделювання транспортного планування за допомогою системи PTV VISUM. Кваліфікаційна робота магістра складається з 81 сторінок пояснювальної записки і включає: вступ, три розділи, висновок, список використаних джерел, а також 3 таблиці, 11 рисунків і 60 джерел. |
| URI: | https://er.chdtu.edu.ua/handle/ChSTU/8778 |
| Appears in Collections: | 275 Транспортні технології (Транспортні технології (на автомобільному транспорті)) |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Жиляков_.pdf Restricted Access | 1.32 MB | Adobe PDF | View/Open Request a copy |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
Extracted text
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ
18006, м. Черкаси, бул. Шевченка, 460, тел./факс (0472) 71 00 92
ЗАТВЕРДЖУЮ
зав. кафедри автомобілів та
технологій їх експлуатації, професор
______________ Л.А. Тарандушка
«___» __________________2023 р.
Кваліфікаційна робота магістра
«ОПТИМІЗАЦІЯ МЕРЕЖІ ГРОМАДСЬКОГО ТРАНСПОРТУ В
СИСТЕМІ ТРАНСПОРТНОГО ПЛАНУВАННЯ PTV VISUM»
начальник технічного відділу
КП «Черкасиелектротранс» _________________ К.П. Бражник
(посада) (підпис) (Ініціали, прізвище)
Керівник роботи:
доцент кафедри АТЕ _______________ М.П. Рудь
(посада) (підпис) (Ініціали, прізвище)
Виконавець:
студент 2 курсу, гр. мАВ-83
спеціальності 274 – Автомобільний
транспорт _______________ _А.М. Жиляков
(підпис) (Ініціали, прізвище)
2023
2
РЕФЕРАТ
«ОПТИМІЗАЦІЯ МЕРЕЖІ ГРОМАДСЬКОГО ТРАНСПОРТУ В
СИСТЕМІ ТРАНСПОРТНОГО ПЛАНУВАННЯ PTV VISUM»
Об’єкт дослідження – макроскопічне моделювання мережі громадського
транспорту.
Предмет дослідження – методи оптимізації мережі громадського
транспорту в системі транспортного планування PTV VISUM.
Мета дослідження – створення ефективних маршрутних мереж для систем
громадського транспорту (проблема маршрутизації міського транспорту
(UTRP)) шляхом подолали розрив між теоретичними дослідженнями UTRP і
плануванням транспорту в реальному світі.
Для досягнення мети нам необхідно вирішити такі завдання:
- Порівняльне дослідження мережевих структур, які використовуються в
дослідженні UTRP і Visum, а також методологія з’єднання між ними.
- процедури інтерфейсу між мережевими моделями Visum і UTRP для
полегшення передачі та перекладу даних між ними.
- Гіперевристичний алгоритм вибору, адаптований для оптимізації
маршрутів громадського транспорту Visum за допомогою процедур інтерфейсу.
- Інтеграція інструментів Visum для оцінки варіантів рішень.
Методи дослідження – макроскопічне моделювання транспортного
планування за допомогою системи PTV VISUM.
Кваліфікаційна робота магістра складається з 81 сторінок пояснювальної
записки і включає: вступ, три розділи, висновок, список використаних джерел, а
також 3 таблиці, 11 рисунків і 60 джерел.
3
ЗМІСТ
ВСТУП .......................................................................................................................... 5
РОЗДІЛ 1. ОГЛЯД ЛІТЕРАТУРИ ............................................................................. 8
1.1 Огляд моделей прогнозування поїздок............................................................ 8
1.1.1 Чотирьохетапна модель прогнозування подорожей .............................. 10
1.1.2 Призначення громадського транспорту .................................................. 14
1.2 Програмні продукти для транспортного моделювання ............................... 16
1.2.1 Огляд макроскопічних програмних продуктів ....................................... 17
1.2.2 Програмне забезпечення Emme 3 ............................................................ 19
1.2.3 Програмне забезпечення Emme 4 ............................................................ 25
1.3 Теоретичні основи предмета дослідження .................................................... 29
1.3.1 Коротка історія проблеми маршрутизації міського транспорту (UTRP)
.............................................................................................................................. 29
1.3.2 Інтерфейс алгоритмів UTRP і програмного забезпечення моделювання
транспорту ........................................................................................................... 31
1.3.3 Оптимізація громадського транспорту у Visum за допомогою
гіперевристики вибору ....................................................................................... 32
РОЗДІЛ 2. МЕТОДИ ДОСЛІДЖЕННЯ ПРОБЛЕМИ МАРШРУТИЗАЦІЇ
МІСЬКОГО ТРАНСПОРТУ ..................................................................................... 36
2.1 Структури даних маршрутизації міського транспорту ................................ 36
2.1.1 Визначення проблеми маршрутизації міського транспорту (UTRP) ... 36
2.1.2 Структура даних Visum ............................................................................ 37
2.1.3 Інтерфейс між структурами даних UTRP і Visum ................................. 39
2.2 Процеси інтерфейсу між алгоритмами UTRP і Visum ................................. 41
2.2.1 Вилучення графа UTRP із моделі мережі Visum ................................... 42
2.2.2 Перетворення маршрутів UTRP на лінійні маршрути Visum ............... 45
4
РОЗДІЛ 3. ЕКСПЕРИМЕНТАЛЬНЕ ДОСЛІДЖЕННЯ ТРАНСПОРТНИХ
МЕРЕЖ ІЗ ЗАСТОСУВАННЯМ АЛГОРИТМІВ ГІПЕРЕВРИСТИКИ .............. 49
3.1 Оптимізація транспортних мереж .................................................................. 49
3.1.1 Застосування алгоритму відбору гіперевристики .................................. 49
3.1.2 Оптимізація маршруту лінії PuT за допомогою гіперевристики вибору
.............................................................................................................................. 51
3.1.3 Алгоритм евристики низького рівня ....................................................... 53
3.1.4 Здійсненність рішення транспортної задачі ........................................... 54
3.1.5 Оцінка отриманого набору маршрутів .................................................... 56
3.2 Результати емпіричних досліджень ............................................................... 61
3.2.1 Тестування на малій моделі ..................................................................... 61
3.2.2 Застосування моделі у мережі розміром міста ....................................... 63
3.2.3 Застосування моделі локальної оптимізації ........................................... 68
3.3 Модифікації тестових мереж .......................................................................... 72
3.3.1 Модифікації малої мережі ........................................................................ 72
3.3.2 Модифікації мережі міста......................................................................... 73
Висновки ................................................................................................................... 75
СПИСОК ЛІТЕРАТУРИ ........................................................................................... 77
5
ВСТУП
Системи громадського транспорту є важливою частиною інфраструктури в
містах. Їх ефективність життєво важлива для багатьох зацікавлених сторін, тому
вони потребують точного проектування та планування. Створення ефективних
маршрутних мереж для систем громадського транспорту відоме в багатьох
дослідженнях як проблема маршрутизації міського транспорту (UTRP). UTRP
фактично є підпроблемою більшого завдання з оптимізації мереж громадського
транспорту, яке складається з п’яти етапів: (1) розробка маршруту, (2)
встановлення частоти руху транспортних засобів, (3) розробка розкладу, (4)
транспортні засоби планування та (5) планування екіпажу (Ceder and Wilson
1986). Оскільки фази взаємопов’язані, проблема має дуже високу складність, і
більшість досліджень мають справу лише з підмножинами цих фаз,
використовуючи спрощення. У випадку UTRP, який розглядає лише перший
етап, передбачається фіксована частота на всіх маршрутах, а інші аспекти, такі
як фактичний час відправлення та прибуття транспортних засобів на зупинки, не
враховуються.
Цій проблемі в літературі присвячено значну кількість досліджень, які
відрізняються за своїм застосуванням у різних випадках, цілями та
методологіями вирішення.
Незважаючи на інтенсивні дослідження UTRP, існує величезна прірва між
часто суто академічними дослідженнями та застосуванням їх результатів у
процесах планування реального світу. Причини розриву досі не були ретельно
досліджені (Walter 2010). Однак одним із можливих пояснень можуть бути
відмінності у вимогах до даних між алгоритмами, які використовуються в
дослідженнях UTRP, і загальновживаними інструментами планування.
Агентства з планування зазвичай приймають рішення на основі моделювання,
виконаного за допомогою професійного програмного забезпечення для
6
моделювання транспорту, наприклад, Visum від PTV (PTV AG 2018) або Emme
від INRO (INRO 2018). Моделі, створені за допомогою таких програмних
пакетів, вимагають детальної інформації про планування вулиць, транспортну
інфраструктуру та попит на подорожі, що робить їх впровадження та
калібрування трудомісткими. Однак отримана модель є дуже потужною і
дозволяє планувальникам вивчати та моделювати різні явища, пов’язані з
транспортом. З іншого боку, дослідники, які працюють над UTRP, застосовують
свої алгоритми проектування до абстрактних моделей, які спрощують багато
аспектів реальних транспортних мереж. Структура графа з точками взаємозаміни
як вершинами та прямими зв’язками між ними як неорієнтованими ребрами є
загальною моделлю, яка використовується в більшості попередніх досліджень.
У цій роботі ми подолали розрив між двома світами теоретичних досліджень
UTRP і планування транспорту в реальному світі. Тут ми зосереджуємося на
програмному забезпеченні для моделювання транспортування Visum і
порівнюємо структуру його транспортної мережі із загальною моделлю UTRP,
яку раніше використовували багато дослідників, вказуючи на ключові
відмінності між ними. На основі цих висновків ми описуємо процес
перетворення компонентів мережі Visum у структуру графа UTRP і навпаки
шляхом реалізації інтерфейсу середнього рівня, через який інформація
транспортної мережі проходить між моделями. Використовуючи цей інтерфейс,
гіперевристика вибору використовується для оптимізації маршрутів
громадського транспорту Visum, одночасно використовуючи переваги
інструментів аналізу Visum для оцінки певного рішення-кандидата. Основні
внески цього дослідження:
- Порівняльне дослідження мережевих структур, які використовуються в
дослідженні UTRP і Visum, а також методологія з’єднання між ними.
- Нові процедури інтерфейсу між мережевими моделями Visum і UTRP
для полегшення передачі та перекладу даних між ними.
- Гіперевристичний алгоритм вибору, адаптований для оптимізації
7
маршрутів громадського транспорту Visum за допомогою процедур інтерфейсу.
- Інтеграція інструментів Visum для оцінки варіантів рішень.
8
РОЗДІЛ 1. ОГЛЯД ЛІТЕРАТУРИ
1.1 Огляд моделей прогнозування поїздок
Прогноз подорожі можна використовувати для прогнозування змін у мережі
трафіку. Поширеним методом прогнозування подорожі є чотириетапна модель,
де програмне забезпечення для макроскопічного моделювання є частиною
процедури. Прогноз подорожей або трафіку – це передбачення того, як трафік
зміниться в майбутньому, і завжди базується на зовнішніх умовах і факторах.
Щоб створити модель із високою точністю, модель насамперед має включати
соціально-економічні дані та транспортну мережу. Цей розділ має на меті надати
короткий опис щодо прогнозування подорожей, включаючи чотириетапну
модель і огляд того, як працює призначення громадського транспорту. Для
отримання додаткової інформації про прогнозування подорожі та чотириетапну
модель див. Ortuzar and Willumsen [6], Hyden et.al. [7], WSP [8], Національна
програма спільних досліджень автомобільних доріг [9], Департамент транспорту
Каліфорнії [10] і Лінд [11].
Прогноз трафіку може бути частково здійснений за допомогою
комп'ютерного програмного забезпечення з моделлю мережі трафіку. Стосовно
транспортної мережі та конкретної мережі громадського транспорту (транзитної
мережі) кодування може бути складним. Може бути широкий вибір доступних
видів транспорту, таких як місцевий автобус, експрес-автобус, електричка,
приміська залізниця та швидкісний автобус. Обслуговування ліній часто
відрізняється в години пік і поза пік протягом дня. Загальний потік
досліджується за допомогою макроскопічного моделювання, а індивідуальна
поведінка транспортних засобів не береться до уваги. Дорожня мережа має
більший масштаб і може включати дорожню мережу для цілого міста чи країни,
і моделювання виконується по ділянках. Emme та Visum — це програми для
макроскопічного моделювання, які використовуються під час прогнозування
подорожей. Модель, яка створюється в програмному забезпеченні симуляції
9
трафіку, є спрощеною версією та представленням мережі реального світу, яка
становить інтерес.
Метод прогнозування можна використовувати не тільки для прогнозування
майбутнього, але й для дослідження того, як буде змінюватися схема подорожі
під час модифікації або зміни будь-чого в інфраструктурі руху. Модель може
бути корисною під час аналізу ефекту від редагування проекту дороги, зміни
постачання громадського транспорту або впровадження плати за проїзд.
Результат моделей прогнозування може бути частиною процесу прийняття
рішень під час прийняття рішень про зміни щодо системи руху. За допомогою
прогнозування можна порівняти наслідки альтернативних дій, щоб особа, яка
приймає рішення, могла легше визначити, яка дія чи дії вплинуть на транспортну
систему в бажаному напрямку. Найпоширенішою причиною та метою
прогнозування трафіку є дослідження змін у потоці (обсязі трафіку) після
модифікації мережі трафіку. Це показує, як модифікація вплинула на систему
дорожнього руху з точки зору збільшення, зменшення або зміни обсягу трафіку.
Це також може бути кількість поїздок і кілометрів автомобіля для різних видів
транспорту на різних дорогах і транзитних лініях. Він також може надавати
інформацію про очікувану заторів у цьому районі.
Вибір процедури прогнозування є компромісом між бажаною точністю
прогнозу та доступними ресурсами щодо часу, грошей, зусиль і доступних
ресурсів. Не завжди обрана процедура дає найточніший результат, оскільки для
цього потрібно багато роботи, наприклад, великий збір даних і точне
калібрування. Використовувана процедура прогнозування також залежить від
основної причини аналізу та періоду тривалості прогнозу. Існує три типи
підходів моделювання: мікроскопічне, мезоскопічне та макроскопічне
моделювання. У мікроскопічній імітаційній моделі вивчаються окремі
транспортні засоби та їх поведінка. Дорожня мережа є відносно невеликою і
може складатися, наприклад, з кільцевої розв’язки. При розробці стратегій
управління для різних функцій (наприклад, світлофорів) та аналізі фактичних
10
інвестицій щодо інформації про дорожній рух, модель має бути доповнена більш
детальними моделями. Цей тип моделі потребує більше вхідних даних із
додатковим кодуванням і, отже, потребує значно більше ресурсів. Аналітики
трафіку часто обмежують мережу меншою географічною областю, яка більше
підходить для мікросимуляції. Мезоскопічне моделювання знаходиться між
мікро- та макрорівнем. Окремі транспортні засоби моделюються, але дії та
взаємодії описуються в макроскопічних співвідношеннях. Цей підхід часто
використовується при оцінці систем інформації для мандрівників. У
макроскопічній імітаційній моделі вивчається загальний потік, а індивідуальна
поведінка транспортних засобів не береться до уваги. Дорожня мережа має
більший масштаб і може включати дорожню мережу для цілого міста чи країни,
і моделювання виконується по ділянках. Emme та Visum — це програми для
макроскопічного моделювання, які використовуються під час прогнозування
подорожей. Модель, яка створюється в програмному забезпеченні симуляції
трафіку, є спрощеною версією та представленням мережі реального світу, яка
становить інтерес.
У наступному розділі коротко описано чотириетапну модель подорожі, де
програмне забезпечення Emme і Visum використовуються на етапах 3 і 4 моделі
подорожі.
1.1.1 Чотирьохетапна модель прогнозування подорожей
Чотирьохетапна модель є широко використовуваним підходом для
моделювання трафіку і складається з чотирьох окремих кроків, які добре описані
в літературі, наприклад, у Ortuzar і Willumsen [6], дивіться рисунок 1.1 для
ілюстрації того, як працює чотириетапна модель.
1. Генерація трафіку
2. Розподіл поїздок
3. Вибір режиму
4. Призначення маршруту
11
Рисунок 1.1: Ілюстрація чотириетапної моделі подорожі та того, що включено
до рішення на кожному кроці
Генерація поїздки
Цей крок описано в [9], і його метою є оцінка кількості поїздок кожного типу
мети, які починаються або закінчуються в кожній зоні. Оцінка ґрунтується на
активності в зоні. Кількість поїздок, згенерованих на цьому кроці, є потоком,
який використовується в моделі. Зазвичай це подорожі транспортним засобом і
особами (автомобілем або транзитом), які часто включають як пішки, так і
велосипед. Результати та вихідні дані моделі генерації подорожей – це
виробництво поїздок і цікаві місця для кожної зони та мети подорожі.
Розподіл поїздок
На цьому етапі обчислюється відсоток загального трафіку, який
проходитиме між кожною парою зон. Результат можна представити у вигляді
матриці, де кожен рядок і стовпець представляють зону. Кожне значення в
комірці матриці представляє кількість поїздок між зонами, і це називається
матрицею подорожей або матрицею OD, де Tij — попит із зони i до зони j. Часто
12
попит на подорожі змінюється з часом, і для вивчення різних періодів часу
можуть використовуватися різні матриці.
Вибір режиму
Мета цього кроку — розділити поїздки між зонами за різними способами
подорожі. Визначення видів транспорту залежить від зони забезпечення
транспортування та типу аналізу транспортування, який потрібен. Режими
зазвичай можна розділити на три групи: автомобільний, транзитний і
безмоторний. Вибір способу може залежати від асортименту видів транспорту,
часу в дорозі з конкретним видом і вартості. Існують різні підходи до вибору
режиму, але, згідно з Hagerwall Stein, [12], найпоширенішим є логіт-модель.
Існує кілька логіт-моделей, але однією з більш базових версій є так звана лінійна
модель, див. формулу нижче:
(1.1)
де Pj – частка відомої загальної вартості, розподіленої на альтернативу j, xi
– характеристика (наприклад, час, вартість), ai – вага для відповідного xi, а k —
доступний вид транспорту.
Щоб отримати розподіл кількості поїздок для кожного режиму руху ����
����,
виконується наступний розрахунок із результатом розподілу поїздок і логіт-
моделі:
(1.2)
Призначення маршруту
Призначення маршруту розраховує, як прогнозовані мандрівники будуть
розподілені між різними ланками в транспортній мережі (включно з
немоторизованими ланками) або транзитними лініями. Те, як працює
призначення маршруту, залежить від використовуваного програмного
забезпечення та того, що аналізується. Існують різні типи призначень, і два
основних: автомобільне призначення, яке обробляє маршрутизацію
13
транспортних засобів, і призначення громадського транспорту (транзиту), яке
стосується маршрутизації пов’язаних пасажирських поїздок (які включають
прогулянки, посадку та висадку). Залежно від програмного забезпечення може
бути більше альтернатив, варіантів або комбінацій цих двох призначень.
Одиницею потоку в автомобільному призначенні є кількість транспортних
засобів, а в транзитному призначенні – кількість пасажирів. Інша відмінність між
двома призначеннями полягає в тому, що призначення транзиту має лінійні
маршрути, які складаються з набору відрізків, які називаються сегментами ліній.
При визначенні очікуваного часу подорожі пасажирів обчислюється функція
імпедансу. У призначенні маршруту ця функція використовується для розподілу
попиту на кожному маршруті. Функція імпедансу відображає небажання
подорожувати та зростає з довшим загальним часом подорожі. Функція
імпедансу в транспортному призначенні, порівняно з автоматичним
призначенням, також містить змінні рівня обслуговування, які не включені в
автомобільне призначення, наприклад час очікування, час посадки та
допоміжний час (час ходьби). Поїздка між двома вузлами може обслуговуватися
більш ніж однією транзитною лінією, і лінії можуть мати різні види транспорту
(наприклад, міський автобус, експрес-автобус, метро).
Коли мандрівники вирішують скористатися громадським транспортом,
попит розподіляється на різні маршрути. Існують різні типи транспортних
призначень залежно від навколишнього середовища та доступного розкладу
громадського транспорту. Доступні процедури призначення різняться залежно
від програмного забезпечення, і прикладом найпоширеніших є: на основі
транспортної системи, руху та розкладу. Коли мета полягає в тому, щоб
оцінити всю систему замість аналізу окремих транзитних ліній
використовується процедура на основі транспортної системи. Це не потребує
мережі транзитних ліній і використовується для створення мережі громадського
транспорту, де пасажири обирають найкоротші маршрути. Процедура, заснована
на розкладі, повинна використовуватися для транспортних систем, які мають
14
лінії з довгими напрямками, наприклад, поїзди далекого прямування або
транзитні лінії в сільській місцевості. Щоб мати можливість виконувати
завдання на основі розкладу, потрібна повна інформація про розклад, час
прибуття та відправлення. Призначення на основі прогресу базується на теорії
оптимальної стратегії, яка вимагає частоти та часу в дорозі для відповідних ліній
громадського транспорту. Оскільки цей тип процедури не вимагає точних
розкладів, він підходить лише для довгострокового планування перевезень, коли
розклади не визначені.
1.1.2 Призначення громадського транспорту
При розподілі попиту на мережу громадського транспорту існує кілька
методів з різними цілями, які описані в посібниках [1] і [2]. Перш за все, існує
стандартне призначення, яке називається на основі пробігу, яке в основному
враховує частоту транзитних ліній. Це найкраще підходить для великих міст із
частими маршрутами транспорту. Однак він не підходить для сільської
місцевості, де лінії можуть відправлятися рідше. У таких випадках замість цього
можна використовувати призначення на основі розкладу. Для цього варіанту
потрібен повний розклад для всіх доступних маршрутів. Існує також
призначення на основі пробігу/часу, яке використовує як частоту, так і час у
дорозі, щоб вирішити, який буде оптимальним маршрутом. Іншим варіантом
призначення громадського транспорту є транспортна система, яка створює
абсолютно нову мережу громадського транспорту на основі існуючої
інфраструктури.
Вагові коефіцієнти, які використовуються в алгоритмах, базуються на
певній оцінці економічних витрат для громади. Час очікування, прогулянки та
пересадки важить більше, ніж подорож у транспортному засобі, тому що люди
цінують цей час вище. Час розраховується як вартість, так звана узагальнена
вартість, і мандрівник хоче мінімізувати цю вартість. Час можна класифікувати,
і коли йдеться про систему громадського транспорту, час оцінюється по-різному.
15
Час, витрачений на перехід між двома лініями, інтерпретується як більший, ніж
фактичний час.
Вагові коефіцієнти призначення можна регулювати, щоб отримати модель
мережі громадського транспорту, яка нагадує реальну мережу. Параметри в цій
роботі були зібрані з однієї з моделей транспортної адміністрації Emme, яка
складається з рекомендованих налаштувань параметрів. Різні параметри та їхні
значення можна побачити пізніше в розділі 3.5.2. Інша література описує методи
калібрування та те, як конкретні мережі були відкалібровані щодо різних
параметрів призначення. У мережевих звітах використовувалися два види
методів калібрування; використання даних з маршрутів громадського
транспорту, використання даних опитувань щодо поведінки мандрівників.
Перший метод був використаний у Parveen et.al. [13] і Фунг [14], тоді як другі
методи частіше використовували Горовіц [15], Вордман [16], Абрантес і
Вордман [17], Кураучі та ін. [18] і Райдергрен [19]. Наприклад _ Rydergren описує
в [19], як міська мережа була відкалібрована відповідно до опитувань поведінки
з різними алгоритмами призначення. Висновки, зроблені на основі цих згаданих
звітів, полягають у тому, що параметри призначення потребують калібрування
відповідно до різних програмних продуктів, алгоритмів призначення,
налаштувань призначення та зони мережі. Тому правильним способом обробки
цих параметрів є налаштування їх відповідно до різних ситуацій. Попередніх
перекладів параметрів між Emme і Visum не існує, принаймні згідно з
інформацією авторів, у призначенні на основі прогресу. Тому буде зроблено
припущення на основі вивчення посібників і перевірки того, як параметри
працюють у кожному програмному забезпеченні. Параметри, які будуть
перекладені, — це ваги, коефіцієнти та/або штрафи за те, як пасажири
сприймають посадку, ходьбу, поїздку громадським транспортом і час очікування
порівняно з часом, який вони могли б провести в автомобілі. Цей переклад
представлено в розділі 3.1, таблиці 4.
Логітарний розподіл — це розподіл ймовірностей (див. рівняння 1), де потік
16
розподіляється відповідно до призначеного відсотка. Потік буде налаштовано
відповідно до рівняння 2, яке враховує розподіл у різних режимах, з’єднувачі між
початковими вузлами та мережею тощо. Використовуючи логіт- розподіл, можна
змусити вибирати різні з’єднувальні зв’язки між вихідними вузлами та мережею,
транзитний маршрут замість того, щоб йти пішки до іншої станції, щоб
скоротити час у дорозі, або пересісти на інший транзитний маршрут замість того,
щоб залишатися на борту. За словами Флоріана та Константіна [20], логіт-
розподіл вирівнює транзитних мандрівників на різних маршрутах у кількох
ситуаціях, коли всі вони обрали б однакову стратегію подорожі. Це призводить
до більш реалістичного результату, коли пасажири вибирають різні маршрути
від відправлення до пункту призначення.
1.2 Програмні продукти для транспортного моделювання
Цей розділ містить інформацію про різні інструменти макроскопічного
моделювання та особливо зосереджується на двох найбільш часто
використовуваних, тобто Emme та Visum. Тому наведено більш детальні описи
цих програмних продуктів щодо призначення громадського транспорту та
доступних алгоритмів. У розділах 3.2 і 3.4 описано, як працює призначення
громадського транспорту у відповідному програмному забезпеченні. Ці розділи
також містять описи алгоритмів призначення транзиту. У Visum є кілька
алгоритмів, однак буде детально визначено лише той алгоритм, який відповідає
стандартному алгоритму Emme 3. Інші алгоритми також доступні в Emme 4, і
вони будуть представлені в розділі 3.3. Потім у розділі 3.5.4 розглядаються
математичні відмінності програмних алгоритмів. Посібники з програмного
забезпечення, Emme 3 [1], Emme 4 [21] і Visum 13 [2], були використані в цьому
розділі та є джерелами, якщо нічого іншого не зазначено.
У статті Флоріана та Шпісса [22] є пояснення того, як працюють оптимальні
стратегії, і приклад із невеликою мережею громадського транспорту. Деякі
17
попередні порівняння між Emme, Visum та подібним програмним забезпеченням
були вивчені та використані як основа для цієї тези. Висновки цих порівнянь
представляли інтерес для подальших досліджень. Крім того, виявлення слабких
місць у порівняннях було важливим. Деякі з вивчених порівнянь – це звіт
Йоханссона [5], звіт Ларсена [23] і магістерська робота [12], де перші дві статті
розглядають як Emme, так і Visum (на основі алгоритмів VIPS) щодо
громадського транспорту. Однак ретельного порівняння алгоритмів не було
зроблено. [12] зосереджено на призначенні автомобіля та автомобіля, тому його
використовували для фактів програмного забезпечення та методу порівняння.
1.2.1 Огляд макроскопічних програмних продуктів
Наступні програмні продукти містять більш-менш макроскопічні функції
моделювання руху; Emme, Visum, Aimsun, TransModeler і VIPS. Aimsun, згідно з
веб-сайтом Transport Simulation System [3], є гібридом між мікро-, макро- та
мезоскопічним програмним забезпеченням моделювання руху. Однак основна
увага зосереджена на мікроскопічному моделюванні, тому його не часто
використовують для макроскопічних мереж трафіку, таких як країна чи місто.
Програмне забезпечення для моделювання TransModeler також є гібридом між
трьома типами рівнів деталізації; макро, мікро та мезо. На веб-сайті TransModeler
[4] зазначено, що програмне забезпечення містить імітаційні моделі, такі як
платні об’єкти, паркування на вулицях, контроль сигналів, динамічне
призначення трафіку та поєднання мікро- та макро (області, які представляють
найбільший інтерес, моделюються на мікрорівні, а решта – на макро рівень).
Існують також призначення громадського транспорту, які базуються на
маршрутах або розкладах. Це програмне забезпечення зазвичай не
використовується для призначення громадського транспорту в межах країн
Європи. Проте є деякі європейські проекти трафіку, які використовують
TransModeler для динамічного розподілу автомобілів і автомобілів. VIPS — це
програмне забезпечення для симуляції макроскопічного транспорту, інтегроване
з Visum. Версія 13 Visum містить деякі частини алгоритму VIPS, і відносно
18
небагато аналітиків трафіку все ще використовують VIPS. У ЄС більшість
муніципалітетів і округів використовують інструменти планування дорожнього
руху, такі як програмне забезпечення з макроскопічним моделюванням
дорожнього руху для майбутнього прогнозування дорожнього руху тощо. У
Швеції, наприклад, Emme включено у програмне забезпечення для
прогнозування дорожнього руху, яке вони використовують для всіх частин
країни, але в Стокгольмі замість цього використовується Visum. Оскільки ці два
основні оператори інфраструктури використовують Emme та Visum, вони
становлять інтерес для подальшого дослідження. Раніше їх порівнювали у звіті
Йоханссона [5], Ларсена [23] і магістерській роботі [12], яка буде описана нижче.
У 1984 році було проведено порівняння між Emme та VIPS, який було
включено до попередньої версії Visum, описаної в [5]. Програмне забезпечення
VIPS використовувалося для аналізу змін у транзитній мережі, однак нове
програмне забезпечення Emme також нещодавно було встановлено в офісі, тому
було цікаво оцінити обидві програми. Мета полягала в тому, щоб порівняти
результати обраних програмами маршрутів із зробленим опитуванням. Під час
опитування 100 осіб на пару вузлів запитували про їхній маршрут. Та сама
мережа транзитних ліній над центральними частинами міста використовувалася
разом із OD-матрицею для середнього періоду часу між 07:00 - 09:00 у VIPS та
Emme. Відповідно до результатів VIPS збільшив обсяги автобусів (+12%)
порівняно з опитуванням, а Emme – менші обсяги (-7 %). У VIPS пасажири
частіше розподіляються на різних маршрутах між відправленням і пунктом
призначення порівняно з Emme. Середня кількість транзитів на одного пасажира
становить 0,63 у VIPS і 0,59 в Emme. В Emme майже всі вибрали той самий
маршрут. Середня абсолютна різниця між опитуванням і моделями щодо
кількості посадок на кожну автобусну лінію становить 30% для VIPS і 15% для
Emme. Йоханссон [5] також прокоментував, що штраф за п’ять хвилин передачі
відкалібрований для VIPS за результатами опитування. Автор згадує про
бажання продовжити порівняння з калібруванням трансферного штрафу проти
19
Емме.
У 2011 році було проведено порівняння між Emme і Visum щодо
транзитного призначення Ларсена [23]. Він згадує про деякі відмінності, але
насправді не пояснює, як він приходить до певних висновків. Є кілька прикладів,
але розрахунки відсутні, і вказано лише остаточну відповідь. Проте ідея мати
простий приклад, щоб показати, як працюють алгоритми, є гарною ідеєю, і вона
також буде використана в цій магістерській роботі.
Призначення трафіку (автомобільний) з мережевою рівновагою було
порівняно між Emme та Visum та оцінено Hagerwall Stein у 2007 році [12].
Незважаючи на те, що порівнювали інше призначення, використовувався той
самий метод, що й у цьому звіті. Обмежена частина мережі була розроблена в
Emme і пізніше імпортована в Visum. Одна і та ж OD-матриця використовувалася
в обох програмах. Його висновок полягав у тому, що результат схожий щодо
потоків на відрізках і маршрутах, що означає, що і Emme, і Visum базуються на
тому самому алгоритмі (мережева рівновага). В основному відмінності були
викликані округленням чисел в OD-матриці.
1.2.2 Програмне забезпечення Emme 3
Emme (Equilibre Multimodal, Multimodal Equilibrium), описаний у посібнику
Emme [1], розробленому в Центрі досліджень транспорту (CRT) Монреальського
університету в сімдесятих роках. У вісімдесятих роках у CRT була розроблена
перша комерційна версія Emme під назвою Emme 2. Професор Майкл Флоріан є
одним із засновників INRO та програмного забезпечення Emme, і він відіграв
ключову роль у розробці модулів, що використовуються для призначення
транзиту. У посібнику Emme 4 [21] зазначено, що було зроблено вдосконалення
та випущено нові версії програмного забезпечення Emme. Emme 3 містить
графічний інтерфейс для редагування мережі, більше інструментів для
моделювання, аналізу тощо. В Emme 4 є інструмент призначення заторів, який
моделює скупчення людей, дискомфорт у транспортних засобах, обмеження
пропускної здатності та збільшення часу очікування. Постійно тривають
20
розробки щодо інтерфейсу, аналізу, реалізації віртуальної та зональної моделі
попиту на подорожі тощо. Emme використовується в понад 85 країнах,
включаючи Австралію, Канаду, США, Південну Африку, Центральну та
Південну Америку, Азію та більшість країни Європи.
Програма моделювання макроскопічного руху Emme використовується для
моделювання міських, регіональних і національних транспортних систем. Emme
— це інструмент аналізу трафіку, який використовують транспортні
планувальники та аналітики трафіку в усьому світі. У цьому розділі буде описано
програмне забезпечення та деякі його функції щодо призначення громадського
транспорту.
1.2.2.1 Призначення громадського транспорту
Призначення транзиту ґрунтується на підході теорії оптимальних стратегій
Флоріана та Спіса [22]. Призначення громадського транспорту в Emme
складається з призначення транзиту на основі руху, руху/часу та розкладу, однак
призначення на основі транспортної системи не включено в поточні версії, що
продаються.
Транзитна мережа складається з центроїдів (зон), регулярних вузлів, ланок
і набору транзитних ліній. Транзитна лінія містить набір вузлів і набір ланок.
Послідовність вузлів представляє маршрут і місце, де мандрівники можуть
сідати або висаджуватися. Кожна ланка може мати більше однієї транзитної лінії,
яка складається з кількох сегментів транзитної лінії.
Алгоритм призначення транзиту спрямований на мінімізацію загального
часу подорожі, що містить; час очікування, допоміжний час, час посадки та час
перебування в транспортному засобі. Компоненти часу зважуються, щоб
порівняти цей час із часом автомобіля. Загальний час подорожі перетворюється
на загальну вартість (TTT), іншими словами, мандрівник хоче мінімізувати
загальну вартість. Час визначається для кожного сегмента лінії та відображається
до загального часу подорожі для всієї подорожі. Коефіцієнт часу очікування
масштабує час, який мандрівник повинен чекати на вузлі для привабливої лінії.
21
Фактор також використовується для визначення часу очікування разом із часом
очікування на конкретному вузлі. Значення може відрізнятися від 0. 01 до 1 і
може бути або специфічним для вузла, або однаковим для всієї мережі. Вага часу
очікування, яка описує, скільки часу очікування оцінюється порівняно з часом у
автомобілі, можна встановити в межах 0–999. 999, а також параметр часу
посадки. Значення може бути однаковим у всій мережі або залежати від
вузла/лінії. Вага часу посадки також встановлена в діапазоні 0-999. 999 і має
відображати, по відношенню до часу перебування в автомобілі, вартість посадки
або пересадки. Допоміжна вага часу та коефіцієнт поширення також повинні
мати значення від 0 до 999. 99.
Після кожного транзитного призначення можна отримати звіт про
призначення та матриці з; час транзиту, час перебування в транспортному засобі,
час додаткового транзиту, загальний час очікування, час першого очікування, час
посадки та середню кількість посадок. Графічні результати також доступні в
Emme 3 з варіантами порівняння двох сценаріїв.
Лінія i є привабливою, якщо час у дорозі на цій лінії менший, ніж загальний
час у дорозі інших привабливих ліній, включаючи час очікування. Це означає,
що вигідніше сісти на лінію i, якщо вона прибуває безпосередньо, ніж чекати на
більш швидку привабливу лінію. Час очікування у вузлі, tωt, залежить від
комбінованої частоти (λi) для привабливих ліній (в оптимальному наборі ліній i
∈ I*), див. рівняння (3), отримане з навчального матеріалу Нільссона [24]:
(3)
3.2.3.2 Алгоритм оптимальних стратегій
Деякі позначки, згадані в цьому розділі, описані в таблиці 1 нижче.
Таблиця 1: Опис нотації для окремих рядків для розділу алгоритму в Emme
Позначення Пояснення позначень
tωt Час очікування
22
ωωt Вага та коефіцієнт часу очікування
tдоп Допоміжний час
ωдоп Вага допоміжного часу
tпосадка Час посадки
ωпосадка на борт Вага часу посадки
tподорожі Час подорожі
ТТТ Загальний очікуваний час подорожі, рівняння (4), також
називається функцією імпедансу та узагальненою
вартістю
a Індекс відрізків
А Всі відрізки в мережі
?̅? Усі відрізки, що містять оптимальні лінії
i Рядковий індекс
я Всі лінії в мережі
я* Усі оптимальні лінії, тобто лінії, вибрані за алгоритмом
оптимальних стратегій
п Індекс вузла
Н Всі вузли в мережі
λ Частота лінії
ч Рух лінії
π Імовірність комбінованої лінії (частка загального
попиту), рівняння (5)
ТТТ' TTT без часу очікування (t ω t ω ω t), рівняння (12)
TTT * Загальний очікуваний час подорожі оптимальних ліній,
рівняння (7)
Пасажири хочуть мінімізувати час у дорозі за всю поїздку. Формула для
загального очікуваного часу подорожі (TTT) показана нижче у рівнянні (4).
(4)
23
Освітній звіт Матті Пурсула та ін. al., [25], стверджує, що призначення
виконується у дві частини, перша – обчислення оптимальної стратегії для
досягнення пункту призначення з кожного джерела, а друга – призначення
попиту відповідно до стратегії.
Різні варіанти того, як пасажири можуть дістатися до місця призначення,
зберігаються в наборі стратегій. Стратегію можна пояснити як правила, які
дозволяють мандрівнику приймати здійсненні рішення та досягати вузла
призначення. Приклад стратегії, згідно з посібником Emme [1]: у вузлі 1 візьміть
лінію, яка прибуває першою з привабливих ліній 1 і 2. Якщо була зайнята лінія
1, зійдіть у вузлі 2. Якщо лінія 2 була захоплена у вузлі 4. У вузлі 2 візьміть лінію,
яка прибуває першою з привабливих ліній 3 і 4. Якщо була зайнята лінія 3,
висадіть у вузлі 4. Якщо була зайнята лінія 4, зійдіть у вузлі 3. У вузлі 3 візьміть
приваблива лінія 5 і виходить у вузлі 4.
Чим більше інформації має мандрівник, тим складнішими стають стратегії.
Мандрівник знає розподіл часу між прибуттями для транзитних ліній для
певного вузла та час у дорозі між вузлами. Мандрівник отримує інформацію,
коли досягає вузла, а також відомий розподіл пасажирів. Разом можна обчислити
загальний прийнятний час очікування для прибуття першого автомобіля в наборі
транзитних ліній, що проходять через вузол, і ймовірність того, що кожна лінія
прибуде першою. Вибрані маршрути залежатимуть від того, які транзитні лінії
першими прибувають до вузлів. Відповідно до Нільссона [24], час очікування
мандрівників у вузлі залежить від сумарної частоти привабливих ліній, які
обслуговують вузол, див. рівняння (3). Ця частина обчислюється у зворотному
порядку, починаючи з вузла призначення та продовжуючи назад до всіх
зачеплених вузлів походження. Транспортна мережа G складається з набору
вузлів і набору зв’язків, G = (N, A). Поїздка визначається послідовністю вузлів, n
∈ N, через зв’язки a ∈ A. Ланці a призначається час проходження ланки ca та
розподіл часу очікування. Результатом є оптимальна стратегія ��̅̅ ̅̅ ̅
����
(послідовність зв’язків) із очікуваним загальним часом подорожі ������∗
����від
24
кожного вузла n ∈ N до місця призначення r.
Перша частина алгоритму ініціалізує очікуваний час подорожі для
досягнення r, TTTnr, до нескінченності для всіх вузлів, за винятком TTT пасажирів
вузла призначення, який встановлено на нуль. Змінна частоти λi для всіх i ∈ I *
містить комбіновані частоти привабливих ліній і ініціалізується нулем. Набір S
використовується для ідентифікації зв’язків, які ще не перевірені, і він
ініціалізується всіма зв’язками в A. Набір A ініціалізується порожнім набором і
використовується для визначення оптимальної стратегії.
Друга частина алгоритму починається з перевірки, чи містить набір S будь-
які неперевірені відрізки, якщо він порожній, перша частина алгоритму буде
зупинена. Якщо S не пусте, вибирається відрізок, найближчий до пункту
призначення r. Час TTT'nr + ca вважається часом від вузла n до пункту
призначення r без урахування часу очікування у вузлі n. Якщо цей час менший
порівняно з попереднім часом при n, TTTnr, то відрізок a включається в
оптимальну стратегію, і обидва λί і TTTnr оновлюються до нового сумарного
загального часу в дорозі привабливих маршрутів. Важливо знати, як змінюється
TTTnr. Перший раз це буде λiTTTnr= ”0 · ∞” (що не визначено), щоб зробити
алгоритм більш компактним, умовність ”0 · ∞” = τ припускається, де τ це фактор
часу очікування.
Відповідно до [24] Нільссона, ймовірність того, що лінія i потрапить на
борт, визначається як співвідношення між частотою лінії та сумарною частотою
привабливих ліній:
(5)
Попередня лінія використовується в Emme, коли обчислюється оптимальна
стратегія для пасажирів. За даними Matti Pursula et. al [25] прогрес може бути
фактичним або уявним прогресом конкретної транзитної лінії або сегмента
(визначається користувачем). Проміжок часу в Emme використовується для
визначення часу очікування, але також використовується для розподілу
25
пасажирів на привабливі транзитні лінії.
У другій частині алгоритму попит від вузла i до пункту призначення r, gir,
призначається відповідно до оптимальної стратегії ?̅?. Частка попиту вузла i на
ланках a ∈ ?̅? відповідає його частоті, див. рівняння (5). Обсяги можна
оновлювати одночасно, оскільки відрізки оцінюються у зворотному
топологічному порядку (зменшення TTT'i + ca), і тому можна перевірити кожний
відрізок лише по одному.
Тест на привабливість може бути описаний нерівністю (6) нижче та
стверджує, що лінія i (другий вибір, лінія з наступним найкоротшим часом
подорожі порівняно з першим вибором) є привабливою, якщо:
(6)
Це означає, що час у дорозі для лінії i менший, ніж загальний очікуваний
час у дорозі для першого вибору. Тому буде краще сісти на лінію i, якщо вона
прибуде на зупинку зараз, ніж чекати лінії першого вибору. Щоб обчислити
кінцевий очікуваний загальний час у дорозі для всіх комбінованих привабливих
ліній, формулюється наступне рівняння.
(7)
1.2.3 Програмне забезпечення Emme 4
При оновленні Emme до Emme 4, з’являться деякі нові функції та більше
налаштувань, які можна використовувати під час калібрування моделей.
Найактуальнішою процедурою призначення для великих міст є, згідно з
посібником Emme 4 [26], розширене призначення транзиту. Тому це буде більш
детально описано, ніж інші завдання в Emme 4, і всі факти базуються на
оперативному посібнику [26] та науковому звіті Сепеда, Комінетті та Флоріана
[27], який описує деякі нові функції в Еммі 4.
Розширене транзитне призначення
26
Це призначення базується на стандартному призначенні транзиту та теорії
оптимальної стратегії, але в цій розширеній версії можна змоделювати вибір
з’єднувача. Іншими словами, мандрівників можна розділити між кількома
з’єднувачами замість вибору лише найкоротшого з’єднувача. Крім того, вибір
маршруту більш чутливий до часу в дорозі (крім довжини), тому лінії з меншою
частотою та коротшим часом у дорозі все ще можуть бути привабливим
варіантом.
У розширеному призначенні транзиту все ще є параметри, які
використовуються в стандартному призначенні транзиту, і деякі додаткові
додаткові параметри, такі як вартість посадки, транспортного засобу та
додаткових транзитних витрат. Вартість посадки – це штраф, пов’язаний із
кожною посадкою (як початковою, так і пересадкою). Вартість транспортного
засобу буде помножено на вагу часу транспортного засобу та може бути
постійною, указати сегмент, відрізок, вузол або лінію транзиту. Вартість буде
додана до загального часу в дорозі. Вартість допоміжного транзиту може бути
постійною, вузлом або ланкою вказано, множиться на вагу та додається до
загального допоміжного часу в рівнянні TTT.
Існує оптимальний вибір у джерелі, де логіт-розподіл можна
використовувати для розділення потоків на різні конектори. Якщо логіт-розподіл
не використовується, усі мандрівники залишать вихідний вузол через конектор,
який найменше впливає на час подорожі. Логітарний розподіл вказується в
точках вибору і може бути визначений для всіх джерел або тих, що мають
спеціальний атрибут. У точках вибору розподіл може бути застосований до всіх
конекторів або лише до ефективних, що означає конектори, які наближають
мандрівника до вузла призначення. При використанні розподілу logit для вузлів
із зазначеними атрибутами це дає змогу використовувати різні набори вибору в
різних джерелах (1 вказує на використання logit для всіх з’єднувачів, а - 1 для
застосування лише до ефективних).
Функція logit у програмі містить два параметри, масштаб і скорочення.
27
Шкала використовується для обчислення ймовірностей, на яких базується
пропорція. Параметр масштабу має бути 0 або більше. Якщо він дорівнює 0,
пропорції для всіх роз’ємів у наборі вибору однакові. Більші значення дадуть
найкращому роз’єму вищі пропорції. Параметр усічення використовується для
видалення з’єднувачів, пропорції яких вважаються занадто малими. З’єднувачі з
пропорціями, меншими за заданий параметр скорочення, не включаються, доки
пропорції інших з’єднувачів не перевищуватимуть значення параметра.
Пропорції, обчислені для з’єднувачів, можна змінити на фіксовані пропорції
за допомогою визначеного користувачем атрибута відрізків. Пропорції мають
бути від 0 до 1, а сума для всіх з’єднувачів із джерела має бути 1. Це можна
зробити лише для підмножини джерел, а для решти джерела атрибут відрізку має
бути – 1.
У розширеному призначенні транзиту також можливо мати розподіл логітів
на регулярних вузлах із допоміжним вибором транзиту. При використанні
логічного призначення мандрівники на вузлі враховують:
• Чекайте на вузлі автомобіль привабливої лінії;
• Залиште вузол найкращою допоміжною транзитною лінією або будь-якою
ефективною допоміжною транзитною лінією.
Усі мандрівники в призначенні без logit чекають на транспортний засіб або
залишають вузол допоміжним транзитним сполученням. При використанні
логічного призначення також можна розділити мандрівників між перебуванням
на борту та висадкою. Мандрівники, які висаджуються, повинні виїхати
допоміжним транзитом. Отже, поділ буде лише якщо:
• Лінія, якою їдуть мандрівники, також приваблива у вузлі
• Вийти з вузла можна допоміжними транзитами
Пропорції висадки або одного разу, хто залишається на борту,
обчислюються на основі опору до пункту призначення. Для оригінальних вузлів
використовуються ті самі параметри функції logit, що й у функції.
У стандартному призначенні транзиту розподіл потоку базується на частоті,
28
але в розширеному призначенні є вибір використання розподілу на основі
частоти та часу проходження до місця призначення. Це означає, що швидкі лінії
з нижчою частотою є більш привабливими, що призводить до більш плавних змін
потоку. Цей параметр можна вибрати для всієї мережі або для окремих вузлів.
Також можна заборонити шляхи від з’єднувача до з’єднувача, що означає,
що мандрівники не можуть подорожувати лише через з’єднувачі, щоб дістатися
до місця призначення. Це підходить для мереж з великою кількістю зон або
щільним населенням.
Призначення перевантаженого транспорту
Це розподіл рівноваги, який включає в себе модель перевантаження на
борту на основі функцій витрат, що залежать від обсягу. Вартість зв’язку
залежить від обсягів транзиту (кількості мандрівників, які користуються
мережею громадського транспорту), які будуть відображати сповільнення
транспортного засобу через кількість пасажирів і дискомфорт для пасажирів,
який посилюватиметься, коли транспортний засіб стане переповненим. Затор на
борту транспортного засобу моделюється шляхом додавання функцій до
транзитних сегментів, які перетворюють ефект скупчення людей на затримку на
сегменті. Це призводить до нелінійної моделі, яка вирішується за принципом
оптимальності користувача Wardrop, моделлю транзитної рівноваги.
Ємне транзитне призначення
Це призначення використовує метод для отримання транзитних потоків,
який відповідає тому факту, що транзитні сегменти стають перевантаженими. Це
рівноважне призначення транзиту, яке враховує функції заторів у транспортному
засобі (такі самі, як у призначенні перевантаженого транзиту) та збільшення часу
очікування на зупинках, яке залежить від пропускної здатності ліній
громадського транспорту. У кожній ітерації рівноважного процесу виконується
розширене призначення транзиту, і мета полягає в тому, щоб розділити потік
таким чином, щоб загальний час у дорозі був однаковим для кожного пасажира.
Стохастичне призначення транзиту
29
У стохастичних транзитних призначеннях обчислюється середнє значення
кількості призначень на основі стратегії. Час проходження сегментів,
сприйманий прогрес і/або фактори сприйняття змінюються різними функціями
розподілу (рівномірний, нормальний або гамбель). Обсяги для сегментів
транзиту отримують шляхом обчислення середнього значення окремих
призначень транзиту, кожен з яких базується на різному наборі випадкових
факторів.
Детерміноване призначення транзиту
Це призначення на основі розкладу, яке включає інформацію про
відправлення та прибуття за оптимальним маршрутом. Мандрівники знають, о
котрій годині вони хочуть залишити вихід або прибути в пункт призначення.
Буде використано шлях із найменшою вартістю. Це завдання корисно
використовувати, коли прогрес є різним протягом періоду навчання.
1.3 Теоретичні основи предмета дослідження
1.3.1 Коротка історія проблеми маршрутизації міського транспорту (UTRP)
Спроби автоматизувати оптимізацію маршрутів міського громадського
транспорту налічують багато десятиліть за допомогою різноманітних
методологій і алгоритмів оптимізації. Зазвичай вони діляться на дві категорії:
точні або евристичні методи. Точні математичні підходи (Bussieck 1998; Chien
and Schonfeld 1997; Guan et al. 2006; van Oudheusden et al. 1987) були перевірені
в багатьох дослідженнях. Основним обмеженням таких методів є труднощі
пошуку оптимальних рішень у мережах великого розміру, враховуючи
комбінаторний характер проблеми, і це призвело до їх нездатності масштабувати
до прикладів практичного розміру.
Через ці недоліки дослідження UTRP потім перемістилися в бік прийняття
евристичних методів вирішення проблеми, завдяки їхній здатності вирішувати
проблеми великого розміру. Деякі евристичні методи базуються на евристичних
процедурах побудови, які намагаються побудувати оптимальні набори
30
маршрутів громадського транспорту з нуля. Прикладом такого методу є
евристичний алгоритм, розроблений Сімонісом (1981). Цей метод починається зі
створення маршруту за допомогою найкоротшого шляху між точками попиту з
найвищою щільністю, а потім видаляє попит, задоволений цим маршрутом.
Процес повторюється до наступних точок найвищого попиту, доки не буде
досягнуто максимальної кількості маршрутів. Інші евристичні методи побудови
описані в (Baaj and Mahmassani 1995; Franz 1975; Silman 1974; Sonntag 1977).
Друга група евристичних методів намагається покращити заданий вхід
наборів маршрутів. Ці методи оптимізації зазвичай базуються на
метаевристичних методах, таких як пошук табу (наприклад, K1I19 і Gok 2014;
Pacheco та ін. 2009), імітований відпал (наприклад, Fan і Mumford 2010; Fan і
Machemehl). 2006) оптимізація мурашиної колонії (наприклад, Пурзахеді та
Сафарі 2011; Ю та ін. 2012), оптимізація бджолиної колонії (наприклад, Ніколіч
і Теодорович 2013, 2014), або генетичні алгоритми (GA) (наприклад, Heyken
Soares та ін. 2019; John та ін. 2014; Nayeem та ін. 2014; Pternea та ін. 2015). У
деяких дослідженнях початкові набори маршрутів виведені з існуючої мережі
громадського транспорту досліджуваних територій. Однак евристична
процедура побудови часто використовується для створення початкових наборів
маршрутів. Приклади такої комбінації можна знайти в Ahmed et al. (2019),
Хейкен Соарес та ін. (2019), K1I19 і Gok (2014) і Мамфорд (2013).
Незважаючи на величезну кількість досліджень комп’ютерних рішень для
UTRP, лише деякі дослідження фактично використовувалися в процесах
реального планування (Walter 2010). Одним із рідкісних прикладів є робота
Pacheco et al. (2009), який описує оптимізацію автобусної мережі в Бургосі,
Іспанія, щодо часу очікування та тривалості поїздки. Отримані рішення значно
покращилися порівняно з рішеннями, створеними планувальниками міських
транспортних органів з використанням тих самих даних про транзитну мережу.
Іншим прикладом є дослідження 2012 року Cipriani et al. (2012) у співпраці з
агентством мобільності Риму, Італія. Він включав застосування генетичного
31
алгоритму на неорієнтованому графі, що представляє мережу вулиць Риму.
Результати показують покращення існуючої мережі автобусних маршрутів з
точки зору часу очікування, витрат оператора та незадоволеного попиту. За
словами авторів, агентство мобільності Риму почало впроваджувати свої
результати в 2012 році. Багато інших досліджень порівнюють свої результати з
реально існуючими маршрутами, показуючи, що їхні методи можуть призвести
до покращення існуючих послуг (наприклад, див. Ahmed et al. 2019).; Bagloee та
Ceder 2011; Bielli та ін. 2002; Heyken Soares та ін. 2019). Однак результати цих
досліджень не були перевірені в реальних процесах планування.
1.3.2 Інтерфейс алгоритмів UTRP і програмного забезпечення моделювання
транспорту
Основним завданням для взаємодії алгоритмів UTRP і програмного
забезпечення для моделювання макроскопічного транспорту, такого як Visum
або Emme, є впоратися з відмінностями між ненаправленими з’єднаннями, що
використовуються в алгоритмах UTRP, і спрямованими з’єднаннями, які
використовуються в макроскопічному моделюванні міського масштабу
(докладніше про це в розділі 3)..
Усі дослідження UTRP, які до цього часу поєднували свої алгоритми з
програмним забезпеченням моделювання макроскопічного транспорту,
обходили ці проблеми, використовуючи лише представлення мережі з
ненаправленими з’єднаннями. Одним із таких випадків є згадане вище
дослідження в Римі (Cipriani et al. 2012), де прикладний алгоритм поєднується з
Emme. Інші приклади Alt і Weidmann (2011), а також Bagloee і Ceder (2011)
використовували Visum і Emme, відповідно, і включили процедури для побудови
відповідних представлень мережі.
Поки що найзагальнішим інструментом для автоматичної оптимізації
мережі громадського транспорту в програмному забезпеченні для моделювання
транспорту є алгоритм пропозиції ліній для Visum, розроблений самою PTV у
32
2006 році (Nokel 2006). Цей інструмент застосовує евристичний алгоритм до
існуючої моделі мережі Visum. Алгоритм спочатку генерує палітру маршрутів-
кандидатів між попередньо вибраними зупинками. Потім ці маршрути-
кандидати окремо оцінюються у Visum, а маршрут, який користується
найбільшим попитом, назавжди додається до мережі. Цей крок можна
повторювати скільки завгодно часто. Інструменту потрібен лише мінімальний
інтерфейс, оскільки алгоритм просто контролює кінцеві точки маршрутів та
ініціює їх оцінку. Усі інші аспекти обробляє Visum, і алгоритм не змінює існуючі
маршрути. Хоча алгоритм успішно використовувався щонайменше у двох
академічних дослідженнях (Marauli 2011 рік; Walter 2010), він залишався
прототипом і ніколи не був повністю розроблений в офіційне розширення Visum.
На жаль, він більше не працює в останніх версіях Visum.
1.3.3 Оптимізація громадського транспорту у Visum за допомогою
гіперевристики вибору
Метою цієї роботи є створення інтерфейсу між мережевою моделлю UTRP
і програмним забезпеченням для моделювання макроскопічного транспорту
Visum, а також використання інтерфейсу для оптимізації маршрутів
громадського транспорту Visum за допомогою загальної методології пошуку
гіперевристики вибору.
Евристика (від др.-грец. εὑρίσκω – «відшукую», «відкриваю») – наукова
галузь, що вивчає специфіку творчої діяльності.
У сучасному розумінні евристика – це теорія та практика організації
виборчого пошуку при вирішенні складних інтелектуальних завдань [5].
Гіперевристика (гіперевристичний алгоритм) – евристичний метод пошуку,
спрямований на автоматизацію процесу вибору, комбінування, узагальнення чи
адаптації кількох простіших евристик (або їх частин) для ефективного вирішення
обчислювального завдання. Також можна зустріти і таке визначення:
"використання (мета-)евристик для вибору (мета-)евристик".
33
Основна перевага гіперевристики – побудова ефективних методів
вирішення класу проблем, ніж вирішення одиночної конкретної задачі класу.
Головною ідеєю гіперевристичних алгоритмів є пошук та вироблення деякої
кількості простих евристик, кожна з яких має свої слабкі та сильні місця, а потім,
побудова механізму для вибору з набору простих евристик залежно від
поточного стану рішення.
Гіперевристики можна розділити на дві групи:
− Засновані на виборі евристик
− Засновані на генерації евристик
Гіперевристики зазвичай спрямовані на зменшення кількості інформації з
предметної галузі в алгоритмах. Результуючий алгоритм має бути швидким і
зручним для реалізації, але в той же час досить надійним для вирішення класу
завдань. З іншого боку, необхідно, щоб підсумковий алгоритм мав хороші
результати проти метаевристиками кожної з завдань.
Visum — це пакет програмного забезпечення для макроскопічного
моделювання транспорту, який поєднує приватний (PrT) і громадський (PuT)
транспорт в єдину модель і надає широкий набір методологій. Це продукт
компанії PTV, що базується в Карлсруе, Німеччина, і доступний для
комерційного використання з кінця 90-х (Friedrich et al. 1999). Нині його
використовують транспортні планувальники та аналітики по всьому світу.
Результати, представлені в цій статті, були отримані з використанням Visum 17,
яка була останньою версією, випущеною на початку цього проекту.
На додаток до різноманітних інструментів аналізу, однією з головних
причин використання Visum для цієї роботи є можливість керувати ним за
допомогою сценаріїв Python через Visum COM-API (PTV AG 2014). Ця
бібліотека надає низку функцій інтерфейсу для керування Visum за допомогою
сценаріїв і отримання будь-якої необхідної інформації. Такі сценарії лягли в
34
основу даної роботи.
Враховуючи складність програмного забезпечення Visum і його величезну
кількість доступних функцій і інструментів, ми повинні обмежити описи його
структури та можливостей лише тими, які життєво важливі для цієї роботи. Ми
обговоримо відповідні структури даних мережевих моделей Visum у розділі. 3.2
і параметри аналізу, які ми використовуємо в Розд. 5.5. Для отримання
додаткової інформації ми відсилаємо зацікавленого читача до посібника Visum
(PTV AG 2018).
Гіперевристика відбору – це методології пошуку, мотивовані ідеєю
узагальнення методів пошуку для кількох проблемних областей з мінімальною
адаптацією. Вони вперше були застосовані для вирішення UTRP у Ahmed et al.
(2019). У цій роботі тридцять гіперевристик вибору, що поєднують різні
комбінації методів вибору та прийняття ходу з різними характеристиками,
перевіряються на наборі відомих еталонних екземплярів. Серія експериментів і
статистичних порівнянь між тридцятьма методами виявила успіх онлайн-методу
відбору, натхненного прихованою моделлю Маркова, порівняно з іншими
методами відбору. Крім того, найефективніший алгоритм успішно знаходив
окремі рішення високої якості за дуже короткий час у порівнянні з найкращими
опублікованими рішеннями. Той самий виграшний підхід був застосований у
Ahmed et al. (2019) на наборі контрольних екземплярів, що представляють міські
райони, і довів, що він може перевершити продуктивність генетичного
алгоритму NSGAII.
Гіперевристична структура вибору має багато переваг, що робить її
хорошим кандидатом для застосування в цій роботі. По-перше, це одноточкова
основа, тобто для неї потрібне лише одне початкове рішення. Це дозволяє нам
витягти існуючу мережу громадського транспорту з даної моделі мережі Visum і
використовувати її як вихідне рішення. По-друге, підтримка єдиного рішення з
одночасним його ітераційним вдосконаленням під час пошуку робить взаємодію
з Visum через процедури інтерфейсу простою. Крім того, відносно короткий час
35
роботи гіперевристичних методів значно додає їм привабливості. Подальший
опис системи гіперевристики вибору наведено в розділі. 5.
PuT: Відноситься до громадського транспорту.
PrT: Відноситься до приватного транспорту.
G: Граф з’єднаних вершин і ребер. Використовується для
представлення графіка UTRP.
v: Вершина графа UTRP, що належить множині вершин V.
Представляє зупинку в моделі мережі Visum. (Терміни «стоп» і
«вершина» можуть використовуватися як взаємозамінні в графі
UTRP.)
u: кінцева вершина (∈ ��), вершина, з якої дозволено починати та
закінчувати маршрут r.
A: Матриця суміжності визначає зв'язність графа G. A i, j = 1 означає,
що існує прямий зв’язок між вершиною i та вершиною j. У випадку A
i, j = 0 вершини не з’єднані безпосередньо.
r: Маршрут у графі UTRP як шлях, що з’єднує кілька вершин. У Visum
маршрут відповідає лінії. Передбачається, що він двонаправлений.
s: зупинка в мережі Visum. Представляє вершину в графі UTRP.
sp: Зупинка в мережі Visum, пов’язана рівно з однією зупинкою. Може
використовуватися для визначення курсу маршруту лінії.
l: рядок PuT у Visum. Просторовий хід лінії визначається її трасами.
lr: Маршрут лінії у Visum. Належить точно одній лінії та визначає
просторовий хід цієї лінії для одного напрямку руху. Маршрути ліній
визначаються пунктами зупинок.
Рисунко 1.2 Інформаційне поле 1: короткий виклад важливих понять, які
використовуються в наступних розділах
36
РОЗДІЛ 2. МЕТОДИ ДОСЛІДЖЕННЯ ПРОБЛЕМИ МАРШРУТИЗАЦІЇ
МІСЬКОГО ТРАНСПОРТУ
2.1 Структури даних маршрутизації міського транспорту
2.1.1 Визначення проблеми маршрутизації міського транспорту (UTRP)
Майже всі попередні підходи до UTRP вибирають представлення доступної
вуличної (або залізничної) мережі у вигляді графіка G = (V,E). Вершини
V={v1,v2,...,v|V|} представляють точки доступу та обміну, а ребра E={e1,e2,…,e।E।}
є прямі зв'язки між ними. Використовуючи ці визначення, PuT маршрут r
(наприклад, автобусна лінія) може бути представлений списком безпосередньо
підключених вершин. Зазвичай вважається, що маршрут є двонаправленим,
тобто транспортні засоби після завершення подорожі в одному напрямку можуть
розвернутися та здійснити таку ж подорож у протилежному напрямку. Щоб це
було можливим у міській обстановці, важливо, щоб усі маршрути починалися та
закінчувалися у визначених кінцевих вершинах U={u1,u2,...,u|U|}∈V, щоб
дозволити розвороти. Дотримуючись цих визначень, мережу PuT певного виду
транспорту можна описати як набір з’єднаних маршрутів R = {r1,r2,...,r।R।}, який
представляє рішення UTRP як задачу оптимізації. Цей «набір маршрутів» має
бути з’єднаний таким чином, щоб кожен маршрут мав принаймні одну спільну
вершину з одним або кількома іншими маршрутами в наборі маршрутів.
У своїй найпростішій формі структура графа G задана матрицею суміжності
A।V|×|V|. Ця матриця визначає зв’язність графа наступним чином: якщо два вузли i
та j безпосередньо з’єднані, відповідний запис у матриці суміжності дорівнює
Ai,j=1, інакше Ai,j=0. Ця матриця має бути симетричною відповідно до правила,
що маршрути вважаються двонаправленими. Основна перевага таких графів для
вирішення UTRP полягає в тому, що вони дозволяють обмежувальні маршрути
складати лише з безпосередньо з’єднаних вершин. Це виключає багато
можливих помилкових рішень і, таким чином, різко скорочує простір пошуку.
Крім того, для оцінки потрібна інформація про попит на подорожі та час
подорожі між будь-якими двома вершинами на графі. Ця інформація зазвичай
37
надається у формі двовимірних матриць: матриці часу в дорозі та матриці
попиту. Обидві матриці зазвичай симетричні. Матриця часу подорожі дає час
подорожі між прямо з’єднаними вершинами. Різниця в часі подорожі між
напрямками (наприклад, у результаті вулиць з одностороннім рухом) зазвичай
не враховується. Матриця попиту визначає кількість мандрівників між будь-
якими двома джерелами попиту. У переважній більшості досліджень вершини V
використовуються як джерела попиту. Лише приблизно кожне п’яте
дослідження використовує зонну структуру попиту, схожу на структуру, що
використовується в моделюванні макроскопічного транспорту (описано нижче)
(Heyken Soares 2020a).
2.1.2 Структура даних Visum
Вхідні дані для транспортних моделей Visum також включають попит на
подорожі та мережеву модель доступної транспортної інфраструктури.
Як стандартна практика в моделюванні макроскопічного транспорту, попит
на подорожі у Visum агрегується на рівні зон (Z={z1,z2,...,z।Z।}) і надається у формі
початкової точки матриця призначення. Матриця попиту D|Z|х|Z| визначає, скільки
поїздок походять із зони zi та подорожують до зони zj. Дані попиту надаються як
окремі матриці для PuT і різних режимів PrT (наприклад, автомобілі). Однак
можна спочатку надати попит як одну матрицю, що об’єднує всі поїздки, а потім
використати процедуру вибору режиму, щоб розділити попит на окремі матриці
для різних режимів подорожі (докладніше про це в розділі 5.5.2).
Модель мережі Visum також базується на графовій структурі, хоча вона
більш детальна, ніж граф UTRP, описаний вище. Вулиці або сегменти залізниць
представлені відрізками, які можна використовувати для певних видів
транспорту. Відрізки складаються з двох окремих мережевих об’єктів, по одному
для кожного напрямку руху. Кожен із цих об’єктів може мати різні значення
атрибутів, наприклад дозволену швидкість і пропускну здатність щодо кількості
транспортних засобів. Вулиці з одностороннім рухом можуть бути представлені
блокуванням одного напрямку зв’язку для всіх режимів. Вузли на початку і в
38
кінці кожної ланки визначають положення перехресть і з'єднань в мережі. Які
повороти дозволені для якого режиму на представлених стиках, можна
визначити у властивостях вузлів. Кожна зона (z ∈ Z) повинна бути з'єднана
принаймні з одним вузлом за допомогою з'єднувача, для виходу та входу в зону
до мережі зв'язку через цей вузол з'єднання.
Модель мережі Visum також включає інші елементи для представлення
доступних ліній PuT і точок пересадки. Точки обміну PuT визначаються трьома
рівнями. «Точка зупинки» — це найнижчий рівень, що вказує фактичне місце
зупинки транспортних засобів (наприклад, сегмент платформи поїзда). Точки
зупинки можуть бути розміщені на вузлах або відрізках і можуть
використовуватися всіма лініями PuT, що проходять ці мережеві об’єкти. Точка
зупинки, розміщена на відрізках, може бути доступною з обох сторін або може
бути обмежена для використання в певному напрямку. «Зупинка», середній
рівень, включає одну або більше точок зупинки (наприклад, платформу на
вокзалі). Усі пункти зупинки однієї зони зупинки вважаються миттєво
з’єднаними, тоді як пересадка між зонами зупинки потребує певного часу
ходьби. Крім того, вузол може бути призначений для зони точки зупинки, щоб
забезпечити доступ до ширшої моделі мережі, особливо до з’єднувачів, що
з’єднують вузли із зонами. «Зупинка», найвищий рівень, включає одну або кілька
пов’язаних зон зупинки (наприклад, вокзал) і є рівнем, на якому призначається
час ходьби між різними зонами зупинки. Зони зупинок не відіграють великої ролі
в цій роботі, і ми припустимо, що зупинки та пункти зупинок безпосередньо
пов’язані, щоб спростити пояснення.
Лінії PuT також визначені на кількох різних рівнях. На найвищому рівні
знаходиться «лінія». Кожна лінія у Visum належить рівно одній транспортній
системі. Просторовий хід лінії визначається її трасами. Одна лінія може
об’єднувати кілька лінійних маршрутів, які визначаються списками точок
зупинок, які потрібно пройти в заданому порядку. Технічно список, що визначає
маршрут лінії, містить як точки зупинок, так і вузли. Однак достатньо надати
39
лише точки зупинки, оскільки Visum може автоматично додавати потрібні вузли
за допомогою пошуку найкоротшого шляху. Маршрути ліній таким чином
спрямовані, і більшість ліній матимуть принаймні два маршрути ліній, по одному
для кожного напрямку руху. Особливим випадком є кільцеві лінії, визначені
однолінійними маршрутами, що починаються та закінчуються в одній зупинці.
Кожному маршруту лінії надається «профіль часу», який описує, серед інших
атрибутів, час у дорозі між окремими точками зупинки. До маршрутів ліній
можна додати «автомобілі» з конкретним часом відправлення, щоб створити
детальний розклад із зазначенням часу відправлення та прибуття на окремі
зупинки.
2.1.3 Інтерфейс між структурами даних UTRP і Visum
На основі порівняння стандартної графової структури UTRP із відповідною
структурою даних Visum є ключові запитання, на які необхідно відповісти перед
побудовою інтерфейсу між ними. По-перше, нам потрібно визначити, чи буде
оптимізація виконуватися на рівні маршрутів чи ліній. Оптимізація маршрутів
ліній окремо може призвести до значних відхилень між маршрутами ліній, які
належать одній лінії. На практиці це було б небажаним. Тому ми вирішили
провести оптимізацію на рівні ліній.
40
Рисунок 2.1 Схематична мережа вулиць.
a – Схема вуличної мережі з одним автобусом (фіолетовий) і розташуванням
його зупинок (фіолетові точки).
b – Представлення a у вигляді моделі мережі Visum. Показано відрізки
(чорні стрілки) і вузли (сині крапки), а також точки зупинки (трикутники) і їх
зупинки (зелені кружечки). Точки зупинки C і D є частиною зупинки 3.
c – граф UTRP із зупинками в b як вершинами та можливими прямими
зв'язками між ними як ребрами.
d – Схематичне зображення двох лінійних маршрутів у тій самій моделі
мережі, що й b, що представляє автобусну службу, показану в (a). Шлях
маршруту лінії визначається лише точками зупинки, хоча маршрутизація
відбувається вздовж вузлів і зв’язків основної моделі мережі з усіма
обмеженнями, визначеними для неї. Разом обидва маршрути утворюють одну
лінію.
e – маршрути лінії від d як двонаправлений список вершин у графі UTRP
Друге питання полягає в тому, чи повинні вершини графа UTRP
представляти зупинки або точки зупинки в моделі мережі Visum. Щоб відповісти
на це запитання, ми повинні враховувати, що деякі точки зупинки в моделі
мережі Visum можуть бути обмежені для використання лише в певних
41
напрямках. Це суперечить тому факту, що маршрути в структурі UTRP
вважаються двонаправленими. Однак у більшості таких випадків зупинки, до
яких належать ці орієнтовані точки зупинки, також включають інші зупинки,
доступні з кількох напрямків (див. Розділ 2.1.2 і Рис. 1). Бувають випадки, коли
до зупинки можна дістатися лише з одного боку. Однак у всіх мережах,
досліджених у цій роботі, таких випадків було дуже мало і, здається, вони не
мали значного впливу на результати. Тому на сучасному етапі роботи ми
залишили їх без уваги. На майбутнє ми плануємо запровадити додаткові
процедури, які адекватно вирішують цю проблему. Тому ми вирішили, що
вершини графа UTRP мають представляти зупинки в моделі мережі Visum, а не
точки зупинки.
Нарешті, необхідно вирішити, які зупинки (тобто вершини) слід вважати
кінцевими вершинами в графі UTRP. У PTV AG (2018) рекомендовано
використовувати виключно точки зупинок, розміщені на вузлах як початкові або
кінцеві точки маршрутів ліній. Однак у мережевих моделях, які ми
використовували, є багато існуючих маршрутів ліній, які не дотримуються цієї
рекомендації. Тому ми вибираємо як кінцеві вершини зупинки, які
задовольняють принаймні одну з наступних умов: (a) Маючи принаймні одну з
їхніх точок зупинки, розміщену на вузлі. (b) Принаймні одна з їхніх зупинок є
початком або кінцем існуючого маршруту лінії. Перераховані тут умови були
обрані для оптимізації автобусних ліній, описаних у Розд. 2.1.3. Для інших
сценаріїв або у разі оптимізації інших режимів PuT може знадобитися адаптувати
ці умови. Також можливий ручний вибір кінцевих вершин.
2.2 Процеси інтерфейсу між алгоритмами UTRP і Visum
На основі обговорення в розд. 2.1.2, ми можемо сформулювати два основні
процеси інтерфейсу для трансляції інформації маршрутизації між алгоритмами
UTRP і Visum. Перший полягає у вилученні зв’язків суміжності між зупинками,
які будуть використовуватися як основа для змін маршруту під час оптимізації.
42
Цей процес буде представлено в Розд. 2.2.1. По-друге, це процес перетворення
змінених маршрутів (тобто неорієнтованих списків зупинок) у пари лінійних
маршрутів (тобто спрямованих списків точок зупинок), щоб забезпечити
реалізацію у Visum для оцінки. Цей процес буде описано в розділі. 2.2.2.
Результати обох процедур інтерфейсу залежать від режиму, оскільки деякі
відрізки в моделі мережі Visum можуть бути доступні лише для певних режимів.
2.2.1 Вилучення графа UTRP із моделі мережі Visum
Процес вилучення відносин суміжності між зупинками для режиму PuT m із
заданої моделі мережі Visum описано в алгоритмі 1. Він починається зі створення
матриці зв’язності точок зупинки Cm. Ця матриця має три типи записів: ����
��,�� = 0
вказує на те, що немає зв’язку між двома точками зупинки i та j, означає ����
��,�� = 1
наявність ����
��,�� = 0.5 прямого зв’язку між точками зупинки i та j та вказує на те,
що з’єднання існує, але воно непряме (тобто з’єднання проходить через інші
точки зупинки). Крім того, у цьому процесі також створюється матриця відстані
Δm, яка записує час подорожі між кожною парою точок зупинки (її використання
описано в розділі 2.2.2).
43
Алгоритм 1: Алгоритм для створення матриці зв’язності точки зупинки та
матриці відстані для режиму m у даній мережі Visum.
Дані: Visum Network
Результат: матриця зв’язності Cm, матриця відстані Δm
1 початок
2 для кожної точки зупинки i у мережі Visum виконати
3 для кожної точки зупинки j у мережі Visum виконати
4 Побудуйте тестову лінію маршруту l режиму m між i та j.
5 якщо l може бути побудовано тоді
6 ∆��
��,�� ←час у дорозі між i і j
7 �� ←кількість точок зупинки в l
8 якщо n = 2, тоді
9 ����
��,�� = 1
10 інакше
11 ����
��,�� = 0.5
12 інакше
13 ����
��,�� = 0
14 повернення Cm, Δm, мережа Visum назад до початкового стану.
Сценарій Python, що використовує функції з Visum COM-API,
використовується для отримання необхідної інформації з даної моделі мережі
Visum. Цей сценарій демонструє алгоритм 1. Для кожної можливої комбінації
точок зупинки i, j алгоритм намагається побудувати тестовий маршрут лінії, що
починається в i і закінчується в j, шляхом пошуку найкоротшого шляху вздовж
відрізків, відкритих для режиму m. Будівництво буде успішним лише тоді, коли
Visum вдасться знайти найкоротший шлях від i до j з урахуванням усіх обмежень
даної моделі мережі. Усі інші зупинки, розташовані на цьому шляху,
44
автоматично підключаються до побудованого маршруту лінії. Якщо маршрут
тестової лінії містить більше двох точок зупинки (не лише i та j), зв’язок між i та
j вважається непрямим і записується в матрицю зв’язності як ����
��,�� = 0.5. Якщо до
маршруту тестової лінії не підключено жодних інших зупинок, з’єднання
вважається прямим і записується як ����
��,�� = 1. У будь-якому випадку Visum
розраховує час проїзду побудованого маршруту лінії та записує його в матрицю
відстані як ∆��
��,��. Якщо процес пошуку найкоротшого шляху між i та j не вдається,
ці точки зупинки вважаються незв’язаними (����
��,�� = 0). Після того, як алгоритм
пройде через усі пари точок зупинки, модель мережі Visum повертається до
початкового стану.
Після побудови матриці зв’язності точок зупинки Cm матриця суміжності
����
|��|×|��| неорієнтованого графа UTRP будується за такими правилами: дві
зупинки X і Y вважаються зв’язаними (����
��,�� = ����,�� = 1), якщо і тільки якщо
принаймні одна точка зупинки x, що належить зупинці X, безпосередньо
пов’язана з принаймні однією точкою зупинки y*, що належить зупинці Y
(����
��,��∗ = 1), і принаймні одна точка зупинки y, що належить зупинці Y,
опосередковано пов’язана принаймні з однією точкою зупинки x*, що належить
зупинці X (����
��,��∗ ≥ 0.5). У будь-якому іншому випадку, навіть якщо всі точки
зупинки двох зупинок X і Y опосередковано з’єднані, X і Y вважаються
несусідними (����
��,�� = ����
��,�� = 0).
45
Рисунок 2.2 Схема вуличної мережі з п’ятьма зупинками (1-5) і сімома
зупинками (від A до G). Шоста зупинка передбачається уздовж вулиці праворуч.
Маршрут UTRP [1, 2, 3, 4, 5] перетворюється на два списки точок зупинки за
допомогою таблиці перетворення праворуч. Таблиця перетворення дає
правильну точку зупинки для однієї зупинки, використовуючи комбінацію трьох
зупинок (тобто вершин), що містять цю зупинку та її суміжні зупинки. Отримані
списки точок зупинки відображаються синім кольором (від A, через B до D, E і
G) і червоним (від G, E і D через C до A). Для кінцевих вузлів, 1 і 5, надається
трійка вершин із порожніми полями для використання на початку та в кінці
маршруту відповідно
2.2.2 Перетворення маршрутів UTRP на лінійні маршрути Visum
Під час процесу оптимізації змінені маршрути потрібно впровадити у Visum
для оцінки. Для цього списки вершин (тобто зупинок) у цих маршрутах потрібно
перетворити на два списки точок зупинок, по одному для кожного напрямку
руху. Кільцеві лінії, де перша і остання зупинки ідентичні, вимагають лише
одного маршруту. Як описано в розд. 3, одна зупинка може мати кілька точок
зупинки. Тому необхідно вибрати правильну комбінацію точок зупинки, які
представляють конкретну комбінацію вершин. Це робиться за допомогою
таблиці перетворення Ym. Його використання показано на рисунку 2.2.
Припустімо, що ми маємо маршрут ri, який містить наступний набір вершин
46
у такому порядку: {1, 2, 3, 4, 5}, а вершини 2 і 4 пов’язані з кількома точками
зупинки, як показано на рисунку 2.2. Щоб перетворити маршрут ri на список
точок зупинки, нам потрібно вибрати правильну комбінацію точок зупинки, які
представляють певний напрямок руху через вершину. Для вершин, пов'язаних з
однією точкою зупинки, цей вибір є тривіальним. Однак для вершин, пов’язаних
із кількома точками зупинки, процес вибору залежить від суміжних вершин і
порядку цих вершин у маршруті. У прикладі, наведеному на рисунку 2.2, точка
зупинки, що представляє зупинку 2, може бути B (якщо порядок 1, 2, 3) або C
(якщо порядок 3, 2, 1).
Таблиця перетворення Ym, яка використовується для вибору правильних
точок зупинки для кожної вершини, показана на рисунку 2.2. Перші три стовпці
дають можливий потрійний набір з’єднаних вершин, по одній комбінації в
кожному рядку. Кожна комбінація розглядається двічі, один раз для кожного
напрямку руху. Четвертий стовпець визначає вибір точки зупинки для середньої
вершини в комбінації. Для терміналів використовуються додаткові потрійні
набори з порожніми полями для визначення точок зупинки на початку та в кінці
маршруту лінії.
Алгоритм 2: Алгоритм створення таблиці перетворення для режиму m
Дані: набір усіх вершин V, матриця суміжності Am, матриця зв’язності Cm,
матриця відстані Δm
Результат: Таблиця перетворення Ym
1 почати
2 для кожної Y ∈ V виконати
3 К ← усі Вершини K ∈ V з Am(Y,K) = 1
4 для кожної X ∈ K виконати
5 для кожної Z ∈ K виконати
6 Ξ ← Точки зупинки, представлені вершиною X
7 Φ ← Точки зупинки, представлені вершиною Y
8 Ω ← Точки зупинки, представлені вершиною Z
47
9 q ← 3 вимірна матриця часу в дорозі між трійками точок
10 зупинки. (Значення за замовчуванням ∞)
11 для кожної χ в Ξ виконати
12 для кожної φ у Φ виконати
13 для кожної ω в Ω виконати
14 якщо ����
��,�� ≥ ��. ��і ����
��,�� ≥ ��. �� тоді
15 �� �� ��
��,��,�� = ∆��,��+∆��,��
16 φ * = argmin(��χ,φ,ω)
17 додайте рядок [X, Y, Z, φ *] до Υ m
18 повернення Y m
Після завершення перетворення списки точок зупинки можна реалізувати у
Visum, замінивши старі маршрути ліній за допомогою Visum COM-API (PTV AG
2014). Щоб дозволити виконувати призначення PuT для оцінки (див. Розділ
3.2.5), можна також створити часові профілі та маршрути транспортних засобів.
Процес побудови таблиці перетворення Ym описано в алгоритмі 2. Він
ґрунтується на даних, отриманих під час генерації Am (алгоритм 1), зокрема на
матриці зв’язності Cm і матриці відстані Δm. Для кожної вершини Y алгоритм
ідентифікує вершини K, суміжні з нею (рядок 3). Завдяки цьому можна визначити
трійки з’єднаних вершин {X, Y, Z} де (���� ��
��,�� = ����,�� = 1). Алгоритм перебирає
кожну можливу комбінацію трійки зупинок {X, Y, Z} (рядок 5) і витягує
відповідну трійку точок зупинки, визначену як {χ, φ, ω}, де χ є точкою зупинки
X, φ точка зупинки Y і ω точка зупинки Z (рядок 6). Якщо будь-яка із зупинок {X,
Y, Z} пов’язана з кількома точками зупинки, генерується кілька потрійних точок
зупинки. Зв’язок між точками зупинки для кожної витягнутої трійки точок
зупинки {χ, φ, ω} перевіряється за матрицею зв’язності точок зупинки Cm. Якщо
згідно з Cm ці точки зупинки з'єднані (���� ��
��,�� ≥ 0.5, ����,�� ≥ 0.5) (рядок 14), час у
дорозі розраховується та зберігається в тривимірній матриці часу в дорозі:
����,��,�� = ∆��
��,��+∆��
��,�� (рядок 15). Після розрахунку часу подорожі для кожної
48
можливої трійки зупинок {X, Y, Z} вибирається зупинка з мінімальним часом
подорожі ����∗,��∗,��∗ = min (����,��,��) (рядок 16), де φ* - точка зупинки, яка
представлятиме вершину Y ∈ {X, Y, Z} у таблиці перетворення.
49
РОЗДІЛ 3. ЕКСПЕРИМЕНТАЛЬНЕ ДОСЛІДЖЕННЯ ТРАНСПОРТНИХ
МЕРЕЖ ІЗ ЗАСТОСУВАННЯМ АЛГОРИТМІВ ГІПЕРЕВРИСТИКИ
3.1 Оптимізація транспортних мереж
3.1.1 Застосування алгоритму відбору гіперевристики
Гіперевристики з'явились для підвищення рівня загальності методів пошуку
складних обчислювальних задач. У той час як евристики працюють
безпосередньо в просторі рішення, гіперевристики працюють на вищому рівні,
контролюючи набір евристик низького рівня, які виконують прямі операції над
рішенням. Таким чином, гіперевристики не вимагають прямого знання базової
реалізації області вирішення, і це дозволяє просту адаптацію до різних
проблемних областей.
Гіперевристики класифіковані в Burke et al. (2019) відповідно до природи
евристичного простору пошуку на гіперевристики генерації та відбору. Перший
генерує нові евристики з існуючих компонентів інших евристик, тоді як другий
(тобто підхід, який ми тут використовуємо) вибирає існуючі евристики в
повному обсязі з існуючого набору евристик. Гіперевристика вибору працює як
два компоненти: компонент вибору та прийняття переміщення. У кожній точці
прийняття рішення метод вибору вибирає евристику або послідовність евристик
із існуючого сховища евристик низького рівня та застосовує їх до наявного
рішення, щоб створити нове рішення. Після цього етап оцінки вирішує, чи
прийняти нове рішення на основі критерію прийнятності. Два компоненти
повторюються, доки не буде виконано умову завершення.
Гіперевристика вибору може включати механізм ненавчання або механізм
навчання залежно від того, чи є зворотний зв’язок, отриманий під час пошуку.
Цей зворотній зв'язок допомагає покращити рішення щодо вибору, прийняті
компонентом вибору.
У цій роботі ми протестували два методи відбору: «простий випадковий»
(SR) вибір без навчання та «гіперевристичний вибір на основі послідовності»
(SSHH) з онлайн-зворотним зв’язком. Для обох ми використали критерій
50
прийнятності «покращити або дорівнювати» (IE), що означає, що нові рішення
приймаються, лише якщо вони дорівнюють або кращі за поточне рішення.
SR випадковим чином вибирає евристику на основі рівномірного розподілу
ймовірностей. Він вважається найпростішим методом відбору і може ефективно
використовуватися як еталон для більш складних методів відбору. SSHH нагадує
модель Hidden-Markov, де низькорівнева евристика представляє приховані стани
моделі, а перехід між цими різними станами формує послідовності евристик,
застосованих до рішення. Мета полягає в тому, щоб створити та вивчити хороші
послідовності евристик, які, ймовірно, покращать рішення. У Ahmed et al. (2019)
серія експериментів і порівнянь за допомогою статистичних методів довели, що
відбір на основі послідовності є більш успішним у вирішенні UTRP, ніж інші
механізми евристичного відбору на одній основі. Ми коротко підсумуємо цей
алгоритм тут і окреслимо його застосування для оптимізації мереж Visum PuT у
наступних розділах. Додаткову інформацію щодо цього алгоритму можна знайти
в Ahmed et al. (2019), Кейрі та Кідвелл (2015) та Кейрі та Кідвелл (2017).
Кожна евристика низького рівня пов’язана з кількома балами, які
використовуються для визначення ймовірності переходу від цієї евристики до
іншої евристики низького рівня в послідовності. Припустимо, що ми маємо набір
із n евристик низького рівня: [llh0, llh1,..., llhn], «матриця переходу» розміру n×n
зберігає ці оцінки. Інша матриця, яка називається «матрицею побудови
послідовності» розміром n×2, пов’язує кожну низькорівневу евристику з двома
станами: «продовжити» та «закінчити», щоб визначити, чи повинна
послідовність закінчуватися чи продовжуватися в цій точці. Обидві матриці
спочатку починаються з однаковими балами.
Послідовність евристик низького рівня будується за допомогою двох
матриць. Послідовність ініціалізується випадково вибраною евристикою.
Імовірність того, що евристика буде обрана наступною в послідовності, зростає
разом із її оцінкою в матриці переходу (тобто чим вище оцінка, тим вище шанс
вибору). Кожного разу, коли в послідовність входить нова евристика, статус
51
послідовності перевіряється в матриці побудови послідовності, щоб визначити,
чи слід припинити побудову послідовності або додати іншу евристику.
Значення в матрицях оновлюються, якщо нове рішення, створене шляхом
застосування певної послідовності, виявляється кращим за поточне рішення.
Оновлення балів у матрицях збільшує ймовірність вибору цієї успішної
послідовності на наступних етапах. Приклад цього оновлення показано на
рисунку 3.1 Протягом процесу оптимізації механізм оновлення допомагає
ідентифікувати успішні послідовності.
3.1.2 Оптимізація маршруту лінії PuT за допомогою гіперевристики вибору
На початку процесу оптимізації набір маршрутів ініціалізується з моделі
мережі Visum шляхом перетворення лінійних маршрутів Visum у списки зупинок
(вершини) для побудови початкового рішення. Початкове рішення (Sinit)
вводиться до гіперевристики як поточне рішення (Scurr), і починається
ітеративний процес оптимізації. Одна ітерація алгоритму SSHH проілюстрована
на рисунку 3.2. Залежно від механізму відбору вибирається або одна евристика у
випадку простого випадкового вибору (SR), або будується евристична
послідовність у разі вибору на основі послідовності (SSHH). Застосування цієї
евристичної/евристичної послідовності до Scurr створює нове рішення Snew, яке
перевіряється на його здійсненність (див. Розділ 3.1.4). Якщо Snew неможливий,
він відхиляється та вибирається нова евристична/евристична послідовність. В
іншому випадку Snew перетворюється на списки точок зупинки та реалізується в
моделі мережі Visum (див. Розділ 2.2.2) для оцінки (див. Розділ 3.1.5). Оцінка
автоматично враховує взаємодію між різними режимами PuT. При відповідній
конфігурації також можна враховувати вплив приватних видів транспорту.
За допомогою необхідної інформації, згенерованої у Visum, обчислюється
цільова функція f(Snew). Якщо f(Snew)<f(Scurr), Snew замінює Scurr і стає новою
основою для пошуку нових рішень. Крім того, у випадку SSHH відповідні
значення в матрицях переходів і побудови послідовності оновлюються.
52
Гіперевристика повторює генерацію нових рішень, вбудовуючи їх у Visum і
оцінюючи, доки не буде виконано заздалегідь визначену умову завершення.
(a) Початкові значення матриць (b) Оновлені значення матриць
Рисунок 3.1 Приклад оновлення значень у матрицях побудови переходу та
послідовності: Припускаємо застосування послідовності [llh0, llh1, llh3] покращив
найкраще рішення. Оцінки цих евристик низького рівня в «матриці переходів» і
«матриці побудови послідовності» оновлюються. Це оновлення збільшує
ймовірність вибору цієї послідовності на наступних кроках
Рисунок 3.2 Опис однієї ітерації застосування алгоритму SSHH у
глобальній оптимізації. Кожна ітерація починається з поля A: генерація
послідовності евристик (див. Розділ 3.1.1) і застосування її до поточного набору
маршрутів (див. Розділ 3.1.3) для створення нового набору маршрутів. Новий
53
набір маршрутів перевіряється на його здійсненність (див. Розділ 3.1.4). Якщо
новий набір маршрутів неможливий, він відхиляється та генерується нова
евристична послідовність. В іншому випадку новий набір маршрутів
перетворюється на списки точок зупинки (блок B, див. розділ 2.2.2). Списки
точок зупинки реалізовано у Visum як маршрути ліній, і виконується
призначення, щоб отримати інформацію, необхідну для оцінки (вставка C, див.
розділ 3.1.5). Оцінка включає поєднання цілей витрат на пасажирів і операторів
(вставка D, див. розділ 3.1.5.1). Якщо згідно з оцінкою новий набір маршрутів
покращує поточний найкращий набір маршрутів, він замінює останній, а матриці
побудови переходів і послідовності оновлюються (див. Розділ 3.1.1).
Оскільки матриця суміжності та таблиця перетворення мають залежати від
режиму, рішення можуть включати лише маршрути для одного режиму PuT.
Якщо потрібно оптимізувати кілька режимів, рішення для різних мереж
маршрутів повинні розроблятися незалежно. Теоретично це може відбуватися
або по черзі, змінюючи режим, який потрібно оптимізувати на кожному кроці,
або послідовно в ієрархічному процесі. Однак така ініціатива виходить за рамки
цієї статті.
3.1.3 Алгоритм евристики низького рівня
Гіперевристичний алгоритм керує набором низькорівневих евристик для
зміни заданого набору маршрутів. Усі низькорівневі евристики були розроблені
для дотримання відносин суміжності, визначених матрицею суміжності A під час
виконання операцій. Якщо застосування операції до вибраних маршрутів і
позицій призведе до створення недійсних з’єднань, натомість вибираються нові
маршрути та позиції. Це збільшує ймовірність створення здійсненних рішень.
Ми надаємо тут повний список низькорівневих евристик, застосованих у цій
роботі (також показано на рисунку 3.3):
- llh0 (Додати): Вибирає випадковий маршрут і випадкову позицію на цьому
маршруті. У цій позиції вибирається та додається нова вершина.
54
- llh1 (Видалити): Вибирає випадковий маршрут і випадкову позицію та видаляє
вершину в цій позиції.
- llh2 (Поміняти внутрішній маршрут): вибір випадкового маршруту та двох
випадкових позицій. Дві вершини в цих положеннях міняються місцями.
- llh3 (Вставити всередині маршруту): вибір випадкового маршруту та двох
випадкових позицій. Вершина в першій позиції вставляється в другу позицію.
- llh4 (перемикання між маршрутами): вибір двох випадкових маршрутів і двох
випадкових позицій на кожному з них. Вершини в цих положеннях міняються
місцями одна з одною.
- llh5 (Вставити між маршрутами): вибір двох випадкових маршрутів і двох
випадкових позицій на кожному з них. Вершина в першій позиції першого
маршруту вставляється у другу позицію другого маршруту.
- llh6 (Замінити): Вибирає випадковий маршрут і випадкову позицію. Вершина
в цій позиції замінюється іншою обраною вершиною.
- llh7 (Обмін): Вибирає два випадкових маршрути та розділяє їх у спільній
вершині. Частини двох маршрутів обмінюються для створення двох нових
маршрутів. Якщо вибрані маршрути не мають спільної вершини, вибирається
нова пара маршрутів.
- llh8 (Продовжити маршрут): Вибирає випадковий маршрут і додає вершини до
кінця маршруту, доки не досягне іншого терміналу.
- llh9 (Зменшити маршрут): Вибирає випадковий маршрут і видаляє вершини,
починаючи з останньої вершини маршруту до досягнення іншого кінцевого
вузла.
3.1.4 Здійсненність рішення транспортної задачі
Перед впровадженням Snew у мережеву модель Visum застосовується тест на
здійсненність, щоб переконатися, що набір маршрутів задовольняє всі визначені
обмеження, щоб уникнути марнування часу на створення та оцінку багатьох
нездійсненних рішень. Техніко-економічні обмеження визначаються щодо
специфікацій у моделі мережі Visum, наприклад, зворотні треки та цикли
55
допускаються в налаштуваннях мережі Visum, тоді як у більшості моделей UTRP
це зазвичай вважається порушенням. Повний список обмежень виглядає так:
- Порядок вершин на кожному маршруті повинен відповідати відношенню
суміжності, визначеному матрицею A.
(а) Додати (b) Вилучити
(c) Поміняти внутрішній маршрут (d) Вставити внутрішній маршрут
(e) Перемикання між маршрутами (f) Вставити між маршрутами
(g) Замінити (h) Маршрути обміну
(i) Розширення маршруту (j) Скоротити маршрут
Рисунок 3.3 Опис низькорівневого набору евристик. Прямі дуги – це ребра
в маршруті або додані після застосування евристики, пунктирні дуги – це ребра,
видалені після застосування евристики, червоні вузли – вузли, додані після
застосування евристики
- Маршрути повинні починатися і закінчуватися в визначених кінцевих
вершинах.
- Кільцеві маршрути дозволені, але вони повинні починатися і закінчуватися в
одній вершині.
56
- Довжина кожного маршруту знаходиться в заданих межах, визначених як
вхідні параметри користувачем.
- Маршрути не повинні повністю збігатися (це включає в себе один маршрут,
який є частиною іншого).
- Кожна зона повинна бути підключена до набору маршрутів: кожна зона в
моделі мережі Visum повинна мати принаймні один з’єднувач, який підключено
до активної точки зупинки (тобто точки зупинки, яка використовується
принаймні однією лінією PuT).
3.1.5 Оцінка отриманого набору маршрутів
Залежно від цілей дослідження та наявних даних існують різні способи
оцінки набору маршрутів. Пакети програмного забезпечення для моделювання
транспорту, такі як Visum, мають безліч опцій для аналізу впливу змін у
транспортній мережі, які можна використовувати для створення широкого
спектру функцій оцінювання. Найбільш помітними серед інструментів Visum
для моделювання впливу змін у транспортній моделі є процедури призначення,
які використовуються для розрахунку потоку транспортних засобів
(призначення PrT) або пасажирів PuT (призначення PuT) через модель мережі.
Вони надають такі вихідні дані, як матриці часу подорожі від зони до зони
(використовується в розділі 5.5.1) або навантаження транспортних засобів на
відрізках (використовується в розділі 5.5.2).
Процедури призначення, як правило, починаються з визначення всіх
можливих шляхів через мережеву модель між усіма парами зон та їхнім
імпедансом. Для призначень PrT необхідно вибрати певний режим PrT
(наприклад, приватні автомобілі), а обчислені можливі шляхи обмежуються
відрізками, які відкриті для цього режиму. Призначення PuT визначають
доступні шляхи в мережі для всіх ліній PuT. Можливі пересадки між різними
режимами PuT (наприклад, між автобусом і поїздом) враховуються автоматично.
Імпеданс шляху включає всі витрати часу, пов'язані з мандрівником. Для PrT
імпеданс визначається такими факторами, як дозволена швидкість на з’єднаннях,
57
штрафи за повороти та втрати часу через ефекти перевантаження. Інші витрати,
такі як грошові витрати, також можна визначити. Однак вони не відіграють ролі
в цьому дослідженні. Для PuT основним фактором імпедансу шляху є очікуваний
час у дорозі, який визначається як зважена сума кількох факторів, таких як:
- Час доступу від початкової зони до початкової зупинки (зазвичай у режимі
«пішохідний»).
- Час очікування на місці відправлення.
- Загальний час у дорозі в автомобілі.
- Штраф за кількість передач.
- Час ходьби між зупинками на пересадках.
- Час очікування на трансферах.
- Час доступу від пункту зупинки до зони призначення (зазвичай у режимі
«пішохідний»).
Інші фактори, такі як час посадки, також можна додати, але це не відіграє
ролі в цьому дослідженні. Вагові коефіцієнти різних факторів можна встановити
вільно. У цьому дослідженні ми використовували конфігурації Visum за
замовчуванням, де всі фактори часу зважені однаково, а штраф за передачу
встановлено на 10 хвилин за передачу.
Особливо важливим є час очікування пересадки, який є фактором, що
розрізняє дві відмінні моделі призначення PuT, що використовуються в цій
роботі: призначення на основі прогресу та призначення на основі розкладу. У той
час як перший передбачає фіксований час очікування між транспортними
засобами на всіх маршрутах, другий виводить час очікування з конкретного
розкладу. Після визначення всіх шляхів призначення розподіляє відключення,
наведені в матриці попиту, на доступні шляхи на основі їх імпедансу.
Використовувані моделі розподілу є однією з головних відмінностей між
доступними процедурами призначення. Детальніше про ці процедури та моделі
їх розповсюдження пояснюється в посібнику Visum (PTV AG 2018). Отриманий
розподіл поїздок дозволяє нам оцінити, наприклад, кількість транспортних
58
засобів, які використовують певний зв’язок (тобто навантаження на канал).
Доступ до результатів завдань можна отримати кількома різними способами
для створення функцій оцінювання. Далі ми представляємо два методи оцінки:
глобальна оптимізація та локальна оптимізація. Перший використовує матрицю
часу в дорозі, створену на основі сприйнятого часу в дорозі. Останній отримує
доступ до навантажень транспортних засобів за вибраними відрізками.
3.1.5.1 Метод глобальної оптимізації
Глобальна оптимізація — це метод, який використовується переважною
більшістю досліджень UTRP: цільова функція, яка збирає інформацію з усієї
системи. Ми вирішили використовувати суму двох відносно простих
компонентів для нашої цільової функції.
Перша мета полягає в тому, щоб зменшити вартість пасажирів (тобто
середній очікуваний час подорожі пасажирів). Він заданий наступним
рівнянням:
(1)
де Di,j – попит на проїзд PuT із зони i до зони j, і |Z| – загальна кількість зон. Θi,j –
це найкоротший очікуваний час подорожі від зони i до зони j з використанням
мережі PuT, визначеної рішенням S. Матриця Θ можуть бути згенеровані під час
виконання призначення PuT.
Друга мета – це зниження витрат оператора. Ми використали просте
наближення для витрат операторів, визначених загальною сумою часу в дорозі
для подорожей усіма маршрутами ліній у мережі PuT:
(2)
де τi - загальний час у дорозі маршруту i та |lr| – загальна кількість маршрутів
ліній. Значення τi можна легко отримати з моделі мережі за допомогою Visum
COM-API.
59
Дві цілі об’єднані в єдину цільову функцію у формі зваженої нормалізованої
суми, заданої такою формулою:
(3)
де S0 є початковим рішенням. Два вагові коефіцієнти a і β можуть бути
скориговані по відношенню один до одного, щоб створити рішення, які є більш
сприятливими для операторів або пасажирів.
5.5.2 Метод локальної оптимізації
Для локальної оптимізації ми використовуємо дві функції Visum. Перший
полягає в тому, що результати призначення можуть бути легко доступні на дуже
локалізованому рівні, наприклад, навантаження транспортного засобу певного
виду транспорту на окремій лінії зв'язку. По-друге, це можливість комбінувати
призначення PuT і PrT із процедурою вибору режиму. Процедура вибору режиму
приймає як вхід матрицю попиту з усіма відключеннями та розподіляє їх на
відключення PuT і відключення PrT. Розподіл заснований на імпедансі можливих
шляхів у відповідних режимах (PTV AG 2018). Для експерименту в розд. 6.3 була
використана вкладена функція розподілу логітів. Однак у Visum доступні інші
функції розподілу, зокрема гравітаційна модель. Детальніше про них можна
знайти в посібнику Visum (PTV AG 2018). Результати поділяються на матриці
попиту PuT і PrT, які потім використовуються відповідними процедурами
призначення для призначення поїздок маршрутам подорожей. Ця комбінована
послідовність процедур дозволяє аналізувати вплив змін в інфраструктурі на
різні види транспорту.
Для локальної цільової функції ми вибираємо групу зв’язків L (наприклад,
зв’язки в певному районі), запускаємо згадану вище комбіновану послідовність
процедур і підсумовуємо навантаження приватних автомобілів (тобто режим
PrT) на ці зв’язки. Мета полягає в тому, щоб мінімізувати навантаження
приватних автомобілів на вибрані відрізки, задані:
60
(4)
vi(S) – навантаження приватних автомобілів на ланку i ∈ L, тоді як мандрівники
в мережі можуть вибирати між поїздками через мережу громадського
транспорту, визначену рішенням S, або приватними автомобілями. Завантаження
відрізку є стандартним виходом для більшості призначень PrT, доступних у
Visum 17 (PTV AG 2018).
Однак оптимізація однієї мети може призвести до дуже екстремальних
рішень, які є небажаними з інших точок зору. Для прикладу дивіться результати
з точки зору пасажирів, представлені в розділі. 6.1, де витрати оператора
збільшуються у 8 разів. Щоб уникнути цього, ми використали глобальні цілі,
представлені в попередньому розділі, як обмежувальні фактори:
(5)
де S 0 – початковий розв’язок, а λ Ρ і λ 0 є факторами для визначення того,
наскільки збільшення глобальних цілей рішення S порівняно з їх початковими
значеннями вважається прийнятним для розгляду рішення S.
Ми вибрали відносно простий захід, щоб показати достовірність концепції
локальної оптимізації. Однак цю концепцію легко узагальнити та застосувати до
інших сценаріїв. Наприклад, можна оцінити рівень шуму та забруднення повітря
за допомогою модуля розширення HBEFA у Visum і отримати доступ до
результатів на рівні зв’язку, подібно до навантаження PrT. На жаль, такий
сценарій не можна було включити в це дослідження, оскільки модуль HBEFA не
був включений у нашу академічну ліцензію. Це розширить наші методи розробки
мереж PuT, які покращать ситуацію в сильно забруднених районах.
61
3.2 Результати емпіричних досліджень
3.2.1 Тестування на малій моделі
3.2.1.1 Налаштування тестової моделі
Для першого набору експериментів ми використали транспортну модель із
швидкого посібника Visum. Цю мережеву модель було створено в 2006 році як
навчальну програму Visum, і приблизно вона базується на невеликому містечку
Пфулінген, Німеччина, з приблизно 18 тисячами жителів. Модель мережі є
відносно невеликою, містить 652 вузли та 1782 зв’язки, 81 зону, 35 зупинок та
пунктів зупинки та лише п’ять автобусних ліній. Ми трохи змінили цю мережеву
модель, щоб мати можливість тестувати різні аспекти процедури інтерфейсу.
Наприклад, було необхідно створити одну зупинку з більш ніж однією точкою
зупинки, щоб перевірити використання таблиці перетворення (див. Розділ 4.2).
Детальний опис цих змін можна знайти в Додатку A.1.
Оптимізація в цих експериментах базується на методі глобального
оцінювання (розділ 5.5.1). Щоб обчислити матрицю сприйнятого часу в дорозі
Θ, ми використали процедуру призначення PuT на основі пробігу. Для всіх ліній
визначено фіксовану частоту 10 хв. Ця модель призначення не вимагає генерації
поїздок транспортного засобу для кожного зміненого маршруту лінії, що
покращує час роботи.
Умова завершення цих експериментів визначається кількістю успішних
ітерацій. Успішна ітерація полягає у створенні нового можливого рішення, його
реалізації у Visum та його оцінці. Кількість успішних ітерацій до завершення
гіперевристики встановлено на 20 000.
3.2.1.2 Результати випробувань малої тестової моделі
У першій серії експериментів ми протестували два методи вибору SR і
SSHH у трьох різних сценаріях: перспектива пасажира, перспектива оператора
та збалансована перспектива. Кожен із цих сценаріїв визначається іншим
набором параметрів у рівнянні. 3: з точки зору оператора фактично
62
враховувалися лише витрати оператора, коли ми встановили α=10-6 і β=1–10-6.
Протилежність у перспективі пасажира, де фокус встановлюється на вартість
пасажира шляхом встановлення α=1–10-6 і β=10-6. У збалансованій перспективі
ми створюємо баланс між двома цілями, встановлюючи для обох параметрів
значення α=β=0,5.
На рисунку 3.4 показано зміну середньої вартості пасажира Cp (зелена лінія
з прямокутниками. Положення маркерів (прямокутник, п’ятикутник і коло) не
мають жодного значення, окрім розрізнення ліній), середніх витрат оператора CO
(синя лінія з п’ятикутники (див. Виноску 12)), а комбінована мета fglobal (чорна
лінія з колами (див. Виноску 12)), обчислена за рівнянням. 3. Для кожного з трьох
сценаріїв витрати пасажирів і операторів були нормалізовані з використанням їх
початкових значень для кращої інтерпретації їх ефективності. Середні значення
обчислюються з десяти прогонів для кожної успішної ітерації.
З цих цифр видно, що як з точки зору пасажира, так і з точки зору оператора,
мета, на якій зосереджується оптимізація, швидко зменшується від початкового
значення, тоді як інша ціль зростає. Це покращення починає сповільнюватися на
етапі 2000 ітерацій.
У випадку збалансування двох цілей витрати як на пасажира, так і на
оператора демонструють однакову поведінку, швидко знижуючись на початку
пошуку та сповільнюючись після 2000 ітерацій. У цьому випадку метод відбору
SSHH був більш успішним у покращенні витрат оператора, тоді як обидва
методи відбору зменшили витрати на пасажира з однаковою швидкістю.
Таблиця 1 підсумовує нормовані та усереднені результати витрат на
пасажирів і операторів для десяти рейсів. Також записуються найкращі
результати та стандартне відхилення. З цієї таблиці найпомітніше покращення в
перспективі пасажирів зі зниженням вартості пасажирів на 20% від початкових
значень, хоча це відбулося за рахунок значного збільшення витрат оператора.
Перспективні рейси оператора знизили витрати оператора в середньому майже
на 7%, а збалансовані рейси зафіксували покращення вартості оператора майже
63
на 5%, а вартість пасажирів також покращилася на 3%.
Як видно з таблиці, різниця в продуктивності між двома гіперевристичними
методами вибору дуже мала, але під час експериментів було зроблено два
спостереження: метод вибору SSHH зміг покращити більше за меншу кількість
ітерацій порівняно з простим вибором, і цей факт має вирішальне значення для
роботи з великими мережами. По-друге, SSHH зафіксував кращі індивідуальні
результати для прогонів у багатьох випадках, особливо з точки зору оператора.
На основі цих фактів ми вибрали SSHH для застосування в наступній серії
експериментів на більшій моделі мережі та для перевірки концепції локальної
оптимізації.
3.2.2 Застосування моделі у мережі розміром міста
3.2.2.1 Налаштування моделі міста
Для того, щоб продемонструвати валідність представлених методів у
більшому масштабі, було проведено інший набір експериментів на моделі
мережі, що походить від процесу планування в реальному світі. Він був
створений у 1990-х роках для міста Галле, Німеччина, з населенням понад 200
тисяч жителів. Модель складається з 1934 вузлів, 4832 ланок, 81 зони, 288
зупинок і 313 точок зупинки, а також загалом 41 лінії PuT, з яких 18 є
автобусними. З 1996 року ця модель лягла в основу багатьох прикладів навчання
Visum, і тому наразі вона включена в усі інсталяції Visum. Незважаючи на те, що
ця модель була змінена з часом, її розмір і компонування достатні для
представлення моделі реальної мережі. Для цілей цієї роботи ми зробили лише
дуже невеликі зміни, які можна знайти в Додатку A.2.
64
(а) Точка зору пасажира SR (б) Точка зору пасажирів SSHH
(в) Точка зору оператора SR (г) Точка зору оператора SSHH
(д) Збалансована перспектива SR (е) Збалансована перспектива SSHH
Рисунок 3.4 Результати глобальної оптимізації на моделі невеликої мережі
для трьох сценаріїв: точки зору пасажирів, перспективи оператора та
збалансування двох цілей за допомогою двох гіперевристик вибору (SR і SSHH).
Кожна фігура відображає розвиток нормалізованої цілі пасажира Cp, усередненої
за десять прогонів (зелений з прямокутниками), нормалізованої усередненої цілі
оператора CO (синій з п’ятикутниками) та усередненої комбінованої функції
оптимізації fglobal (чорний з колами). Середні значення були розраховані для
кожної успішної ітерації з десяти незалежних прогонів. Смужки посередині
представляють стандартне відхилення між циклами. Примітка. Положення
65
маркерів (прямокутник, п'ятикутник і коло) не мають жодного значення, крім
розрізнення ліній
Таблиця 3.1. Результати збалансованих конфігурацій пасажира, оператора
та двох гіперевристик вибору
SR-IE SSHH-IE
Сценарій Об’єкт
Avg Std Min Avg Std Min
Пасажир Cp 0.81 0.005 0.80 0.81 0.006 0.80
CO 6.96 1.07 5.12 7.49 1.55 6.46
Оператор Cp 1.03 0.004 1.02 1.03 0.004 1.02
CO 0.96 0.014 0.93 0.96 0.014 0.93
Збалансований Cp 0.98 0.003 0.97 0.96 0.008 0.96
CO 0.98 0.014 0.96 0.96 0.008 0.96
Результати нормалізуються та усереднюються за десятьма сеансами.
Стандартне відхилення та найкращі результати також записуються
Модель мережі Halle включає кілька видів громадського транспорту:
автобус, трамвай і потяг. Оптимізація застосована лише до автобусних ліній,
залишаючи лінії інших видів транспорту без змін. Періодичність руху автобусів
встановлена 10 хв. У цих експериментах ми використовували призначення PuT
на основі розкладу, яке базує час очікування на пересадці на розкладі,
створеному на основі часу відправлення та руху. Таким чином, частоти
незмінних ліній PuT точно відображаються. Однак використання призначення на
основі розкладу вимагає додавання поїздок транспортних засобів до змінених
автобусних ліній, щоб визначити розклад автобусів.
Умовою завершення для цих експериментів є час виконання, а не ітерації,
де кожен експеримент виконується протягом 16 годин перед його завершенням.
Це було зроблено з практичних причин і призвело до в середньому 8919
успішних ітерацій (тобто в середньому 6,6 с на успішну ітерацію) для кожного
запуску. Для цих експериментів ми використовували настільний ПК із
двоядерним процесором Intel i3-4150 3,50 ГГц і 16 ГБ оперативної пам’яті.
66
3.2.2.2 Результати випробувань моделі міста
Десять запусків було застосовано до цієї транспортної мережі з
використанням вибору на основі послідовності зі збалансованою конфігурацією.
Ця конфігурація була обрана як приклад процесу планування, який вимагає
компромісу між пасажирами та операторами. Рисунок 3.5 показує розвиток
середнього значення вартості пасажира CP (зелений з прямокутниками (див.
Виноску 12)), витрат оператора CO [синій з п’ятикутниками (див. Виноску 12)], а
також ціль, розраховану комбінованою оптимізацією глобальна функція f
(Рівняння 3) [чорний з колами (див. Виноску 12)] з часом. Смужки помилок
показують стандартне відхилення між різними прогонами.
Для цієї мережі можна помітити, що на ранніх етапах пошуку ціль щодо
пасажирів неухильно знижується, тоді як дуже ранні рішення показують
збільшення вартості оператора. Однак протягом часу пошуку вартість оператора
падає нижче своїх початкових значень, але коливається навколо значення 0,95,
на відміну від вартості пасажира, яка продовжує падати до часу завершення
пошуку для більшості рейсів. Через 16 годин вартість пасажира досягає в
середньому значення 0,877.
Права бічна панель на рисунку 3.6 відображає кінцеві значення CP
(прямокутники), CO (п’ятикутники) і комбіновану ціль fglobal (кола) для кожного з
десяти циклів. Цільові значення, що належать одному циклу, отримують
однакові кольори маркерів. Ці значення також наведено в таблиці 2. Ми бачимо,
що в той час як для операторських витрат CO зниження становить від 3,1 до 6,4%,
для пасажирських витрат CP досягнуто більшого зниження від 10,6 до 13,8%.
67
Рисунок 3.6 Результати глобальної оптимізації лінії PuT за допомогою
SSHH у мережі розміром у місто. Відображено розробку нормалізованої цілі
середнього пасажира CP (зелений з прямокутниками), цілі оператора CO (синій з
п’ятикутниками) та комбінованої функції оптимізації fglobal (чорний з колами).
Середні значення були розраховані з кроком в одну хвилину з десяти незалежних
прогонів. Стовпчики показують стандартне відхилення між циклами. Маркери
на правій бічній панелі показують розподіл кінцевих значень окремих циклів
після 16 годин циклу (також показано в таблиці 2). Кожен маркер представляє
кінцеве значення fglobal (кола), CP (прямокутники) або CO (п’ятикутники) для
кожного циклу. Кожен колір унікально ідентифікує один із десяти
експериментів. Примітка. Положення маркерів (прямокутник, п'ятикутник і
коло) не мають жодного значення, крім розрізнення ліній
Таблиця 3.2 Кінцеві значення десяти прогонів із глобальною оптимізацією
SSHH
1 2 3 4 5 6 7 8 9 10 Середнє
fglobal 0,912 0,917 0,914 0,911 0,919 0,914 0,909 0,908 0,921 0,920 0,915
CP 0,882 0,875 0,868 0,874 0,868 0,882 0,882 0,862 0,894 0,884 0,877
CO 0,942 0,959 0,961 0,949 0,969 0,945 0,936 0,955 0,948 0,956 0,952
68
Значення, нормалізовані на початкові значення, і мінімальні значення
виділені жирним шрифтом
Цікаво, що два цикли з найвищим зниженням CO та CP, відповідно, також є
двома найкращими прогонами з точки зору комбінованого зменшення обох
цілей. Серія, що зменшує CO на 6,4 %, знижує CP на 11,8 %, а серія, яка знижує
C P на 13,8 %, також знижує CO на 4,5 %. Це показує, що вдосконалення обох
цілей не є взаємовиключними.
3.2.3 Застосування моделі локальної оптимізації
3.2.3.1 Налаштування локальної моделі
Для тестування локальної оптимізації ми використали транспортну модель
прикладу Visum 17 «Demand NestedLogit», яка постачається з реалізованою
процедурою вибору режиму для вибору режиму між режимами PrT і PuT.
Модель мережі ідентична тій, що використовується в Розд. 3.2.2 і було піддано
тим самим модифікаціям.
Попередньо визначені процедури призначення розділені на окремі
призначення для ранкового та вечірнього пікового трафіку за допомогою різних
матриць попиту. Однак у нашому дослідженні використовується лише результат
ранкового піку (з незмінними налаштуваннями), щоб застосування нашої
методології було максимально простим. Застосовуваною процедурою
призначення для PuT є призначення на основі розкладу, а поїздки транспортних
засобів було встановлено для початку з інтервалом 10 хвилин.
Як зазначено в розд. 3.1.5.2, метою локальної оптимізації є зменшення
навантаження приватних автомобілів на вибрану кількість ланок. Для цього ми
вибрали відрізки з ID-номерами 178, 186 та 4048, які представляють вулицю
Вормлітцер. StraBe в місті Галле. Ця вулиця є важливим сполучним пунктом
приблизно в 1 км на південь від головного центру міста. Як обмежувальні
коефіцієнти ми вибрали λΡ=1,05 і λ0=1,01. Значення λP і λO вибирали довільно.
Вони являють собою максимально дозволене збільшення витрат оператора на 1%
69
і збільшення очікуваного часу в дорозі на 5%. Ми знову використали час роботи
16 годин. Однак через більш складну послідовність процедур, необхідних для
оцінки, середня тривалість успішної ітерації під час експериментів становила
83,8 с, що призвело до середньої кількості успішних ітерацій 765.
3.2.3.2 Результати випробувань моделі локальної оптимізації
Було проведено десять незалежних прогонів, і результати відображені на
рисунку 3.7. Лінії даних показують зміну в часі середнього глобального
пасажирського об’єкта CP (зелений з прямокутниками) та об’єкта оператора CO
(синій з п’ятикутниками), відповідно. Чорна лінія з колами показує середнє
локальне цільове CL. Стовпчики показують стандартне відхилення між різними
циклами.
Рисунок 3.7. Результати локальної оптимізації лінії PuT за допомогою SSHH
для зменшення кількості приватних автомобілів, які користуються певною
вулицею в моделі розміру міста. Елементи цієї фігури подібні до опису рисунка
3.6. Тут чорна лінія з колами показує середнє зниження локальної цілі CL.
Праворуч кругові маркери показують кінцеві значення CL для окремих циклів
70
(також показано в таблиці 3)
Таблиця 3.3 Кінцеві значення десяти прогонів з локальною оптимізацією за
допомогою SSHH
1 2 3 4 5 6 7 8 9 10 Середнє
CL 0,292 0,426 0,315 0,528 0,461 0,573 0,596 0,539 0,697 0,596 0,502
CP 0,998 0,860 0,936 0,847 1,049 0,836 0,837 0,848 0,839 0,833 0,888
CO 1,001 1,00 1,005 1,005 1,006 1,008 1.01 1,009 1,009 1,008 1,006
Значення нормалізуються щодо початкових значень, а найкращі результати
виділено жирним шрифтом
З рисунка видно, що головна мета цих експериментів, яка полягає в
зниженні навантаження приватних автомобілів на вибраних ланках, була
успішно досягнута із середнім зниженням CL до 50,7% від початкового значення.
Ми також спостерігаємо широке розповсюдження рішень, оскільки стандартне
відхилення між результатами починає збільшуватися з часом пошуку. Для
найменш вдалого прогону CL було зменшено на 30,3%, тоді як для
найуспішнішого навантаження автомобілів на вибрані ланки зменшено на 70,8%,
більше ніж на дві третини початкового значення (див. рисунок 3.8).
71
Рисунок 3.8 Частини моделі мережі Галле до (ліворуч) і після (праворуч)
найуспішнішого запуску експериментів локальної оптимізації. Відрізки
відображаються чорним кольором, а навантаження на відрізки відображаються
помаранчевими смужками (навантаження PrT щодо кількості транспортних
засобів) і зеленими смугами (навантаження PuT щодо кількості пасажирів)
уздовж відрізків. Товщина брусків вказує на відносний об'єм навантаження.
Пунктирним синім колом позначені відрізки, вибрані для оптимізації
Крім того, ми бачимо, що середнє значення CP падає на початку пошуку,
навіть більше, ніж це відбулося в глобальній оптимізації в деяких випадках. Це
свідчить про те, що початкові скорочення CL є результатом зменшення
середнього часу в дорозі загалом для всіх пасажирів і, у свою чергу, підвищення
привабливості громадського транспорту, спричиняючи скорочення
використання приватних автомобілів. Подальше зменшення CL відбувається за
рахунок збільшення CP, ймовірно, шляхом створення мережі, яка спеціально
надає перевагу пасажирам, які в іншому випадку використовували б приватні
автомобілі на маршрутах через вибрані зв’язки. Через 16 годин CP в середньому
72
все ще на 13% нижче початкового значення. Однак існують суттєві відмінності
в кінцевих значеннях CP між сеансами. Серії з найбільш істотним зниженням CL
показують найвищі кінцеві значення CP. Це вказує на те, що деякі запуски
розробили вузькоспеціалізовані мережі, які для цього конкретного завдання
випереджають інші мережі з більш глобальними вдосконаленнями. Значення CO
дуже подібні в усіх прогонах без будь-яких істотних змін. Усі цикли
закінчуються збільшенням CO між мінімумом 0,003% і максимумом 0,96%.
3.3 Модифікації тестових мереж
3.3.1 Модифікації малої мережі
Модель мережі Visum, використана для експериментів у Розд. 6.1 — це
модифікована версія файлу версії Visum «430_VisumTutorial.ver», який
використовується на останньому етапі короткого підручника Visum17 (PTV AG
2017b). Ця мережева модель, хоч і базується на невеликому містечку Пфуллінген,
Німеччина, була створена як суто навчальна вправа. Ми модифікували його, щоб
мати можливість тестувати різні аспекти наших процедур інтерфейсу.
У початковій версії всі зупинки мають рівно одну зупинкову зону з одним
місцем зупинки, а вулиць з одностороннім рухом для автобусів немає. Щоб
правильно перевірити, чи таблиця перетворення (див. розділ 4.2) працює
правильно, нам потрібно було створити ситуацію, коли одна зупинка має дві
точки зупинки, доступні з протилежних напрямків. Щоб досягти цього, ми
заблокували відрізки, що представляють вулицю «FriedrichstraBe» у центрі міста
(номер відрізків: 53167233, 53167376, 53167410, 53167440, 53167475, 53167523,
540910046 та 563879509) для проїзду автобусів у південному напрямку.
напрямок і відрізки, що представляють її паралельна вулиця “SeitenstraBe”
(номер зв’язку: 53167201, 53167240, 53167275, 53167371, 53167383, 53167421,
53167524 та 78579745) для автобусного руху в північному напрямку. Крім того,
ми видалили зупинку з ідентифікатором 106062573 на « FriedrichstraBe » та
підключили її зону зупинки та зупинку до зупинки з ідентифікатором 106071832
73
на «SeitenstraBe». Час пересадки між двома точками зупинки було встановлено
2,5 хв. Єдиними існуючими маршрутами, на які вплинули ці зміни, були
маршрути «Автобус 5». Їх відповідно перенаправили.
Крім того, ми додали кілька конекторів до мережі. У оригінальній мережі
з’єднувачі розміщено таким чином, що всі зони зупинки необхідні для
підключення всіх зон до мережі PuT. Оскільки всі зони зупинки мають лише одну
точку зупинки, усі ці зупинки потрібні мережі ліній PuT, щоб усі зони були
підключені до мережі PuT. Щоб перевірити, чи оптимізатор знаходить кращі
рішення, якщо він здатний пропустити деякі точки зупинки, ми додали додаткові
з’єднувачі для транспортної системи «PUTW» (перехід до PuT) між наступними
парами вузлів зони:
- Зона 16 і вузол 106062573,
- Зона 17 і вузол 106062529,
- Зона 24 і вузол 106062529,
- Зона 32 і вузол 106062573,
- Зона 33 і вузол 106063464,
- Зона 37 і вузол 106063464,
- Зона 52 і вузол 106062293,
- Зона 62 і вузол 106061623.
3.3.2 Модифікації мережі міста
Транспортна модель, яку ми використовували для експериментів у розділах.
3.3.2 і 3.3.3 ґрунтуються на двох навчальних прикладах Visum 17
(«3D_Visualization.ver» і « NestedDM_absolu - teResult.ver », відповідно (PTV AG
2017a). Обидва використовують однакову мережеву модель і відрізняються лише
даними попиту, які вони використовують, і попередньо визначені процедури
моделювання.
Модель мережі базується на місті Галле, Німеччина, з населенням понад 200
тисяч жителів. Оскільки наша мета полягає в тому, щоб експерименти були
74
якомога ближче до реального прикладу, ми внесли лише мінімальні зміни в цю
мережу: ми додали транспортну систему «Walk» (пішохідна прогулянка до PuT)
до з’єднувачів між зоною та підключеним вузлом. до зони зупинки. Це дозволяє
використовувати відповідні 23 роз’єми в призначеннях PuT на додаток до
призначень PrT. Крім того, ми видалили автобусну лінію «B33», оскільки вона
повністю перетинається з автобусною лінією «B38». Нарешті, ми змінили рейси
всіх автобусів на відправлення з 10-хвилинним інтервалом. Поїздки
транспортних засобів інших режимів PuT залишили без змін.
75
Висновки
У цій роботі ми порівняли структуру даних, яку використовують багато
дослідників для задачі оптимізації міського транспортного маршруту (UTRP), і
професійне програмне забезпечення для моделювання транспорту PTV Visum.
Тому ми розробили інтерфейс для перекладу мережевих структур та іншої
важливої інформації між двома моделями. Ця процедура інтерфейсу потім
використовується для оптимізації ліній громадського транспорту Visum за
допомогою гіперевристики вибору.
Оптимізацію було застосовано за допомогою двох різних режимів
оптимізації: глобальної оптимізації, яка спрямована на мінімізацію загальних
витрат оператора та середнього часу подорожі пасажира, і локальної оптимізації,
яка спрямована на зменшення навантаження користувачів приватних
автомобілів на вибраних вулицях. Результати глобальної оптимізації показали
дієвість гіперевристик у невеликій мережі, а також у мережі розміром із місто. В
обох випадках одночасно досягаються високі темпи зниження витрат пасажирів
і операторів. Крім того, локальна оптимізація була перевірена на міській мережі,
зменшивши кількість користувачів приватних автомобілів на цільових вулицях
до 70%.
Ця робота показує нові можливості, що відкриваються для планувальників.
Використання алгоритмів оптимізації дозволяє проектувати майже оптимальні
мережі PuT, які не можна було б виявити більш традиційними методами
планування. Описаний інтерфейс дозволяє просто застосовувати такі алгоритми
з існуючими мережевими моделями та отримувати доступ до результатів у
звичному форматі. Для академічних дослідників ця робота показує переваги
використання професійного програмного забезпечення для моделювання
транспорту, такого як PTV Visum, у дослідженнях UTRP, оскільки це забезпечує
легкий доступ до величезного набору потужних інструментів оцінювання. Крім
того, процедури інтерфейсу, описані в цій роботі, можна легко використовувати
для запуску інших алгоритмів UTRP з використанням подібної структури даних.
76
Слід зазначити, що більшість алгоритмів UTRP не використовують структуру
попиту на основі зони, що перешкоджає їх застосуванню в налаштуваннях на
основі зон, таких як ті, що використовуються тут. Проте нещодавно в Heyken
Soares (2020b) було запропоновано метод подолання таких проблем. Варіації
функцій оцінки, які використовуються в цій роботі, можна легко реалізувати
відповідно до конкретних сценаріїв планування або дослідження.
Для майбутньої роботи можливості оптимізації можна розширити, щоб
включити інші етапи оптимізації транзитної мережі (див. Примітку 1), особливо
встановлення частоти маршрутів. Варто було б вивчити та вдосконалити процес
оптимізації маршрутів кількох видів транспорту. Крім того, є деякі аспекти
дизайну в процедурах інтерфейсу, які можна додатково вдосконалити,
наприклад, обробка ізольованих точок зупинки на спрямованих відрізках.
Гіперевристична продуктивність також може бути покращена шляхом додавання
нової евристики низького рівня; було б особливо цікаво включити евристику, яка
додає та видаляє маршрути, щоб дозволити різну кількість маршрутів. Однією з
проблем розробки евристики генерації маршруту є визначення оптимальних
початкового та кінцевого вузлів. Підхід до цього представлено в Heyken Soares
(2020b). (Додаткові обговорення інтеграції в інтерфейси представлені тут, у
розділі 7 Heyken Soares (2020a)).
Хоча ця робота є лише доказом концепції, вона демонструє потенціал повної
реалізації такого інтерфейсу в реальному плануванні громадського транспорту.
Враховуючи очікуваний вплив таких інновацій, як підключені автономні
транспортні засоби, на ландшафт громадського транспорту, ми вважаємо, що
такі інструменти, як представлений тут, можуть допомогти планувальникам у
необхідній адаптації мереж громадського транспорту. Тому ми сподіваємося, що
ця робота стане сходинкою на шляху до широкого застосування алгоритмів
проектування мережі в громадському транспорті в реальному світі.
77
СПИСОК ЛІТЕРАТУРИ
1 Software manual from PTV Group. PTV Visum 13 manual. Karlsruhe,
Germany, 2013.
2 TSS-Transport Simulation Systems. Aimsun - traffic modelling without
boundaries. Website, http://www.aimsun.com/wp/?page_id=21, May 2014.
3 Software manual from INRO. EMME/2 User’s Manual Software Release 9.
Montreal, Canada, April 1999.
4 Caliper Corporation. Transmodeler traffic simulation software. Website, http:
//www.caliper.com/transmodeler/Simulation.htm, May 2014.
5 Luis G. Willumsen Juan de D. Ortuzar. Model ling transport. Book published by
John Wiley & Sons Ltd, 4th edition, 2011.
6 National Cooperative Highway Research Program (NCHRP). Report 716:
Travel Demand Forecasting: Parameters and Techniques. Transportation Research
Board 2012 Executive Committee, 2012.
7 California department of Transportation. What is modeling? Website, http:
//www.dot.ca.gov/hq/tsip/otfa/microsim/whatis_modeling.html, September 2012.
8 Wahba M Parveen M, Shalaby A. G-emme/2: Automatic calibration tool of the
emme/2 transit assignment using genetic algorithms. J Transp Eng, 133:549-555, 2007.
9 Fung WCS. Calibration and validation of transit network assignment models.
Master’s thesis, Master thesis from University of Hong Kong, 2005.
10 Horowitz AJ. Subjective value of time in bus transit travel. Transportation,
10:149-164, 1981.
11 Wardman M. Public transport values of time. Transp Policy, 11:363-377, 2004.
12 Wardman M Abrantes PAL. Meta-analysis of uk values of travel time: An
update. Transp Res A, 45:1-17, 2011.
13 Fonzone A Hemdan SMH Shimamoto H Bell MGH Kurauchi F, Schmcker J-D.
Estimating weights of times and transfers for hyperpath travelers. J Transp Res Board,
78
2284:89-99, 2012.
14 Clas Rydergren. Comparison of headway-based public transport models:
Numerical experiments for stockholm. Public Transp, 5:177-191, 2013.
15 Isabelle Constantin Michael Florian. A note on logit choices in strategy transit
assignment. EURO J Transp Logist, 1:29-46, 2012.
16 Heinz Spiess Michael Florian. Optimal strategies: A new assignment model for
transit networks. Report from Transpn. Res.-B journal, 23B:83-102, 1989.
17 M. Florian M. Cepeda, R. Cominetti. A frequency-based assignment model for
congested transit networks with strict capacity constraints: characterization and
computation of equilibria. Transportation Research Part B: Methodological, 40 Issue
6:437-459, 2006.
18 Ahmed L, Heyken Soares P, Mumford C, Mao Y (2019) Optimising bus routes
with fixed terminal nodes: comparing hyper-heuristics with NSGAII on realistic
transportation networks. In: Proceedings of the genetic and evolutionary computation
conference. ACM, pp 1102-1110
19 Ahmed L, Mumford C, Kheiri A (2019) Solving urban transit route design
problem using selection hyperheuristics. Eur J Oper Res 274(2):545-559
20 Alt B, Weidmann U (2011) A stochastic multiple area approach for public
transport network design. Public Transp 3(1):65-87. https://doi.org/10.1007/s12469-
011-0042-0
21 Baaj MH, Mahmassani HS (1995) Hybrid route generation heuristic algorithm
for the design of transit networks. Transp Res Part C Emerg Technol 3(1):31-50
22 Bagloee SA, Ceder AA (2011) Transit-network design methodology for actual-
size road networks. Transp Res Part B Methodol 45(10):1787-1804
23 Bielli M, Caramia M, Carotenuto P (2002) Genetic algorithms in bus network
optimization. Transp Res Part C Emerg Technol 10(1):19-34
24 Burke EK, Hyde M, Kendall G, Ochoa G, Ozcan E, Woodward JR (2019) A
classification of hyper-heuristic approaches: revisited. In: Handbook of metaheuristics,
vol 272. Springer, pp 453-477
79
25 Bussieck M (1998) Optimal lines in public rail transport. PhD thesis, TU
Braunschweig
26 Ceder A, Wilson NH (1986) Bus network design. Transp Res Part B Methodol
20(4):331-344
27 Chien S, Schonfeld P (1997) Optimization of grid transit system in
heterogeneous urban environment. J Transp Eng 123(1):28-35
28 Cipriani E, Gori S, Petrelli M (2012) Transit network design: a procedure and an
application to a large urban area. Transp Res Part C Emerg Technol 20(1):3-14
29 Fan L, Mumford CL (2010) A metaheuristic approach to the urban transit routing
problem. J Heuristics 16(3):353-372
30 Fan W, Machemehl RB (2006) Using a simulated annealing algorithm to solve
the transit route network design problem. J Transp Eng 132(2):122-132
31 Franz H-D (1975) Untersuchung zur Planung von Verkehrsnetzen unter
besonderer Beracksichtigung des offentlichen Personennahverkehrs. Forschung
StrOfenbau und StraBenverkehrstechnik, p 182
32 Friedrich M, Haupt T, Noekel K (1999) Planning and analyzing transit networks:
an integrated approach regarding requirements of passengers and operators. J Public
Transport 2(4):19-39
33 Guan J, Yang H, Wirasinghe SC (2006) Simultaneous optimization of transit
line configuration and passenger line assignment. Transp Res Part B Methodol
40(10):885-902
34 Heyken Soares P (2020a) Three steps towards practical application of public
transport route optimisation in urban areas. PhD thesis, University of Nottingham
35 Heyken Soares P (2020b) Zone-based public transport route optimisation in an
urban network. Public Transp. https://doi.org/10.1007/s12469-020-00242-0
36 Heyken Soares P, Mumford CL, Amponsah K, Mao Y (2019) An adaptive scaled
network for public transport route optimisation. Public Transp 11(2):379-412.
https://doi.org/10.1007/s12469-019- 00208-x
37 INRO (2018) INRO, Montreal, Canada. Emme 4 User Manual
80
38 John MP, Mumford CL, Lewis R (2014) An improved multi-objective algorithm
for the urban transit routing problem. In: Blum C, Ochoa G (eds) Evolutionary
computation in combinatorial optimisation. Springer, Berlin, pp 49-60
39 Kheiri A, Keedwell E (2015) A sequence-based selection hyper-heuristic
utilising a hidden Markov model. In: Proceedings of the 2015 annual conference on
genetic and evolutionary computation. ACM, pp 417-424
40 Kheiri A, Keedwell E (2017) A hidden markov model approach to the problem
of heuristic selection in hyper-heuristics with a case study in high school timetabling
problems. Evolut Comput 25(3):473-501
41 Kilig F, Gok M (2014) A demand based route generation algorithm for public
transit network design. Comput Oper Res 51:21-29
42 Marauli A (2011) Nachfrageorientierte Verkehrsmodellbasierte OPNV-
Planung. TU Graz
43 Mumford CL (2013) New heuristic and evolutionary operators for the multi-
objective urban transit routing problem. In: 2013 IEEE congress on evolutionary
computation (CEC). IEEE, pp 939-946
44 Nayeem MA, Rahman MK, Rahman MS (2014) Transit network design by
genetic algorithm with elitism. Transp Res Part C Emerg Technol 46:30-45
45 Nikolic M, Teodorovic D (2013) Transit network design by bee colony
optimization. Expert Syst Appl 40(15):5945-5955
46 Nikolic M, Teodorovic D (2014) A simultaneous transit network design and
frequency setting: computing with bees. Expert Syst Appl 41(16):7200-7209
47 Nokel K (2006) Network design for public transport. PTV AG
48 Pacheco J, Alvarez A, Casado S, Gonzάlez-Velarde JL (2009) A tabu search
approach to an urban transport problem in Northern Spain. Comput Oper Res
36(3):967-979
49 Poorzahedy H, Safari F (2011) An ant system application to the bus network
design problem: an algorithm and a case study. Public Transp 3(2):165-187.
https://doi.org/10.1007/s12469-011-0046-9
81
50 Pternea M, Kepaptsoglou K, Karlaftis MG (2015) Sustainable urban transit
network design. Transp Res Part A Policy Pract 77:276-291
51 PTV AG (2014) Introduction to the PTV Visum COM-API, Karlsruhe
52 PTV AG (2017a) PTV Visum 17—overview of examples in the Visum
installation, Karlsruhe
53 PTV AG (2017b) Vision Traffic Suite—Tutorial PTV Visum 17 Quick Start,
Karlsruhe
54 PTV AG (2018) PTV Visum 17 User Manual, Karlsruhe
55 Silman LA, Barzily Z, Passy U (1974) Planning the route system for urban
busses. Comput Oper Res 1:201-211
56 Simonis C (1981) Optimierung von Omnibuslinien. Berichte des Instituts fir
Stadtbauwesen, RWTH Aachen, p 26
57 Sonntag H (1977) Linienplanung im offentlichen Personennahverkehr. PhD
thesis, Technical University Berlin
58 van Oudheusden D, Ranjithan S, Singh K (1987) The design of bus route
systems—an interactive location-allocation approach. Transportation 14(3):253-270
59 Walter S (2010) Nachfrageorientierte Liniennetzoptimierung am Beispiel Graz
(demand orientated line optimisation at the example of Graz). Master’s thesis,
Technische Universitat Graz
60 Yu B, Yang Z-Z, Jin P-H, Wu S-H, Yao B-Z (2012) Transit route network
design-maximizing direct and transfer demand density. Transp Res Part C Emerg
Technol 22:58-75