Математичне моделювання та методи оптимізації замкнених маршрутів в задачах транспортного типу
Електронного архіву Харківського національного університету радіоелектроніки (Open Access Repository of KHNURE)
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Математичне моделювання та методи оптимізації замкнених маршрутів в задачах транспортного типу
|
|
| Creator |
Маций, О. Б.
|
|
| Subject |
гамільтонова задача комівояжера
задача про призначення 2-фактор задача про зважене паросполучення Hamiltonian Traveling Salesman Problem Assignment Problem 2-factor Weighted Matching Problem |
|
| Description |
Дисертаційна робота присвячена дослідженню математичних моделей оптимізації транспортних перевезень, розробленню нових і вдосконаленню відомих методів та алгоритмів комбінаторної оптимізації, які застосовуються в транспортній логістиці для побудови замкнених маршрутів. Розв'язання таких задач є важливим і набуває особливого значення в екстремальних умовах, коли виникає необхідність швидкої перебудови маршрутів руху при зміні зовнішніх умов. Для класу задач про паросполучення, які представлені задачею про призначення, задачею знаходження 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.
|
|
| Date |
2019-03-25T12:15:51Z
2019-03-25T12:15:51Z 2019 |
|
| Type |
Other
|
|
| Identifier |
Маций, О. Б. Математичне моделювання та методи оптимізації замкнених маршрутів в задачах транспортного типу : автореф. дис. ... канд. техн. наук : 01.05.02 "Математичне моделювання та обчислювальні методи" / О. Б. Маций ; М-во освіти і науки України, Харків. нац. ун-т радіоелектроніки. – Харків, 2019. – 20 с.
http://openarchive.nure.ua/handle/document/8232 |
|
| Language |
uk
|
|
| Publisher |
ХНУРЕ
|
|