Эффективные приближенные алгоритмы с оценками для асимметричной задачи коммивояжера
Аннотация
Рыженко К.В.ЭФФЕКТИВНЫЕ ПРИБЛИЖЕННЫЕ АЛГОРИТМЫ С ОЦЕНКАМИ ДЛЯ АСИММЕТРИЧНОЙ ЗАДАЧИ КОММИВОЯЖЕРА, магистерская диссертация: страниц, рисунков, таблиц, формул, 9 источников использованной литературы.
Ключевые слова: комбинаторная оптимизация, асимметричная задача коммивояжера, обобщенная задача коммивояжера с ограничениями предшествования.
Пpедмет исследования - постановки и приближенные алгоритмы решения асимметричной и обобщенной задач коммивояжера, сведение обобщенной задачи коммивояжера с ограничениями предшествования к постановке, решающейся методами смешанного целочисленного программирования (MIP).
Цель работы - изучение алгоритма Свенссона с константной оценкой точности для задачи ATSP, построение MIP постановки для задачи PCGTSP, численные эксперименты на публичных библиотеках постановок задач.
В ходе работы удалось познакомиться с самыми современными приближенными алгоритмами решения асимметричной задачи коммивояжера, предложить новую полиномиальную схему сведения обобщенной задачи с ограничениями предшествования к подходящей задаче смешанного линейного программирования, провести серию численных экспериментов с использованием данной постановки, системы Gurobi для решения
постановок из библиотеки PCGTSPLIB.
Ryzhenko K.V. EFFECTIVE APPROXIMATE ASSESSMENT ALGORITHMS FOR THE ASYMMETRIC PROBLEM OF THE TRAVELER, Master’s thesis: pages, figures, tables, formulas, 9 sources of used literature.
Keywords: combinatorial optimization, asymmetric traveling salesman problem, generalized traveling salesman problem with precedence constraints.
The research subject is statements and approximate algorithms for solving asymmetric and generalized traveling salesman problems, reducing the generalized traveling salesman problem with precedence constraints to a statement that solves using mixed integer programming (MIP) methods.
The purpose of the work is to study existing algorithms, their software implementation and numerical testing on ready-made libraries of problem statements.
In the course of the work, we were able to get acquainted with new algorithms for solving the asymmetric traveling salesman problem, as well as reduce the generalized traveling salesman problem with precedence constraints to the integer programming problem and
solve it using the Gurobi system.
Ключевые слова: комбинаторная оптимизация, асимметричная задача коммивояжера, обобщенная задача коммивояжера с ограничениями предшествования.
Пpедмет исследования - постановки и приближенные алгоритмы решения асимметричной и обобщенной задач коммивояжера, сведение обобщенной задачи коммивояжера с ограничениями предшествования к постановке, решающейся методами смешанного целочисленного программирования (MIP).
Цель работы - изучение алгоритма Свенссона с константной оценкой точности для задачи ATSP, построение MIP постановки для задачи PCGTSP, численные эксперименты на публичных библиотеках постановок задач.
В ходе работы удалось познакомиться с самыми современными приближенными алгоритмами решения асимметричной задачи коммивояжера, предложить новую полиномиальную схему сведения обобщенной задачи с ограничениями предшествования к подходящей задаче смешанного линейного программирования, провести серию численных экспериментов с использованием данной постановки, системы Gurobi для решения
постановок из библиотеки PCGTSPLIB.
Ryzhenko K.V. EFFECTIVE APPROXIMATE ASSESSMENT ALGORITHMS FOR THE ASYMMETRIC PROBLEM OF THE TRAVELER, Master’s thesis: pages, figures, tables, formulas, 9 sources of used literature.
Keywords: combinatorial optimization, asymmetric traveling salesman problem, generalized traveling salesman problem with precedence constraints.
The research subject is statements and approximate algorithms for solving asymmetric and generalized traveling salesman problems, reducing the generalized traveling salesman problem with precedence constraints to a statement that solves using mixed integer programming (MIP) methods.
The purpose of the work is to study existing algorithms, their software implementation and numerical testing on ready-made libraries of problem statements.
In the course of the work, we were able to get acquainted with new algorithms for solving the asymmetric traveling salesman problem, as well as reduce the generalized traveling salesman problem with precedence constraints to the integer programming problem and
solve it using the Gurobi system.