Розробка та дослідження алгоритмів розв’язання задачі маршрутизації з поверненням товару
Дата
2016
ORCID
DOI
Науковий ступінь
Рівень дисертації
Шифр та назва спеціальності
Рада захисту
Установа захисту
Науковий керівник
Члени комітету
Назва журналу
Номер ISSN
Назва тому
Видавець
НТУ "ХПІ"
Анотація
Розглядаються існуючі точні та евристичні алгоритми розв’язку задачі маршрутизації з поверненням товару. Більш докладно розкривається задумка евристичного алгоритму табу пошуку. На його основі з певними евристиками знаходження початкового рішення, побудови сусідніх розв’язків та покращення знайденого розв’язку пропонується новий алгоритм. Приводяться результати роботи алгоритму на тестових даних, що були запропоновані авторами, які розглядали цю проблему раніше, та їх порівняння. Запропонований алгоритм може бути використаний для розв’язання подібних задач у системах реального часу, оскільки евристичний алгоритм навіть на великих наборах даних надає результат за прийнятний час.
The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?". It generalizes the well-known travelling salesman problem (TSP). Determining the optimal solution is an NP-hard problem in combinatorial optimization, so the size of problems that can be solved optimally is limited. The commercial solvers therefore tend to use heuristics due to the size and frequency of real world VRPs they need to solve. We consider the existing exact and heuristic algorithms for solving vehicle routing problem with backhauls. Reveal the idea of the tabu search heuristic algorithm. Based on certain heuristics find the initial solution, the construction of the neighboring solutions and improve the obtained solution, proposes a new algorithm. We present the results of the algorithm on the test data, proposed by the authors, who considered this issue before, and present the results of a comparison of these algorithms. The proposed algorithm can be used to solve such problems in real-time systems, as a heuristic algorithm, even on large data sets provides the result in an acceptable time.
The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?". It generalizes the well-known travelling salesman problem (TSP). Determining the optimal solution is an NP-hard problem in combinatorial optimization, so the size of problems that can be solved optimally is limited. The commercial solvers therefore tend to use heuristics due to the size and frequency of real world VRPs they need to solve. We consider the existing exact and heuristic algorithms for solving vehicle routing problem with backhauls. Reveal the idea of the tabu search heuristic algorithm. Based on certain heuristics find the initial solution, the construction of the neighboring solutions and improve the obtained solution, proposes a new algorithm. We present the results of the algorithm on the test data, proposed by the authors, who considered this issue before, and present the results of a comparison of these algorithms. The proposed algorithm can be used to solve such problems in real-time systems, as a heuristic algorithm, even on large data sets provides the result in an acceptable time.
Опис
Ключові слова
задача маршрутизації, повернення товару, табу пошук, евристичні алгоритми, евристики покращення розв’язку, vehicle routing problem, backhauls, tabu search, heuristics
Бібліографічний опис
Розробка та дослідження алгоритмів розв’язання задачі маршрутизації з поверненням товару / К. А. Кузнєцов [та ін.] // Вісник Нац. техн. ун-ту "ХПІ" : зб. наук. пр. Сер. : Механіко-технологічні системи та комплекси. – Харків : НТУ "ХПІ", 2016. – № 7 (1179). – С. 20-25.