Определение оптимального кольцевого маршрута, проходящего через заданное множество пунктов на карте

Abstract

Предметом исследований являются методы и информационные технологии транспортной логистики. Цель – снижение затрат и сокращение времени на доставку товаров автомобильным транспортом за счет разработки и внедрения эффективных методов и алгоритмов поиска оптимального маршрута развоза товаров. В статье рассматривается задача поиска оптимального кольцевого маршрута развоза товаров со склада, проходящего через заданное множество пунктов на карте. Для решения задачи используются методы и алгоритмы дискретной математики. Получены следующие результаты. Выполнен анализ проблемы и существующих методов дискретной математики для ее решения, определены недостатки этих методов. Предложен метод решения задачи, устраняющий эти недостатки. Разработан эвристический алгоритм решения задачи, реализующий предложенный метод решения. Решение рассматриваемой задачи сводится к задаче поиска гамильтонова цикла на новом графе меньшей размерности. Новый граф строится из начального графа, описывающего карту, и состоит из вершин заданного множества пунктов на карте, через которые должен пройти маршрут. Каждая дуга в новом графе соединяет пару вершин, если в начальном графе существует путь между этими вершинами. Дуга взвешивается числом, которое определяет минимальное расстояние между вершинами в начальном графе, которые она соединяет. Для построения графа используется алгоритм Дейкстры. Выводы: предложенный метод решения рассмотренной задачи выполняет ее сводимость к классической задаче дискретной математики поиска гамильтонова цикла на графе. Тестирование разработанной программы показало работоспособность предложенного метода и алгоритма решения задачи. Разработанный метод позволяет понизить размерность решаемой задачи, поскольку решение ищется на новом графе меньшей размерности в отличие от графа, описывающего исходную карту. Фактор понижения размерности значительно снижает затраты на поиск решения и повышает шансы найти оптимальный маршрут развоза товаров.The subject of research is the methods and information technologies of transport logistics. The goal is to reduce costs and time for delivery of goods by road through the development and implementation of effective methods and algorithms for finding the optimal route for delivering goods. The article deals with the task of finding the optimal ring route for the delivery of goods from the warehouse, passing through a given set of points on the map. Methods and algorithms of discrete mathematics are used to solve the problem. The following results were obtained. The analysis of the problem and the existing methods of discrete mathematics for its solution were carried out. The disadvantages of these methods are determined. A heuristic algorithm for solving the problem that implements the proposed solution method has been developed. The solution of the considered problem is reduced to the problem of finding a Hamiltonian cycle on a new graph of smaller dimension. The new graph is constructed from the initial graph describing the map, and consists of the vertices of a given set of points on the map, through which the route must pass. Each arc in a new graph connects a pair of vertices if there is a path between those vertices in the initial graph. The arc is weighted by a number that determines the minimum distance between the vertices in the initial graph it connects. Dijkstra's algorithm is used to construct the graph. Conclusions: the proposed method for solving the considered problem performs its reducibility to the classical problem of discrete mathematics of search for a Hamiltonian cycle on a graph. Testing of the developed program showed the efficiency of the proposed method and algorithm for solving the problem. The developed method makes it possible to reduce the dimension of the problem to be solved, since the solution is sought on a new graph of smaller dimension in contrast to the graph describing the original map. The factor of dimension reduction significantly reduces the cost of finding a solution and increases the chances of finding the best route for the delivery of goods.