Гуляницький, Леонід ФедоровичПрохорова, Катерина Сергіївна2018-07-062018-07-062018Прохорова, К. С. Задача командного спортивного орієнтування з урахуванням часових вікон : магістерська дис. : 122 Комп'ютерні науки та інформаційні технології / Прохорова Катерина Сергіївна. – Київ, 2018. – 111 с.https://ela.kpi.ua/handle/123456789/23794Магістерська дисертація: 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].ukдетермінований локальний пошукповторюваний локальний пошукалгоритм імітаційного відпалузадача побудови туристичних маршрутівзадача командного спортивного орієнтування з часовими вікнамипаралельне програмуванняметаевристичні алгоритмиdeterministic local searchiterated local searchsimulated annealing algorithmtourist trip design problemteam orienteering problem with time windowsparallel programmingmetaheuristic algorithmsMaster Thesis111 с.519.854.2