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

Маций, О. Б.

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

dc.contributor.author	Маций, О. Б.
dc.date.accessioned	2019-03-25T12:15:51Z
dc.date.available	2019-03-25T12:15:51Z
dc.date.issued	2019
dc.description.abstract	Дисертаційна робота присвячена дослідженню математичних моделей оптимізації транспортних перевезень, розробленню нових і вдосконаленню відомих методів та алгоритмів комбінаторної оптимізації, які застосовуються в транспортній логістиці для побудови замкнених маршрутів. Розв'язання таких задач є важливим і набуває особливого значення в екстремальних умовах, коли виникає необхідність швидкої перебудови маршрутів руху при зміні зовнішніх умов. Для класу задач про паросполучення, які представлені задачею про призначення, задачею знаходження 2-фактора мінімальної ваги і задачею про зважене паросполучення, запропоновано методи розв’язання, розроблені за єдиною схемою, яка знижує трудомісткість відомих методів. Запропоновано модифікацію методу Літтла для знаходження оптимального маршруту в транспортній мережі. Для класу задач про паросполучення, наведених задачею про призначення, задачею знаходження 2-фактора мінімальної ваги і задачею про зважене паросполучення, запропоновано методи розв’язання, розроблені за єдиною схемою, яка знижує трудомісткість відомих методів. Особливість модифікації полягає в тому, що вперше оцінка знизу шуканого значення цільового функціонала визначається в результаті розв’язання задачі знаходження 2-фактора мінімальної ваги. Застосування вибраної оцінки обмежує згори дерево перебору та істотно скорочує час пошуку розв’язку задач транспортного типу. In the thesis describes a modified method for solving the Hamiltonian Traveling Salesman Problem, which is a Traveling Salesman Problem. The method is represented by an upgraded version of the classical Little’s algorithm, where solution of the 2-factor problem is used to get increasing accuracy of the lower bound estimates of the cost for cycles. A 2-factor of an arbitrary graph is called the union of not overlapping nodes of cycles. The 2-factor problem lies in the fact that, it is required to find in a weighted graph a 2-factor, which would have the smallest sum of its edges weights. Subject of the study was working time of known methods for solving assignment problem (the method of potentials and the Hungarian method) and the recurrent method, proposed in this thesis work. The working time of the 2-factor method for solving problem of obtaining minimum weight of the 2-factor was under study. The same parameters and input data were used, as it was in experiment for studying working time of the methods for solving the assignment problem. A time of solving a Travel Salesman Problem by updated version of the Little’s method was under study, where various relaxations were used to obtain estimates of lower bound for the cost of traveling salesman routes. A comparison of the methods for solving the assignment problem proved that the recursive method for solving the assignment problem, represented in the Second section of this thesis work, showed the best characteristics. The results of computational experiment show that the shortest time for solving a Traveling Salesman Problem demonstrates the updated version of the Little’s method, using the 2-factor relaxation. The second result shows usage of updated version for solution of the assignment problem by recursive method.	uk_UA
dc.identifier.citation	Маций О. Б. Математичне моделювання та методи оптимізації замкнених маршрутів в задачах транспортного типу : автореф. дис. ... канд. техн. наук : 01.05.02 "Математичне моделювання та обчислювальні методи" / О. Б. Маций ; М-во освіти і науки України, Харків. нац. ун-т радіоелектроніки. – Харків, 2019. – 20 с.	uk_UA
dc.identifier.uri	http://openarchive.nure.ua/handle/document/8232
dc.language.iso	uk	uk_UA
dc.publisher	ХНУРЕ	uk_UA
dc.subject	гамільтонова задача комівояжера	uk_UA
dc.subject	задача про призначення	uk_UA
dc.subject	2-фактор	uk_UA
dc.subject	задача про зважене паросполучення	uk_UA
dc.subject	Hamiltonian Traveling Salesman Problem	uk_UA
dc.subject	Assignment Problem	uk_UA
dc.subject	2-factor	uk_UA
dc.subject	Weighted Matching Problem	uk_UA
dc.title	Математичне моделювання та методи оптимізації замкнених маршрутів в задачах транспортного типу	uk_UA
dc.type	Other	uk_UA
dspace.entity.type	Publication