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

dc.contributor.authorМаций, О. Б.
dc.date.accessioned2019-03-25T12:15:51Z
dc.date.available2019-03-25T12:15:51Z
dc.date.issued2019
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.urihttp://openarchive.nure.ua/handle/document/8232
dc.language.isoukuk_UA
dc.publisherХНУРЕuk_UA
dc.subjectгамільтонова задача комівояжераuk_UA
dc.subjectзадача про призначенняuk_UA
dc.subject2-факторuk_UA
dc.subjectзадача про зважене паросполученняuk_UA
dc.subjectHamiltonian Traveling Salesman Problemuk_UA
dc.subjectAssignment Problemuk_UA
dc.subject2-factoruk_UA
dc.subjectWeighted Matching Problemuk_UA
dc.titleМатематичне моделювання та методи оптимізації замкнених маршрутів в задачах транспортного типуuk_UA
dc.typeOtheruk_UA
dspace.entity.typePublication

Файли

Оригінальний пакет
Зараз показано 1 - 1 з 1
Завантаження...
Зображення мініатюри
Назва:
Matsiy_avtoref.pdf
Розмір:
825.16 KB
Формат:
Adobe Portable Document Format
Ліцензійний пакет
Зараз показано 1 - 1 з 1
Немає доступних мініатюр
Назва:
license.txt
Розмір:
9.42 KB
Формат:
Item-specific license agreed upon to submission
Опис:

Колекції