DETERMINATION OF THE OPTIMAL CIRCULAR ROUTE PASSING THROUGH THE GIVEN SET OF POINTS ON THE MAP
DOI:
https://doi.org/10.30837/2522-9818.2019.7.102Keywords:
transport logistics, route on the map, graph, Hamiltonian cycle, complexity, NP-completeness, Dijkstra's algorithm, reducibility, search scheme with returnsAbstract
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.
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.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2019 Vladymyr Prokopenkov, Yuryy Kozhyn, Oleh Malykh
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Our journal abides by the Creative Commons copyright rights and permissions for open access journals.
Authors who publish with this journal agree to the following terms:
Authors hold the copyright without restrictions and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License (CC BY-NC-SA 4.0) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
Authors are able to enter into separate, additional contractual arrangements for the non-commercial and non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
Authors are permitted and encouraged to post their published work online (e.g., in institutional repositories or on their website) as it can lead to productive exchanges, as well as earlier and greater citation of published work.
