Розроблення геоінформаційної системи управління транспортними перевезеннями
Автор: Шупер Віталій Андрійович
Кваліфікаційний рівень: магістр
Спеціальність: Інформаційні технології проектування
Інститут: Інститут комп'ютерних наук та інформаційних технологій
Форма навчання: денна
Навчальний рік: 2021-2022 н.р.
Мова захисту: українська
Анотація: Шупер В.А., Белей О.І. Розроблення геоінформаційної системи управління транспортними перевезеннями. Магістерська кваліфікаційна робота. – Національний університет «Львівська політехніка», Львів, 2021 р. Розширена анотація Використання геоінформаційних систем значно зросло з 80-х та 90-х років. Однією з найважливіших проблем в цьому напрямку є пошук найкоротшого шляху. Кілька досліджень щодо пошуку найкоротшого шляху показують доцільність використання графів для досягнення цієї мети. Задача пошуку найкоротшого шляху є однією з найбільш класичних проблем алгоритмів у теорії графів, що має на меті знайти найкоротший шлях між двома вузлами в мережі. Цей алгоритм широко використовується для вирішення проблем пошуку шляхів у великій кількості додатків та систем, включаючи маршрутизацію в комп’ютерних мережах, штучний інтелект, дизайн ігор тощо. Об’єктом дослідження в даній роботі є геоінформаційна система для керування транспортними перевезеннями. Предметом дослідження є алгоритми пошуку найкращого шляху та геоінформаційні сервіси. Метою дипломної роботи є проектування та розробка геоінформаційної системи управління транспортними перевезеннями, а також дослідження наявних проблем в галузі досліджень маршрутизації та пошуку найкращого шляху. Дослідження принципів та методів пошуку найкоротшого шляху. Поглиблений аналіз існуючих досліджень теорії графів та засобів маршрутизації та розрахунків оптимального маршруту. Методи розробки – система розроблялася з використанням мов програмування Python та С++, а також використовуючи такі технології: OpenCV, OpenSSL; база даних – SQLite; десктопний інтерфейс – Kivy. Ряд дослідників у своїх роботах [2,3] представляє функціонування алгоритму Дейкстри, реалізуючи чергу з мінімальним пріоритетом з використанням хіпу Фібоначчі, а також аналізує та порівнює ефективність алгоритмів Джонсона та Флойда-Уоршалла. В інших дослідженнях[1] проведено оцінку складності та навантаження алгоритмів Дейкстри та Беллмана-Форда. Оцінка цих показників вказує, що складність алгоритму Дейкстри за часом швидша, ніж складність алгоритму Беллмана-Форда, але алгоритм Дейкстри не може бути використаний для вирішення графіків з негативними вагами ребер. Розроблено сервер, на якому відбувається обробка даних та побудова картографічної мережі облич, а також містить базу даних для збереження даних зареєстрованих користувачів, водіїв та пунктів відправки/призначення системи. Розроблено інтерфейс десктопної програми, що забезпечує отримання даних від сервера та візуалізацію маршрутів на карті. Приведені приклади роботи системи. Ключові слова: геоінформаційна система, граф, алгоритм, пошук найкоротшого шляху, база даних, картографічна мережа, клієнт, сервер. Список використаних джерел: Huang, B, Wu, Q, and Zhan, F.B. 2017. "A shortest path algorithm with novel heuristics for dynamic transportation networks. International Journal of Geographical Information Science. Vol. 21, No. 6, 625–644. Anu Pradhan, and Kumar, G. 2018. "Finding All-Pairs Shortest Path for a Large-Scale Transportation Network Using Parallel Floyd-Warshall and Parallel Dijkstra Algorithm". Journal of Computing in Civil Engineering ASCE. 263-273. Cormen, Thomas H, Leiserson, Charles E, and Rivest, Ronald L.Stein Clifford . 2017. "Johnson’s algorithm for sparse graphs". Introduction to Algorithms. ISBN 978-0-262 03293-3. 636–640.