ВДОСКОНАЛЕННЯ СИСТЕМИ БРОНЮВАННЯ ТА ПОШУКУ КВИТКІВ В ОНЛАЙН СЕРВІСАХ УКРАЇНИ



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

Ключові слова: сервіси бронювання та пошуку квитків, теорія графів, алгоритми Дейсктрі та А*, пошук маршрутів он-лайн.

Improvement of searching and booking tickets in online services of Ukraine

Rudnytskykh Dmytro Olesandrovich, Student NTUU «KPI», Kyiv, Ukraine

Summary. The article deals about general description of searching and booking tickets to the online services of Ukraine. There have been identified disadvantages and basic solutions, including the use of Dejkstra algorithm and A* algorithm, that make additional assumptions or conduct so-called informative search in the analysis of the main features ticket services online. It was concluded about the lack of a universal algorithm for solving a wide range of tasks, which leads to the need to findthe optimal combination of instruments and tools for software and play all reasonable search customer needs.

Keywords: services search and booking tickets, graph theory, algorithms Dijkstra and A * search routes online.

У сучасному українському суспільстві такі сервіси, як Яндекс.Карти та Google.Maps вже змінили наше уявлення про побудову маршрутів, як використовуючи власний транспорт, так і громадський. На сьогодні звичним стали системи побудови шляхів в навігаторах та інших пристроях та придбання за обраними маршрутами квитків он-лайн. Водночас окремі системи для покупки квитків, зокрема офіційний сервіс ПАТ «Укрзалізниці» – booking.uz.gov.ua, недостатньо задовольняють потреби споживача та не відповідають сучасним вимогам, хоча ПАТ«Укразалізниця» є монополістом у сфері надання послуг залізничних перевезень і більша частина споживачів користується саме цим сервісом. Аналізуючи основні можливості сервісу продажу квитків он-лайн на сайті booking.uz.gov.ua, можна виділити такі недоліки:

- відсутність публічного API для отримання інформації про маршрути та наявність квитків;

- неможливість побудови маршрутів, якщо між двома пунктами відсутні прямі сполучення;

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

- можливість шукати квитки тільки на точну дату;

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

- відсутність інтеграції з іншими системами сполучення (авіа- та автотранспорт);

- відсутність мобільних додатків.

Логічно, що в Україні з’явилося багато систем, які намагаються вирішити одну чи декілька з вищеперерахованих проблем. Такі сервіси, наприклад, bilet.privatbank.ua та e-kvytok.kiev.ua створюють для зручності користування мобільні додатки та інтегруються з іншими сервісами. Сервіс tickects.ua додатково надсилає споживачу послуги нагадування про появу нових квитків за допомоги e-mail та sms та надає більш гнучкий пошук.

Проблему з відсутності відкритого API та відсутності інтеграції з іншими системами сполучення вирішила ТОВ «Argest group» (http://www.argest.com.ua/) з сервісом Uticket-api, які дають інформацію про наявні квитки, однак не дають додаткової інформації про усі можливі маршрути, якщо квитків немає в наявності.

На рівні з вищевикладеним залишаються дві проблеми, які до сьогодні не вирішені на рівні жодного з он-лайн-сервісів продажу квитків – відсутність єдиної системи для всіх видів залізничного транспорту та неможливість побудови складних маршрутів. Сьогодні інформацію про приміські потяги наявна на одному з шести підрозділів сайту ПАТ«Укрзалізниці». Цю проблему дуже складно вирішити за допомоги зовнішніх розробників, але розробити систему для розрахунку маршрутів з пересадками цілком можливо при наявності відкритого API. Подібну задачу вирішує будь-який сервіс пошуку авіаквитків та багато залізничних кас Європи та США. Водночас така система пошуку залізничних маршрутів враховуючи можливі пересадки, все одно має певні обмеження. Так, користувачу необхідно надати декілька варіантів маршруту; треба враховувати, наявність квитків у продажу за обраними маршрутами, оскільки користувач можливо захоче отримувати повідомлення, коли з’являться додаткові місця; пересадки між рейсами повинні враховувати час відправлення від кожної станції та деяку дельту для зміни транспорту; кількість пересадок не може бути більше деякого заданого числа, наприклад п’яти, оскільки при більшому значенні це може дуже ускладнити пересування пасажира; між двома станціями може бути більше, ніж один маршрут; якщо використовувати різні метрики в якості ваги ребер, наприклад ціна, то додатково необхідно враховувати різні типи місць в рамках одного вагону; необхідно підтримувати актуальність даних кожного дня, оскільки багато маршрутів мають дуже специфічний розклад руху та сезонність, які не можливо наперед передбачити.

Побудова системи, яка б враховувала вищевказані обмеження, можлива за допомогою вирішення класичної задачі з теорії графів – а саме задачі пошуку найкоротшого шляху. Оскільки реально допустимий маршрут в результаті не може складатися з великої кількості пересадок, тому не має сенсу розглядати дуже складні алгоритми. Відповідно варто надати перевагу алгоритмам Дейсктрі та А*, які роблять додаткові припущення, або проводять так званий інформативний пошук.[1]

Класичний алгоритм Дейкстри працює тільки для графів без циклів від’ємної довжини. У процесі роботи алгоритму послідовно позначаються розглянуті вершини графа. Причому вершина, позначена останньої (на даний момент) розташована ближче до вихідної вершині, ніж всі непозначених, але далі, ніж всі помічені. Спочатку позначається вихідна вершина; наступної, очевидно, буде позначена вершина, найближча до початкової, і суміжна з нею. Нехай на якомусь кроці вже позначений кілька вершин. Відомі найкоротші шляхи, що ведуть з вихідної вершини до поміченим. Для кожної з непозначених вершин проробимо наступне: 1. Розглянемо всі дуги, провідні з помічених вершин в одну непозначених. Кожна така дуга є останньою дугою на шляху з вихідної вершини в цю непозначених. 2. Виберемо з цих шляхів найкоротший. А потім виберемо серед них самий короткий до всіх непозначених вершин, і позначимо вершину, до якоївін веде. Алгоритм завершиться, коли будуть помічені всі досяжні вершини. У результаті роботи алгоритму Дейкстри будується Дерево найкоротших шляхів.[2]

Алгоритм А* належить до евристичних алгоритмів пошуку. Алгоритм використовує допоміжну функцію (евристику), аби скеровувати напрям пошуку та скорочувати його тривалість. Алгоритм повний в тому сенсі, що завжди знаходить оптимальний розв’язок, якщо він існує. Алгоритм А* спершу відвідує ті вершини, які ймовірно ведуть до найкоротшого шляху до мети. Аби розпізнати такі вершини, кожній відомій вершиніx зіставляється значення $f\left( x \right)$, яке дорівнює довжині найкоротшого шляху від початкової вершини до кінцевої, який пролягає через обрану вершину. Вершини з найменшим значенням f обираються в першу чергу. Функція $f\left( x \right)$ для вершини x визначається так: $f\left(x \right)=g\left( x \right)+h\left( x \right)$, де: $g\left( x \right)$ функція, значення якої дорівнюють вартості шляху від початкової вершини до $x,$ $h\left( x \right)-$ евристична функція, оцінює вартість шляху від вершини x до кінцевої [3]. Використана евристика не повинна давати завищену оцінку вартості шляху. Прикладом оцінки може служити пряма лінія: загальний шлях не може бути коротшим за пряму лінію. Головною різницею цих алгоритмів є наявність евристичної функції, яка дає виграш у швидкості, бо алгоритмічна складність Дейкстрі та $A*O\left(\left| E \right|+\left| V \right|*\log \left| V \right| \right)$ та $O\left(\left| V \right|*\log \left| V \right| \right)$ відповідно.

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

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

Список використаних джерел

  1. Pathfinding [Електронне видання]. – Електр. дан. – Режим доступу:

  2. http://en.wikipedia.org/wiki/Pathfinding Молчановський О. Курс з дискретної математики. / О.Молчановський // [Електронний ресурс]. – Режим доступу: http://oim.asu.kpi.ua/files/DM/30\_Shortest\_path\_algorithms.pdf

  3. Жигаревич О.К. Методита засоби проектування та розробки системи оптимізації транспортних маршрутів /О.К.Жигаревич// Науковий журнал «Комп’ютерно-інтегровані технології: освіта, наука, виробництво». – Луцьк, 2013. – Випуск №11.
  • Рецензент: к.т.н., доц. каф. ТК НТУУ "КПІ" Ліхоузова Т. А.
May 26, 2016