Розв'язування задачі комівояжера великих розмірностей методом спільних ребер

No Thumbnail Available

Date

2014

Journal Title

Journal ISSN

Volume Title

Publisher

Видавництво Львівської політехніки

Abstract

Досліджено евристичні алгоритми розв'язання задачі комівояжера: найближчого сусіда, 2-Opt, 3-Opt, Ліна-Кернігана та Ліна-Кернігана-Гельсгауна. Здійснено порівняльний аналіз часу роботи алгоритмів та якості отриманих розв'язків. Запропоновано декомпозиційний метод знаходження розв’язків задачі комівояжера на основі спільних ребер. Existing heuristic algorithms for solving traveling salesman problem, such as Nearest Neighbor, 2-Opt, 3-Opt, Lin-Kernighan and Lin-Kernighan-Helsgaun have been investigated in this work. The algorithms have been compared in terms of running time and solution quality. Decomposition approach, based on using common edges in multiple solutions, has been proposed.

Description

Keywords

задача комівояжерaа, NN, 2-Opt, 3-Opt, алгоритм Ліна-Кернігана, алгоритм Ліна-Кернігана-Гельсгауна, евристика, велика розмірність, traveling salesman problem, NN, 2-Opt, 3-Opt, Lin-Kernighan, LKH, heuristics, large-scale

Citation

Базилевич Р. Розв'язування задачі комівояжера великих розмірностей методом спільних ребер / Р. Базилевич, Р. Кутельмах, А. Томчук // Вісник Національного університету "Львівська політехніка". – 2014. – № 800 : Комп’ютерні науки та інформаційні технології. – С. 278–285. – Бібліографія: 10 назв.