Базилевич Р.П., Кутельмах Р.К. Алгоритм приєднання часткових розв’язків у підмножинах при декомпозиції задачі комівояжера

УДК 519.16

Р.П. Базилевич, Р.К. Кутельмах

Національний університет “Львівська політехніка”,
кафедра програмного забезпечення

АЛГОРИТМ ПРИЄДНАННЯ ЧАСТКОВИХ РОЗВ’ЯЗКІВ У ПІДМНОЖИНАХ ПРИ ДЕКОМПОЗИЦІЇ ЗАДАЧІ КОМІВОЯЖЕРА

© Базилевич Р.П., Кутельмах Р.К., 2009

Запропоновано новий метод приєднання часкових розв’язків у підмножинах при декомпозиції задачі комівояжера. Алгоритм передбачає розбиття вхідної множини точок на підмножини. Процес розв’язання починається в певній підмножині, де розв’язок відомий. Розв’язок у наступній (сусідній) підмножині утворюється за допомогою розширення існуючого розв’язку.
Ключові слова – задача комівояжера, транспортна задача, декомпозиція, підмножина.

New algorithm is suggested for union partial TSP solutions in subsets, created with the decomposition. The algorithm presupposes splitting the initial vertex set into subsets. The solution begins in a certain initial subset, where solution is found. The solution in the next subset is found by expanding the existing initial one.
Keywords – traveling salesman problem, vehicle routing problem, decomposition, subarea.

Кількість посилань - 19