Програмне забезпечення для вирішення задачі оптимізації транспортного руху

Скорочена інформація про документ
dc.contributor.advisorЖаріков, Едуард В'ячеславович
dc.contributor.authorЖнакін, Володимир Володимирович
dc.date.accessioned2024-03-11T13:39:47Z
dc.date.available2024-03-11T13:39:47Z
dc.date.issued2024
dc.description.abstractРозмір пояснювальної записки – 123 аркушів, містить 44 ілюстрацій, 22 таблиці, 3 додатків, 51 посилань на джерела. Актуальність теми. Сучасні системи керування транспортними маршрутами потребують розроблення програмного забезпечення, що реалізує більш точні та швидкі алгоритми розв’язання задачі комівояжера, які забезпечують для великої кількості точок пошук найкращого маршруту з порівняно невеликою похибкою за коротший час. Основними недоліками існуючих реалізацій є стохастичність, обмежена адаптивність до параметрів задачі та велика чутливість до початкових умов, що призводить до невірних рішень та непотрібних витрат ресурсів. Через це, розроблення нового алгоритму для вирішення задачі оптимізації транспортного руху, який усуне ці недоліки, є актуальним завданням. Мета дослідження. Основна мета полягає у покращенні процесу побудови транспортних маршрутів за рахунок розроблення програмного забезпечення, що реалізує новий алгоритм вирішення задачі комівояжера, який дозволяє знайти оптимальний або наближений до оптимального маршрут та сприяє покращенню транспортного руху. Об'єкт дослідження: програмне забезпечення побудови оптимальних транспортних маршрутів для використання у різних предметних галузях. Предмет дослідження: методи, підходи та алгоритми вирішення задачі комівояжера в основі прикладного програмного забезпечення побудови наближених до оптимальних маршрутів. Для досягнення мети повинні бути виконані такі завдання: – проаналізувати існуючі рішення та літературу; – розробити новий алгоритм для розв’язання задачі комівояжера, враховуючи різні вхідні дані та умови; – провести аналіз продуктивності розробленого алгоритму, порівнявши його результати з існуючими методами розв'язання задачі комівояжера та можливі шляхи його покращення; – розробити програмне забезпечення побудови оптимальних транспортних маршрутів на основі запропонованого алгоритму; – провести експерименти на різноманітних наборах даних, включаючи реальні сценарії, з метою оцінки роботи програмного забезпечення. Науковою новизною роботи є реалізація інтерфейсу та необхідної функціональності при побудові наближених до оптимальних маршрутів з урахуванням особливостей запропонованого алгоритму розв’язання задачі комівояжера, що відрізняється від існуючих використанням тільки суттєвих вхідних даних і умов та дозволяє покращити пошук маршруту у різних варіантах застосування. Практичне значення отриманих результатів полягає у тому, що запропоновано реалізацію, яка вирішить конкретні проблеми транспортної індустрії та надасть додаткові можливості для суспільства та транспортної інфраструктури. Зв'язок з науковими програмами, планами, темами. Робота виконувалась на кафедрі інформатики та програмної інженерії Національного технічного університету України "Київський політехнічний інститут імені Ігоря Сікорського". Апробація. Наукові положення дисертації пройшли апробацію на V Міжнародній науково-практичній конференції молодих вчених та студентів «Інженерія програмного забезпечення і передові інформаційні технології SoftTech-2023». Публікації. Наукові положення дисертації опубліковані в: 1) Розробка програмного забезпечення на основі покращеного геометричного алгоритму для вирішення задачі оптимізації транспортного руху / В.В. Жнакін, Е. В. Жаріков // Матеріали V Міжнародної науково-практичної конференції молодих вчених та студентів «Інженерія програмного забезпечення і передові інформаційні технології SoftTech-2023» – м. Київ: НТУУ «КПІ ім. Ігоря Сікорського», 12-21 грудня 2023 р.
dc.description.abstractotherExplanatory note size – 123 pages, contains 44 illustrations, 22 tables, 3 appendices, and 51 references to sources. Topicality. Modern transport route management systems require the development of software that implements more accurate and faster algorithms for solving the traveling salesman problem, which provide for a large number of points the search for the best route with a relatively small error in a shorter time. The main disadvantages of the existing implementations are stochasticity, limited adaptability to the parameters of the problem and high sensitivity to the initial conditions, which leads to incorrect decisions and unnecessary expenditure of resources. Because of this, the development of a new algorithm for solving the problem of traffic optimization, which will eliminate these shortcomings, is an urgent task. The aim of the study. The main goal is to improve the process of building transport routes through the development of software that implements a new algorithm for solving the traveling salesman problem, which allows you to find an optimal or near-optimal route and contributes to the improvement of traffic. Object of research: software for building optimal transport routes for use in various subject areas. Subject of research: methods, approaches and algorithms for solving the traveling salesman's problem based on application software for constructing approximate optimal routes. To achieve the goal, the following tasks must be completed: – analyze existing solutions and literature; – develop a new algorithm for solving the traveling salesman problem, taking into account different input data and conditions; – analyze the performance of the developed algorithm, comparing its results with existing methods of solving the traveling salesman's problem and possible ways to improve it; – develop software for building optimal transport routes based on the proposed algorithm; – to conduct experiments on various data sets, including real scenarios, in order to evaluate the performance of the software. The scientific novelty of the work is the implementation of the interface and the necessary functionality when building approximate to optimal routes, taking into account the features of the proposed algorithm for solving the traveling salesman problem, which differs from the existing ones by using only essential input data and conditions and allows to improve the route search in various application options. The practical value of the obtained results is that an implementation is proposed that will solve specific problems of the transport industry and provide additional opportunities for society and transport infrastructure. Communication with scientific programs, plans, topics. The work was performed at the Department of Informatics and Software Engineering of the National Technical University of Ukraine "Ihor Sikorsky Kyiv Polytechnic Institute". Approbation. The scientific provisions of the dissertation were approved by V International scientific and practical conference of young scientists and students "Software engineering and advanced information technologies SoftTech-2023". Publications. The scientific provisions of the dissertation are published in: 1)Development of software based on an improved geometric algorithm for solving the problem of traffic optimization/ V.V. Zhnakin, E. V. Zharikov // Materials of the 5th International Scientific and Practical Conference of Young Scientists and Students "Software Engineering and Advanced Information Technologies SoftTech-2023" - Kyiv: NTUU "KPI named after Igor Sikorsky", December 12-21, 2023.
dc.format.extent123 с.
dc.identifier.citationЖнакін, В. В. Програмне забезпечення для вирішення задачі оптимізації транспортного руху : магістерська дис. : 121 Інженерія програмного забезпечення / Жнакін Володимир Володимирович. - Київ, 2024. - 123 с.
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/65422
dc.language.isouk
dc.publisherКПІ ім. Ігоря Сікорського
dc.publisher.placeКиїв
dc.subjectкомбінаторна оптимізація
dc.subjectзадача комівояжера
dc.subjectоптимальний маршрут
dc.subjectчас виконання
dc.subjectточність
dc.subjectiOS
dc.subjectSwift
dc.subjectUIKit
dc.subjectMapKit
dc.subjectcombinatorial optimization
dc.subjecttraveler's problem
dc.subjectoptimal route
dc.subjectexecution time
dc.subjectaccuracy
dc.subject.udc004.42
dc.titleПрограмне забезпечення для вирішення задачі оптимізації транспортного руху
dc.title.alternativeSoftware for Solving Traffic Optimization Problems
dc.typeMaster Thesis

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
Zhnakin_magistr.pdf
Розмір:
7.08 MB
Формат:
Adobe Portable Document Format
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
8.98 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Магістерські роботи (ІПІ)
Магістерські роботи