PCGLNS: библиотека эвристических алгоритмов для обобщенной задачи коммивояжера с ограничениями предшествования
Аннотация
Кудрявцев А. В. PCGLNS: БИБЛИОТЕКА ЭВРИСТИЧЕСКИХ
АЛГОРИТМОВ ДЛЯ ОБОБЩЕННОЙ ЗАДАЧИ КОММИВОЯЖЕРА С
ОГРАНИЧЕНИЯМИ ПРЕДШЕСТВОВАНИЯ, магистерская диссертация: 48 страниц, 10 рисунков, 2 таблицы, 5 формул, 8 источников использованной литературы, 5 приложений.
Ключевые слова: комбинаторная оптимизация, эвристические
алгоритмы, обобщённая задача коммивояжера.
Предмет исследования — существующая система алгоритмов для решения задач GTSP, которая будет модифицирована для решения задач GTSP с ограничениями предшествования.
Цель работы — разработка, программная реализация и численное тестирование серии эвристических алгоритмов для решения задачи PCGTSP на основе существующих алгоритмов решения задач GTSP и SOP.
В ходе работы удалось модифицировать систему GLNS и обобщить её для решения задач PCGTSP. Были проведены эксперименты на постановках SOP и PCGTSP, проведён сравнительный анализ с аналогичными решениями существующих систем. Алгоритм оказался эффективен для решения задач PCGTSP.
Kudryavtsev A.V. PCGLNS: HEURISTIC ALGORITHMS LIBRARY FOR
THE GENERALIZED TRAVELING SALESMAN PROBLEM WITH
PRECEDENCE CONSTRAINTS, qualifying work: 48 pages, 10 figures, 2 tables, 5 formulas, 8 sources of literature, 5 appendices.
Keywords: combinatorial optimization, heuristic algorithms, generalized traveling salesman problem.
The subject of the study is the existing system of algorithms for solving GTSP problems, which will be modified to be able to solve GTSP problems with precedence constraints.
The purpose of the work is the development, software implementation and numerical testing of a series of heuristic algorithms for solving the PCGTSP problem based on existing algorithms for solving GTSP and SOP problems.
In the course of work, we were able to modify the GLNS system and generalize it to solve PCGTSP problems. Experiments were conducted on the productions of SOP and PCGTSP, a comparative analysis was carried out with similar solutions to existing systems. The algorithm turned out to be effective for
solving PCGTSP instances.
АЛГОРИТМОВ ДЛЯ ОБОБЩЕННОЙ ЗАДАЧИ КОММИВОЯЖЕРА С
ОГРАНИЧЕНИЯМИ ПРЕДШЕСТВОВАНИЯ, магистерская диссертация: 48 страниц, 10 рисунков, 2 таблицы, 5 формул, 8 источников использованной литературы, 5 приложений.
Ключевые слова: комбинаторная оптимизация, эвристические
алгоритмы, обобщённая задача коммивояжера.
Предмет исследования — существующая система алгоритмов для решения задач GTSP, которая будет модифицирована для решения задач GTSP с ограничениями предшествования.
Цель работы — разработка, программная реализация и численное тестирование серии эвристических алгоритмов для решения задачи PCGTSP на основе существующих алгоритмов решения задач GTSP и SOP.
В ходе работы удалось модифицировать систему GLNS и обобщить её для решения задач PCGTSP. Были проведены эксперименты на постановках SOP и PCGTSP, проведён сравнительный анализ с аналогичными решениями существующих систем. Алгоритм оказался эффективен для решения задач PCGTSP.
Kudryavtsev A.V. PCGLNS: HEURISTIC ALGORITHMS LIBRARY FOR
THE GENERALIZED TRAVELING SALESMAN PROBLEM WITH
PRECEDENCE CONSTRAINTS, qualifying work: 48 pages, 10 figures, 2 tables, 5 formulas, 8 sources of literature, 5 appendices.
Keywords: combinatorial optimization, heuristic algorithms, generalized traveling salesman problem.
The subject of the study is the existing system of algorithms for solving GTSP problems, which will be modified to be able to solve GTSP problems with precedence constraints.
The purpose of the work is the development, software implementation and numerical testing of a series of heuristic algorithms for solving the PCGTSP problem based on existing algorithms for solving GTSP and SOP problems.
In the course of work, we were able to modify the GLNS system and generalize it to solve PCGTSP problems. Experiments were conducted on the productions of SOP and PCGTSP, a comparative analysis was carried out with similar solutions to existing systems. The algorithm turned out to be effective for
solving PCGTSP instances.