ALGORITHM FOR OPTIMIZATION OF ROAD TRANSPORTATION CARGO ROUTES BASED ON DYNAMIC MODIFICATION OF THE TWIG AND BOUNDARY METHOD

Abstract

In the article, based on the twig and boundary method, an algorithm for optimizing routes for road freight transportation is proposed based on the criterion of minimizing the transport work for their delivery, when the distances and volumes of delivery for each point and between points are given. In this study, the optimization criterion used is the minimization of the transport work of transporting goods from the corresponding transport and logistics center to the specified delivery points and the uniqueness of passing through their locations. The main idea of the method is that the branching of the set of possible freight transportation options into subsets is carried out according to an algorithm based on constructing estimates from above for the objective function on a certain set of solutions, which allows organizing a complete procedure for searching for possible route options for this problem. In accordance with the proposed approach, the set of all possible route options is divided into several non-intersecting subsets, from which the subset is determined on which the objective function of transport work reaches its smallest value.The paper shows that transport work is a complex indicator that takes into account the volume and distance of cargo transportation and is determined by their product. Unlike the classical application of the twig and boundary method when minimizing the length of the transportation route, when the elements of the transportation distance matrix are constant, the peculiarity of the proposed approach is that the entire set of possible cargo transportation options is described by the transport work matrix of delivery, the elements of which are calculated dynamically at each step of the algorithm, since their value depends on the volume of shipment that occurred at the previous stage. To increase the efficiency of searching for the optimal route, a modification of the twig and boundary method (TBM) was carried out for the case of dynamic determination of the elements of the transport work matrix of delivery. An algorithm for applying the proposed variant of the TBM method to construct an optimal road route by minimizing the transport work of transporting goods from a logistics center and a network of five delivery points is also presented. Analysis of the results of the calculations confirms the effectiveness of the proposed approach and shows that its application allows to reduce the computational complexity due to the use of improved strategies for cutting off irrelevant solutions and adaptive branching of possible cargo delivery options. The proposed approach allows to increase the accuracy of the calculation results and reduce the time of searching for the optimal route according to the criterion of minimizing the transport work of delivering cargo to the destination points. The results obtained can be used to optimize logistics processes and reduce the cost of transportation.