DETERMINATION OF THE OPTIMAL CIRCULAR ROUTE PASSING THROUGH THE GIVEN SET OF POINTS ON THE MAP

Keywords: transport logistics, route on the map, graph, Hamiltonian cycle, complexity, NP-completeness, Dijkstra's algorithm, reducibility, search scheme with returns

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.

Downloads

Download data is not yet available.

Author Biographies

Vladymyr Prokopenkov, National Technical University "Kharkiv Polytechnic Institute"
Senior Teacher at the Department of System Analysis and Information-Analytical Technologies
Yuryy Kozhyn, National Technical University "Kharkiv Polytechnic Institute"
Senior Teacher at the Department of System Analysis and Information-Analytical Technologies
Oleh Malykh, National Technical University "Kharkiv Polytechnic Institute"
PhD (Engineering Sciences), Associate Professor, Associate Professor at the Department of System Analysis and Information-Analytical Technologies

References

Fёdorov, V. A. (2016), "Analysis of the advantages and disadvantages of the traditional method of handling and delivery of goods in transport logistics" ["Analyz prevoskhodstv y nedostatkov tradytsyonnoho sposoba obrabotky y dostavky hruza v transportnoy lohystyke"], Symbol of Science, No. 11 (1), P. 217–218.

Iastremska, O. (2018), "Logistics at an enterprise: the peculiarities of procurement activities" Innovative Technologies and Scientific Solutions for Industries, No. 3 (5), P. 141–148. DOI: https://doi.org/10.30837/2522-9818.2018.5.141.

Ustenko, M. O. "The main problems of transport logistics" ["Osnovni problemy transportnoyi lohistyky"], available at : http://uran.donntu.org/~masters/2012/iii/dyadyk/library/article3.htm (last accessed 08.02.2019).

Horyaynov, A. N. (2006), "Types of routes of vehicles in the transport of goods in the logistics system" ["Vydy marshrutov avtotransportnykh sredstv pry perevozke hruzov v lohystycheskoy systeme"], Utilities of cities, No. 67, P. 304–309.

"Problems of transport logistics: Practical experience of Ukrainian enterprises" ["Problemy transportnoy lohystyky: Praktycheskyy opyt ukraynskykh predpryyatyy"], available at : http://www.ukrlogist.com/node/452 (last accessed 08.02.2019).

Nykolyn, V. Y. (2004), Freight transport : monograph [Hruzovye avtomobyl'nye perevozky : monohrafyya], Varyant, Omsk, 480 p.

Shamys, V. A. "Some aspects of choosing the optimal shipping route" ["Nekotorye aspekty vybora optymal'noho marshruta perevozok"], available at : https://novainfo.ru/article/5296 (last accessed 08.02.2019).

Serheev, V. Y. (2001), Logistics in business [Lohystyka v byznese], Ynfra-M, Moscow, 608 p.

Anderson, Dzh. (2003), Discrete mathematics and combinatorics [Dyskretnaya matematyka y kombynatoryka], Vyl'yams, Moscow, 214 p.

Vershik, A. M. (2013), "Long history of the Monge-Kantorovich transportation problem", Math. Intelligencer, No. 4 (35), P. 1–9. DOI: https://doi.org/10.1007/s00283-013-9380-x.

Kantorovych, L. V. (2011), Selected work. Mathematical and economic work [Yzbrannye trudy. Matematyko-ekonomycheskye raboty], Nauka, Novosybyrsk, 760 p.

"Transport task. Mathematical model" ["Transportnaya zadacha. Matematycheskaya model'"], available at : http://www.grandars.ru/student/vysshaya-matematika/model-transportnoy-zadachi.html (last accessed 08.02.2019).

Rohatkyn, A. Yu., Zakharkyna, M. V. (2016), "Optimization of motor routes: heuristic algorithms and logistics management practices" ["Optymyzatsyya avtotransportnykh marshrutov: evrystycheskye alhorytmy y praktyka lohystycheskoho menedzhmenta"], Bulletin of the Moscow International Academy, No. 1, P. 124–135.

Davendra, D. (2010), Traveling Salesman Problem. Theory and Applications, IntechOpen, London, 336 p. DOI: https://doi.org/10.5772/547.

Hery, M., Dzhonson, D. (1982), Computational machines and difficult tasks [Vychyslytel'nye mashyny y trudnoreshaemye zadachy], Myr, Moscow, 419 p.

"Littleton's algorithm is a method for solving a salesman's problem" ["Alhorytm Lyttla – metod reshenyya zadachy kommyvoyazhera"], available at : https://intellect.ml/algoritm-littla-metod-resheniya-zadachi-kommivoyazhera-7734 (last accessed 08.02.2019).

Clarke, G., Wright, J. (1964), "Scheduling of Vehicles from a central depot to a number of delivery", Operations Research, No. 4 (12), Р. 568–581. DOI: https://doi.org/10.1287/opre.12.4.568.

Bellman, R. (1958), "On a routing problem", Quarterly of Applied Mathematics, No. 1 (16), P. 87–90. DOI: https://doi.org/10.1090/qam/102435.

Dijkstra, E. W. (1959), "A note on two problems in connexion with graphs", Numerische Mathematik, No. 1 (1), P. 269–271. DOI: https://doi.org/10.1007/bf01386390.

Prokopenkov, V. F. (2014), "Finding a closed path in a graph passing through a given set of vertices, which is an eigenvalue of vertices of a graph" ["Poysk zamknutoho puty v hrafe, prokhodyashcheho cherez zadannoe mnozhestvo vershyn, yavlyayushcheesya sobstvennym podmnozhestvom vershyn hrafa"], International Scientific Conference MicroCAD 2014: Section No. 1 – Information and Management Systems, P. 18.

Wirth, N. (1984), "Data Structures and Algorithms", Scientific American, No. 3 (251), P. 60–69. DOI: https://doi.org/10.1038/scientificamerican0984-60.

Ore, O. (2009), The theory of graphs [Teoryya hrafov], URSS, Moscow, 354 p.


Abstract views: 17
PDF Downloads: 17
Published
2019-04-02
How to Cite
Prokopenkov, V., Kozhyn, Y. and Malykh, O. (2019) “DETERMINATION OF THE OPTIMAL CIRCULAR ROUTE PASSING THROUGH THE GIVEN SET OF POINTS ON THE MAP”, INNOVATIVE TECHNOLOGIES AND SCIENTIFIC SOLUTIONS FOR INDUSTRIES, (1 (7), pp. 102-112. doi: 10.30837/2522-9818.2019.7.102.