Математичне та програмне забезпечення для побудови навігаційних маршрутів
Вантажиться...
Дата
2019-05
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Магістерська дисертація: 122 с., 36 рис., 8 табл., 4 додатка, 20 джерел.
Актуальність теми.
Рівень розвитку сучасних технологій дозволяє обладнувати мобільні пристрої (мобільні телефони, кишенькові та планшетні комп’ютери) засобами доступу до бездротового мобільного Інтернету та до глобальної системи супутникової навігації GPS. Це дає змогу організувати наземну навігацію рухомих об’єктів, зокрема, автомобільну, використовуючи мобільні навігаційні додатки.
Однією із найбільш важливих задач таких навігаторів є побудова оптимального маршруту руху об’єкта до заданої точки.
Наявні способи реалізації даного функціоналу в існуючих програмних засобах (таких як GoogleMaps, YandexMaps, AppleMaps та інші) передбачають при побудові маршруту можливість обрати на власний розсуд, як критерій оптимальності, найкоротшу відстань або найменший час. За замовчуванням система обирає найшвидший маршрут. Якщо існує два маршрути з однаковим часом проходження, система автоматично обирає найкоротший із них та пропонує альтернативний варіант.
Значним недоліком таких мобільних навігаторів є обмеженість вибору критеріїв оптимізації при побудові маршруту. Наприклад, відсутня можливість вибору маршруту з урахуванням якості дорожнього покриття, завантаженості доріг, якості їх освітленості, інформації про аварійні ситуації, ремонтні роботи, пробки, закриття дороги або зміну напрямку руху, допустимого відхилення від найменшого часу або найкоротшої дистанції тощо.
Тому мобільні навігатори, що забезпечують побудову навігаційних маршрутів з можливістю урахування додаткових критеріїв (таких як якість дорожнього покриття, освітленість дороги тощо), є дуже затребуваними, а їх розробка - вкрай актуальним завданням.
Мета і задачі дослідження.
Мета даної роботи полягає в дослідженні та розробці математичних та програмних засобів для багатокритеріальної побудови навігаційних маршрутів.
Для досягнення поставленої мети необхідно розв‘язати комплекс наступних взаємопов‘язаних задач:
дослідити існуючі методи та підходи до побудови навігаційних маршрутів;
дослідити існуючі методи багатокритеріальної оптимізації;
розробити математичне забезпечення для побудови багатокритеріальних навігаційних маршрутів;
розробити мобільний навігатор, який має підтримувати функціонал побудови навігаційних маршрутів з урахуванням декількох критеріїв оптимальності;
виконати експериментальне дослідження запропонованих рішень.
Об’єкт дослідження.
Процес побудови навігаційних маршрутів.
Предмет дослідження.
Методи багатокритеріальної оптимізації та алгоритми знаходження оптимальних шляхів у графі.
Наукова новизна одержаних результатів полягає у розробці метода побудови багатокритеріальних навігаційних маршрутів, який ґрунтується на використанні удосконаленого алгоритма A*.
Практичне значення одержаних результатів.
Всі запропоновані математичні методи і алгоритми доведені до практичної реалізації у рамках програмного забезпечення, яке використовується для побудови багатокритеріальних навігаційних маршрутів з урахуванням відстані і якості дорожнього покриття.
Публікації.
Матеріали роботи опубліковані в тезах конференції «Інформатика та обчислювальна техніка-ІОТ-2017» та «Інформаційні системи та технології управління - 2019»
Опис
Ключові слова
багатокритеріальна оптимізація, метод згортання критеріїв, алгоритми пошуку маршрутів, знаходження оптимального шляху, A*, побудова багатокритеріальних маршрутів, multi-criterian optimization, method of criteria building, algorithm of routine search, introduction of optimal way, building of multi-criterian routes
Бібліографічний опис
Храмченко, М. С. Методи та програмні засоби передачі об'єктів доповненої реальності : магістерська дис. : 121 Інженерія програмного забезпечення / Храмченко Микола Сергійович. – Київ, 2019. – 123 с.