Розробка та дослідження алгоритмів розв’язання задачі маршрутизації з поверненням товару

Abstract

Розглядаються існуючі точні та евристичні алгоритми розв’язку задачі маршрутизації з поверненням товару. Більш докладно розкривається задумка евристичного алгоритму табу пошуку. На його основі з певними евристиками знаходження початкового рішення, побудови сусідніх розв’язків та покращення знайденого розв’язку пропонується новий алгоритм. Приводяться результати роботи алгоритму на тестових даних, що були запропоновані авторами, які розглядали цю проблему раніше, та їх порівняння. Запропонований алгоритм може бути використаний для розв’язання подібних задач у системах реального часу, оскільки евристичний алгоритм навіть на великих наборах даних надає результат за прийнятний час.

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.