Методи прискорювання обчислень в задачах оптимальної маршрутизації

Левченко, А. Ю.

Публікація:
Методи прискорювання обчислень в задачах оптимальної маршрутизації

dc.contributor.author	Левченко, А. Ю.
dc.date.accessioned	2016-08-01T08:11:46Z
dc.date.available	2016-08-01T08:11:46Z
dc.date.issued	2013
dc.description.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.	uk_UA
dc.identifier.citation	Левченко А. Ю. Методи прискорювання обчислень в задачах оптимальної маршрутизації : автореф. ... канд. техн. наук : 01.05.02 – "Математичне моделювання та обчислювальні" / А. Ю. Левченко ; Харк. нац. ун-т радіоелектроніки. – Х., 2013. – 19 с.	uk_UA
dc.identifier.uri	http://openarchive.nure.ua/handle/document/1692
dc.language.iso	uk	uk_UA
dc.subject	загальна задача комівояжера	uk_UA
dc.subject	симетрична задача комівояжера	uk_UA
dc.subject	гамільтонова задача комівояжера	uk_UA
dc.subject	наближений розв’язок	uk_UA
dc.subject	точний розв’язок	uk_UA
dc.subject	транспортні мережі	uk_UA
dc.subject	оптимізація	uk_UA
dc.subject	графи	uk_UA
dc.subject	General Traveling Salesman Problem	uk_UA
dc.subject	Symmetric TravelingSalesman Problem	uk_UA
dc.subject	Hamiltonian Traveling Salesman	uk_UA
dc.subject	Problem approximate solution	uk_UA
dc.subject	exact solution	uk_UA
dc.subject	transport networks	uk_UA
dc.subject	optimization	uk_UA
dc.subject	graph	uk_UA
dc.title	Методи прискорювання обчислень в задачах оптимальної маршрутизації	uk_UA
dc.type	Other	uk_UA
dspace.entity.type	Publication