Please use this identifier to cite or link to this item: http://openarchive.nure.ua/handle/document/1692
Title: Методи прискорювання обчислень в задачах оптимальної маршрутизації
Authors: Левченко, А. Ю.
Keywords: загальна задача комівояжера
симетрична задача комівояжера
гамільтонова задача комівояжера
наближений розв’язок
точний розв’язок
транспортні мережі
оптимізація
графи
General Traveling Salesman Problem
Symmetric TravelingSalesman Problem
Hamiltonian Traveling Salesman
Problem approximate solution
exact solution
transport networks
optimization
graph
Issue Date: 2013
Citation: Левченко, А. Ю. Методи прискорювання обчислень в задачах оптимальної маршрутизації : автореф. ... канд. техн. наук : 01.05.02 – "Математичне моделювання та обчислювальні" / А. Ю. Левченко ; Харк. нац. ун-т радіоелектроніки. – Х., 2013. – 19 с.
Abstract: Метою дисертації є вдосконалення відомих методів оптимізації за- мкнених маршрутів на транспортних мережах, що включають в себе загальну, гамільтонову та симетричну задачі комівояжера (ЗЗК, ГЗК та СЗК відповідно). Для розв’язання ЗЗК запропоновано точний метод, в якому спочатку знаходяться найкоротші ланцюги між усіма парами вершин вхідного графа, а потім в отриманій матриці ваг алгоритмом Літла знаходиться розв’язок СЗК.Кожне ребро знайденого маршруту комівояжера заміняється на відповідний найкоротший ланцюг. Запропоновано метод розв’язання ЗЗК, яка піддається розбиттю на блоки. Розв’язки ЗЗК в блоках об'єднуються в шуканий маршрут за поліноміальний час. Розроблено наближений метод ЗЗК. Запропоновано модифікацію методу Літла з поліпшеною процедурою обчислення нижньої межі, заснованої на алгоритмі розв’язання варіанту зада- чі про призначення. Отримана модифікація має кращу швидкодію та менші вимоги до оперативної пам’яті. This thesis aims at improving existing methods of closed routes optimization in transport networks including the General TSP (GTSP), Hamiltonian TSP and Symmetric TSP. An exact method of GTSP is proposed which finds the shortest paths between all pairs of vertexes of an input graph and then solves metric TSP for the resulting weights matrix by Little’s method. The corresponding shortest paths replace every edge in the retrieved Salesman’s Route. A dividing into blocks GTSP’s solution method is developed. Blocks’ GTSP routes are united to the sought solution in polynomial time. An approximate GTSP method is developed. A modification of the Little’s method with improved lower bound calculations procedure, based on the Assignment Problem’s variant algorithm, is proposed. The applied modification has greater performance and lower memory requirements.
URI: http://openarchive.nure.ua/handle/document/1692
Appears in Collections:Автореферати

Files in This Item:
File Description SizeFormat 
LevchenkoAY.pdf265.12 kBAdobe PDFView/Open


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

Admin Tools