Ястребов Павло Сергійович

студент ХНУРЕ другого (магістерського) рівня вищої освіти

Харківський національний університет радіоелектроніки

Україна, м. Харків

 

Назаров Олексій Сергійович

кандидат технічних наук, доцент кафедри Програмної інженерії

Харківський національний університет радіоелектроніки

Україна, м. Харків

 

 Анотація: In this paper, we will consider and compare the performance of algorithms for solving problems of fast search for a path on geographic maps. Consider using a set of algorithms to use and identify the main problems of the studied approaches. Let us highlight the main disadvantages of methods and methods for optimizing algorithms.

 Ключові слова: АГРЕГАТОР, ТАКСІ, УПРАВЛІННЯ, ПЕРЕВЕЗЕННЯ, ОПТИМІЗАЦІЯ, АЛГОРИТМ, КОРОТКИЙ ШЛЯХ.

 

 Послуги таксі сьогодні користуються величезною популярністю серед усіх категорій населення. За допомогою даного сервісу можна оперативно прибути в місце призначення за відсутності особистого транспортного засобу. У будь-якому місті сьогодні функціонує величезна кількість компаній, що надають подібні послуги [1].

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

• оперативність;
• підвищений рівень комфорту;
• зручність переміщень;
• можливість перевозити досить об'ємні вантажі;
• відсутність необхідності шукати зупинку - таксі прибуває за вказаною адресою.

 Ринок агрегації послуг таксі стрімко зростає в Україні, та в країнах, що розвиваються - гравці вітчизняного ринку щорічно потроюють обсяги виручки і в кілька разів збільшують кількість скоєних поїздок. У більшості країн поява на ринку онлайн агрегаторів таксі призвело до трансформації індустрії транспортних перевезень і, особливо, на ринок таксомоторних послуг. Більш того, онлайн агрегатори таксі стали одними з перших компаній, що реалізують нові способи надання та споживання класичних послуг (таксі), що в значній мірі вплинуло на активний розвиток сервісів, що пропонують цифрову трансформацію оффлайн послуг.

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

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

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

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

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

• алгоритми, що дозволяють визначити оптимальний шлях [2]; 
• алгоритми, що дозволяють знайти субоптимальний шлях [3].

 У першій групі для знаходження рішення потрібно повністю дослідити деяку область. Найпростішим способом пошуку оптимального шляху є повний перебір всіх можливих маршрутів. В цьому випадку знайдений шлях буде найкоротшим. Однак такий спосіб не застосуємо в більшості випадків через надмірність накладних витрат, так як потрібно повне дослідження всієї карти і зберігання її в пам'яті. У зв'язку з цим на перший план виходить розробка алгоритмів пошуку субоптимальних шляхів. Прикладом є евристичні алгоритми, які на кожному кроці наближаються до кінцевої точки. Однак при пошуку одного з близьких до оптимального шляху слід враховувати, що спочатку важко точно передбачити, який саме варіант буде обраний. До того ж, однією з вимог до маршруту є його реалістичний зовнішній вигляд. В цьому випадку можна використовувати різні алгоритми при виборі напрямку на кожному кроці або різні алгоритми постобробки маршрутів.

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

• визначення можливого напрямку руху; 
• визначення ключових точок маршруту і видалення точок, що лежать на одній прямій; 
• випрямлення окремих ділянок шляху; 
• «Огрубіння» попереднього подання шляху. 

 На основі тестового аналізу було запропоновано включити такі алгоритми пошуку шляху: 

• алгоритм A *; 
• алгоритм Theta * [3].

 На рисунку 1 наведені приклади пошуку шляху між двома точками за допомогою алгоритмів A * і Theta *. 

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

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

 З рисунка видно, що шлях, отриманий за допомогою Theta*, коротше і, крім того, виглядає більш реалістичним. 

 Однак алгоритм Theta* виявляється досить важким через велику кількість звернень до ландшафту.

 Якщо використовувати в ньому функцію визначення наявності перешкод на прямій між двома точками застосувати до результату роботи алгоритму A *, вийде шлях, по реалістичності близький до результату роботи алгоритму Theta *, при цьому накладні витрати будуть на порядок менше.

Рисунок 1 - Порівняння шляху A * (червона лінія) c шляхом Theta * (синя лінія)

 

 Великий вплив на якість знаходження шляху надає спосіб представлення ландшафту. В основному для цього використовується представлення карти в вигляді матриці прохідності. Вибір форми осередку грає велику роль при реалізації алгоритму впливає на довжину отриманого шляху. У таблиці наведені основні використовувані форми осередків прохідності і збільшення (в середньому) знайденого шляху в порівнянні з оптимальним.

Таблиця 1

Форми клітинки сітки прохідності

 

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

 З огляду на сказане, при вирішенні поставленого завдання ми в більшості випадків будемо інтерпретувати карту набором квадратних осередків, складаючи з них сітку. Квадрати сітки будуть маркуватися числами 0 або 1 (проходимо або не проходим), тобто для кожного типу об'єкта і типу місцевості, по якому він рухається, визначається власне факт прохідності. У перспективі завдання може бути ускладнена введенням деякого штрафу, що відображає різний характер прохідності клітинки.

 Головна проблема завдання пошуку шляху полягає в тому, що не існує будь-якого універсального алгоритму її рішення. Разом з тим, на підставі проведених досліджень можна зробити висновок, що в разі пошуку шляху на географічних картах необхідно вибирати один з наступних способів вирішення завдання. Якщо потрібно отримати найбільш реалістичний вигляд субоптимального шляху, рекомендується використовувати алгоритм Theta *. Коли витрати на звернення до ландшафту виявляються критичними, рекомендується використовувати наступну комбінацію алгоритмів: застосовуємо алгоритм A * для отримання маршруту; видаляємо точки, що лежать на одній прямій; для кожної пари з невеликого безлічі отриманих ключових точок застосовуємо алгоритм перевірки наявності шляху по прямій. Можна застосовувати цей алгоритм лише до сусідніх відрізків шляху, розбиваючи їх шляхом впровадження фіктивних точок. У загальному випадку необхідно будувати систему алгоритмів, що мають схожі вхідні і вихідні дані, що дозволить обмінюватися даними на окремих кроках, комбінуючи різні підходи до вирішення завдання. Крім цього, важливим виявиться введення ієрархії: об'єднуючи окремі області ландшафту, можна прокладати шляхи спочатку між великими областями, потім, застосовуючи інші алгоритми, на окремих ділянках.

 

Література:

1. Черкасов, О.Н. Підвищення ефективності управління автотранспортом на базі сучасних інформаційних технологій / О.М. Черкасов, Г.Е.Ковалев, В.Є. Межов, В.К. Зольників // Інформаційні технології моделювання та управління. 2017. № 2 (20). С. 178-184

2. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритми. Побудова та аналіз. / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. – Москва, Вильямс, 2015.

3. Daniel K., Nash A., Koenig S., Felner A. Theta*: Any-Angle Path Planning on Grids. Journal of Artificial Intelligence Research, 2016, vol. 39, pp. 533–579.