Genetic algorithm of distribution of delivery routes
Abstract
Information technologies have become an integral part of the life of modern society. That is why they are actively used to solve the complicated tasks related to optimisation of activities in economy, management, finance, social and other spheres. Logistics are not an exception, and information technologies are used to automate delivery processes, which contributes to the efficient and cost-effective operation of enterprises. This is possible provided that the supplier's resources are managed rationally and provided with an efficient way of distributing delivery routes. This explains the relevance of this work. The purpose of the article is to develop a genetic algorithm to determine the optimal delivery plan, as well as to compare its work with some well-known delivery optimization methods. The object of study is the delivery routes. The subject of the study is the distribution route distribution algorithm. The article proposes a genetic algorithm for solving the traveling salesman problem with several routes. The statement of the problem of determining the optimal delivery plan is presented, the possibility of using a genetic algorithm for the task is considered, the type of the genetic algorithm is described and a block diagram of its implementation is presented. A software implementation of the genetic algorithm and other methods of distributing delivery routes has been prepared, which is carried out using the C++ programming language and the Qt framework. For the algorithms to work, you need to generate an order, vehicles and depots, as well as enter the necessary parameters. The results of the operation of the algorithm and other selected methods using the program were obtained, which made it possible to evaluate their effectiveness on the basis of experimental data for given parameters and to compare their work. The advantage of the proposed genetic algorithm over the well-known ant algorithm in randomly generated tests has been experimentally established. This indicates the applied value of the results obtained and the possibility of applying the algorithm in real conditions of distribution of supply routes.
Downloads
References
Dantzig, G. B., Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6 (1), 80-91. doi: https://doi.org/10.1287/mnsc.6.1.80.
Stodola, P., Mazal, J. (2015). Tactical models based on a multi-depot vehicle routing problem using the ant colony optimization algorithm. International journal of mathematical models and methods in applied sciences, 9, 330-337.
Chitty, D., Wanner, E., Parmar, R., & Lewis, P. (2019). Applying Partial-ACO to Large-scale Vehicle Fleet Optimisation. arXiv. Retrieved from https://arxiv.org/abs/1904.07636.
Diestel, R. (2005). Graph Theory. NY: Springer-Verlag.
Cormen, T., Leiserson, C., Rivest, R., & Stein, C. (2009). Introduction to Algorithms (2nd ed.). MIT Press.
Knuth, D. (1974). Postscript about NP-hard problems. ACM SIGACT News, 6(2), 15-16. doi: https://doi.org/10.1145/1008304.1008305.
Nakonechny, S.I., Savina, S.S. (2003). Mathematical programming: textbook. Kyiv: KNEU. (іn Ukrainian)
Eiben, A. E., Raué, P., Ruttkay, Z. (1994). Genetic algorithms with multi-parent recombination. PPSN III: Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature Jerusalem, October 9–14, 2010, Israel, 78-87.
Mitchell, M. (1995). Genetic algorithms: an overview. Complexity, 1(1), 31-39. doi: https://doi.org/10.1002/cplx.6130010108.
Mitchell, M. (1996). An introduction to genetic algorithms. Cambridge, MA: MIT Press.
Koza, J. R. (1994). Introduction to genetic programming. In K. E. Kinnear (Ed.), Advances in Genetic Programming. Cambridge: MIT Press, 21-41.
Steeb, W.-H. (2001). The Nonlinear Workbook: Chaos, Fractals, Cellular Automata, Neural Networks, Genetic Algorithms, Fuzzy Logic: with C++, Java, SymbolicC++ and Reduce Programs. Singapore: World Scientific.
