Задача командного спортивного орієнтування з урахуванням часових вікон
Дата
2018
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
Анотація
Магістерська дисертація: 110 с., 20 рис., 22 табл., 1 додаток, 84 джерела.
Актуальність. Всесвітня туристська організація (World Tourism Organization, UNWTO) визначає впровадження нововведень в туризмі однією з основних функцій туристичного маркетингу. Тому, використання інформаційних технологій з метою розвитку туризму, є актуальною задачею на сьогоднішній день. В зв’язку з цим, широкого розповсюдження набули персоналізовані електронні туристичні путівники (Personalized Electronic Tourist guides, PETs), до функціональності яких відноситься задача побудови туристичних маршрутів. При її розв’язанні математична модель може відрізнятись з огляду на те, які умови предметної області враховуються. В даній роботі математичною моделлю виступає задача Командного спортивного орієнтування з часовими вікнами (Team Orienteering Problem with Time Windows, TOPTW).
Оскільки час реагування для програмного забезпечення є важливою ознакою, розробка ефективного алгоритму поставленої задачі на сьогоднішній день є актуальною задачею. Тому, дана робота присвячена дослідженню та удосконаленню розв’язування TOPTW.
Мета роботи і задачі дослідження. Метою є максимізація сумарної корисності побудованих туристичних маршрутів заданої тривалості з врахуванням часових періодів відвідування туристичних місць. Для досягнення поставленої мети необхідно вирішити такі завдання:
− провести аналіз відомих результатів розв’язування задачі TOPTW;
− розробити метод (модифікацію існуючого методу) розв’язання задачі з використанням технологій паралельного програмування;
− розробити алгоритмічне забезпечення задачі TOPTW;
− розробити програмну реалізацію алгоритму(ів);
− провести дослідження ефективності розробленого алгоритмічного забезпечення.
Об’єкт дослідження – процес складання туристичних маршрутів.
4
Предмет дослідження – задача командного спортивного орієнтування з часовими вікнами.
Методи дослідження, застосовані в роботі, базуються на метаевристичних алгоритмах.
Наукова новизна одержаних результатів полягає у модифікації алгоритму повторюваного локального пошуку, порівнянні його з алгоритмом іматійного відпалу, використанні технологій паралельного програмування для модифікації алгоритмів повторюваного локального пошуку і алгоритму імітаційного відпалу для розв’язання задачі задачі TOPTW.
Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалась у філії кафедри автоматизованих систем обробки інформації та управління Національного технічного університету України «Київський політехнічний інститут ім. Ігоря Сікорського» в рамках науково-дослідної теми Інституту кібернетики ім. В. М. Глушкова НАН України: «Розробити математичний апарат, орієнтований на створення інтелектуальних інформаційних технологій розв’язування проблем комбінаторної оптимізації та інформаційної безпеки» (шифр теми: ВФ.180.11).
Публікації. Результати роботи опубліковані у матеріалах науково практичної конференції «Інформатика та обчислювальна техніка-ІОТ-2017» [82], міжнародної науково-практичної конференції «Актуальні питання сьогодення» [83].
Опис
Ключові слова
детермінований локальний пошук, повторюваний локальний пошук, алгоритм імітаційного відпалу, задача побудови туристичних маршрутів, задача командного спортивного орієнтування з часовими вікнами, паралельне програмування, метаевристичні алгоритми, deterministic local search, iterated local search, simulated annealing algorithm, tourist trip design problem, team orienteering problem with time windows, parallel programming, metaheuristic algorithms
Бібліографічний опис
Прохорова, К. С. Задача командного спортивного орієнтування з урахуванням часових вікон : магістерська дис. : 122 Комп'ютерні науки та інформаційні технології / Прохорова Катерина Сергіївна. – Київ, 2018. – 111 с.