Детальная информация

Тема выпускной квалификационной работы: «Поиск субоптимального решения задачи коммивояжёра методом агрегирования транспортного графа». Данная работа посвящена исследованию нового подхода к приближенному решению задачи коммивояжера посредством декомпозиции и агрегирования транспортного графа. Задачи, которые решались в ходе работы: Обзор некоторых существующих методов решения задачи коммивояжера, оценка их свойств. Формулировка общего подхода к решению задачи коммивояжера посредством декомпозиции и агрегирования транспортного графа. Исследование влияния выбора параметров, определяющих подзадачи метода. Синтез критериев оптимальности для подзадач разбиения и агрегирования. Исследование влияния критериев оптимальности подзадач на качество решения. Особенностью работы является новизна выдвигаемого подхода, а также его перспективность как альтернатива другим методам решения. В финале работы был проведен численный эксперимент, в результате которого сделаны выводы относительно пригодности как подхода в целом, так и синтезированных критериев. Определен класс задач, для которых они могут давать решение, близкое к точному.

The subject of this graduate qualification work is “Search for suboptimal solution to TSP with graph aggregation”. The work is devoted to a new approach for solving the TSP with graph decomposition and aggregation. The tasks, fulfilled while processing the research: A review of some existing methods for solving the TSP and their property evaluationStating a basic approach for solving the TSP with graph decomposition and aggregation. A research of subproblem parameters impact on the process of solving the problem. Generation of optimal criteria for the graph partitioning and aggregation subproblems. A research of subproblem optimal criteria impact on the quality of solution. The work features novelty of the approach proposed and its perspectives as an alternative to existing methods for solving the TSP. In the end of this work there has been conduct a series of tests. The results of them allowed the author to assess not only the usability of the entire method, but also of the criteria proposed. Finally, a problem class, for which best results can be provided was defined.