Публікація: Методи прискорювання обчислень в задачах оптимальної маршрутизації
Завантаження...
Дата
2013
Автори
Назва журналу
ISSN журналу
Назва тома
Видавництво
Анотація
Метою дисертації є вдосконалення відомих методів оптимізації замкнених маршрутів на транспортних мережах, що включають в себе загальну, гамільтонову та симетричну задачі комівояжера (ЗЗК, ГЗК та СЗК відповідно). Для розв’язання ЗЗК запропоновано точний метод, в якому спочатку знаходяться найкоротші ланцюги між усіма парами вершин вхідного графа, а потім в отриманій матриці ваг алгоритмом Літла знаходиться розв’язок СЗК. Кожне ребро знайденого маршруту комівояжера заміняється на відповідний найкоротший ланцюг. Запропоновано метод розв’язання ЗЗК, яка піддається розбиттю на блоки. Розв’язки ЗЗК в блоках об'єднуються в шуканий маршрут за поліноміальний час. Розроблено наближений метод ЗЗК. Запропоновано модифікацію методу Літла з поліпшеною процедурою обчислення нижньої межі, заснованої на алгоритмі розв’язання варіанту задачі про призначення. Отримана модифікація має кращу швидкодію та менші вимоги до оперативної пам’яті.
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.
Опис
Ключові слова
загальна задача комівояжера, симетрична задача комівояжера, гамільтонова задача комівояжера, наближений розв’язок, точний розв’язок, транспортні мережі, оптимізація, графи, General Traveling Salesman Problem, Symmetric TravelingSalesman Problem, Hamiltonian Traveling Salesman, Problem approximate solution, exact solution, transport networks, optimization, graph
Бібліографічний опис
Левченко А. Ю. Методи прискорювання обчислень в задачах оптимальної маршрутизації : автореф. ... канд. техн. наук : 01.05.02 – "Математичне моделювання та обчислювальні" / А. Ю. Левченко ; Харк. нац. ун-т радіоелектроніки. – Х., 2013. – 19 с.