Задача командного спортивного орієнтування з урахуванням часових вікон

Přispěvatelé: Гуляницький, Леонід Федорович
Jazyk: ukrajinština
Rok vydání: 2018
Předmět:
Popis: Магістерська дисертація: 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]. Master dissertation:110 p., 20 fig., 22 tab., 1 appendix, 84 sources. Relevance. The World Tourism Organization (UNWTO) identifies the introduction of tourism innovations as one of the main functions of tourism marketing. Therefore, the use of information technology for the development of tourism is an actual task to date. Because of that, personalized Electronic Tourist Guides (PETs), which encapsulate tourist trip design problem (TTDP), have become widespread. When TTDP is solved, the mathematical model may differ in terms of what the terms of the subject area are taken into account. In this paper, the problem of Team Orienteering Problem with Time Windows (TOPTW) is the mathematical model. As the response time for the software is an important feature, developing an effective algorithm for the task to date is an actual task. Therefore, this work is devoted to the research and improvement of the solution methods of TOPTW. Purpose and objectives of the study. The purpose is to maximize the total usefulness of the built tourist routes of a given duration, taking into account the time periods of visiting tourist places. To achieve this goal it is necessary to solve the following tasks: − to analyze known results of solving TOPTW; − to develop a method (modification of the existing method) for solving a problem using parallel programming technologies; − to develop algorithms for TOPTW; − to develop software implementation of the algorithms; − to study the effectiveness of the developed algorithms. The object of study – the process of designing tourist routes. Purpose of the study –team orienteering problem with time windows. The scientific novelty of the obtained results is in modifying the Iterated Local Search algorithm, comparing it with the algorithm of Simulated annealing, using parallel programming technologies for modifying the Iterated Local Search algorithms and the Simulated annealing algorithm for solving TOPTW. 6 Relationship of work with scientific programs, plans, themes. The work has been carried out at the branch of the Department of Computer-Aided Management and Data Processing Systems of The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" within the framework of the research topic of the Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine: "To develop a mathematical apparatus focused on the creation of intelligent information technologies for solving combinatorial optimization and information security problems" (topic code: VF.180.11). Publications. The results of the work are published in [82, 83].
Databáze: OpenAIRE
Externí odkaz: