Інформаційна система розв'язку задачі комівояжера із застосуванням алгоритму імітації відпалу

Abstract

Задача комівояжера це одна з класичних проблем комбінаторної оптимізації, що має велике значення в багатьох сферах діяльності, включно з логістикою, виробництвом тощо. Ця проблема полягає у пошуку найкоротшого маршруту комівояжером, який відвідає всі дані міста та шлях якого завершиться у початковому пункті. Зростання обсягів даних та складності завдань вимагає розробки ефективних алгоритмів для їх розв'язання. Одним із найперспективніших підходів є використання алгоритму імітації відпалу, що базується на принципах термодинаміки і використовується для пошуку глобальних оптимальних рішень в складних задачах. Алгоритм імітації відпалу є евристичним методом, який дає можливість знаходити близькі до оптимальних маршрути з високою ймовірністю. Актуальність дослідження задачі комівояжера з використанням алгоритму імітації відпалу обумовлена наступними факторами: ефективність (алгоритм імітації відпалу може знаходити кращі маршрути, ніж інші евристичні методи, за порівняно невеликий час), універсальність (алгоритм імітації відпалу може бути застосований для розв'язання задачі комівояжера з різними типами даних, наприклад, з дискретними або неперервними координатами), простота (алгоритм імітації відпалу має зрозумілу концепцію та може бути легко реалізований програмно). Із використанням перелічених вище концепцій було розроблено ПЗ та складено інструкцію користувача, що дозволяє ознайомитись із технічними вимогами та методами використання інформаційної системи. Проведено аналіз контрольного прикладу, який продемонстрував позитивні результати. Об’єкт дослідження. Об’єктом дослідження є процес розв'язку задачі комівояжера із застосуванням алгоритму імітації відпалу. Предмет дослідження. Предметом дослідження є засоби і методи, які використовуються для створення інформаційної системи розв'язку задачі комівояжера із застосуванням алгоритму імітації відпалу. Мета дослідження. Метою виконання роботи є розробка інформаційної системи розв'язку задачі комівояжера із застосуванням алгоритму імітації відпалу. Результати дослідження. Результатом роботи є інформаційна система, яка надає можливість виконувати задачі пошуку розв'язку задачі комівояжера із застосуванням алгоритму імітації відпалу.The traveling salesman problem is one of the classic problems of combinatorial optimization, which is of great importance in many fields of activity, including logistics, production, etc. This problem consists in finding the shortest route by a traveling salesman that visits all given cities and whose path ends at the starting point. The growth of data volumes and the complexity of tasks requires the development of effective algorithms for their solution. One of the most promising approaches is the use of an annealing simulation algorithm, which is based on the principles of thermodynamics and is used to find global optimal solutions in complex problems. The annealing simulation algorithm is a heuristic method that makes it possible to find close to optimal routes with high probability. The relevance of researching the traveling salesman problem using the annealing simulation algorithm is due to the following factors: efficiency (the annealing simulation algorithm can find better routes than other heuristic methods in a relatively short time), universality (the annealing simulation algorithm can be applied to solve the traveling salesman problem with different data types, for example, with discrete or continuous coordinates), simplicity (the annealing simulation algorithm has a clear concept and can be easily implemented programmatically). With the use of the concepts listed above, the software was developed and the user manual was compiled, which allows you to familiarize yourself with the technical requirements and methods of using the information system. An analysis of the control example was carried out, which demonstrated positive results. Research Object. The object of the study is the process of solving the traveling salesman problem using the annealing simulation algorithm. Subject of the Study. The subject of the study encompasses the tools and methods used to create an information system for solving the traveling salesman problem using the annealing simulation algorithm. Research Objective. The objective of this work is to develop an information system for solving the traveling salesman problem using the annealing simulation algorithm.. Research Results. The result of this work is an information system that enables the tasks of solving the traveling salesman problem using the annealing simulation algorithm..