Электронный архив
Донецкого национального технического университета (г.Донецк)
Electronic archive of Donetsk national technical university (Donetsk)
 

eaDonNTU, Donetsk >
Научные труды ДонНТУ >
Серія: Інформатика, кібернетика та обчислювальна техніка >
Випуск 1 (19) >

Please use this identifier to cite or link to this item: http://ea.donntu.org/handle/123456789/30900

Title: Новітній метод розв’язання задач комбінаторної оптимізації великої розмірності
Other Titles: Новый метод решения задач комбинаторной оптимизации большой размерности
A novel method for solving large-scale combinatorial optimization problems
Authors: Погорілий, С.Д.
Потебня, А.В.
Погорелый, С.Д.
Pogorilyy, S.D.
Potebnia, A.V.
Keywords: задачі комбінаторної оптимізації
мінімальна опукла оболонка
задача комівояжера
картографічні сервіси
алгоритм Джарвіса
м’який реальний час
розбиття графів
NP-складні задачі
граф
задачи комбинаторной оптимизации
минимальная выпуклая оболочка
задача коммивояжера
картографические сервисы
алгоритм Джарвиса
мягкое реальное время
разбиение графов
NP-сложные задачи
combinatorial optimization problems
minimal convex hull
travelling salesman problem
map services
Jarvis march
soft real-time
graph partition
NP-hard problems
graph
Issue Date: 2014
Publisher: ДонНТУ
Citation: Наукові праці Донецького національного технічного університету. Серія: Інформатика, кібернетика та обчислювальна техніка : збірник статей. Вип. 1(19) / ДВНЗ "ДонНТУ" ; редкол.: О.Є. Башков (голов. ред.) та ін. - Донецьк : ДВНЗ "ДонНТУ", 2014.
Abstract: Вперше запропоновано ефективний метод розв’язання складних задач оптимізації в режимі м’якого реального часу. Формування розв’язків відбувається за допомогою розподілу множини вершин графа на сукупність оболонок та їх сполучення. Виконано низку експериментальних досліджень алгоритму та показано придатність його використання для розв’язання задачі комівояжера. Наведено рекомендації щодо застосування методу при розв’язанні прикладних задач.
Description: In this paper an effective method is first suggested for soft real-time solving large instances of optimization problems. The new method recursively splits the input graph vertices set into hulls and merges them into final result. A set of algorithm investigations is conducted and its suitability for solving the travelling salesman problem is demonstrated. The developed method can produce good quality solutions quickly due to O (n^2) time complexity and linear memory usage. Another important advantage of the new algorithm is its ability to parallel execution. The special program tool for real-time geographic routes calculation is designed based on the developed algorithm. Recommendations of method usage for applied tasks solving are provided.
URI: http://ea.donntu.org/handle/123456789/30900
Appears in Collections:Випуск 1 (19)

Files in This Item:

File Description SizeFormat
Pogorilyy.pdf1.92 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.