Development of a genetic algorithm for solving a one-stage transport problem with fixed surcharges

Managing complex logistics processes of modern enterprises requires the development of adequate mathematical models that make it possible to calculate optimal transportation plans. One of these models is the transport problem with fixed surcharges, the feature of which is the nonlinearity of the goal function. This study is devoted to the development of a genetic algorithm for solving a transport problem with fixed surcharges. The basis of the study is the analysis of existing approaches to solving various modifications of transport problems. A feature of the proposed algorithm is the formation at each stage of chromosomes that satisfy the constraints of the problem, which allows reducing the solution time. The study presents in detail the steps of the algorithm for forming the initial population, crossing over and mutation, adapted to the conditions of the transport problem with fixed surcharges. The formation of the initial population is based on the approach of randomly selecting a “supplier-consumer” pair, which ensures its sufficient diversity. The crossing over operator is implemented by developing an algorithm based on dividing modulo two the sum of the genes of the parents and subsequent redistribution of the remainders from the division between the descendants. The chromosome mutation algorithm is based on changing the transportation plan for randomly selected rows and columns while maintaining the admissibility of the individual. To conduct a computational experiment, a software product was developed in Python, and a demonstration example of the calculation is given. The results of the calculations for a group of agricultural producers allowed us to draw conclusions about the practical significance of the proposed algorithm and identified the possibilities of its use for solving multi-stage transport problems that are relevant for large manufacturing and logistics companies.

1. Korbut A.A., Finkel'shtein Yu.Yu. Diskretnoe programmirovanie. Moscow: Nauka; 1969. 368 p. (In Russ.).

2. Dimov Yu., Lukyanov N. Genetic algorithm application for solving a multi-index transportation problem. Vestnik Irkutskogo gosudarstvennogo tekhnicheskogo universiteta = Proceedings of Irkutsk State Technical University. 2016;(7):73–79. (In Russ.). https://doi.org/10.21285/1814-3520-2016-7-73-79

3. Chernyshova G.D., Chigodaeva A.S. The tasks of transport-typed with discontinuous objective function. Vestnik Voronezhskogo gosudarstvennogo universiteta. Seriya: Sistemnyi analiz i informatsionnye tekhnologii = Proceedings of Voronezh State University. Series: Systems Analysis and Information Technologies. 2016;(2):65–69. (In Russ.).

4. Kumari A., Bose T., Gupta G., Bala R. Modified method for finding the solution of balanced transportation problems: a power rank method. Vychislitel'nye tekhnologii = Computational Technologies. 2024;29(2):62–68. https://doi.org/10.25743/ICT.2024.29.2.005

5. Volhonskaya E.E. The problem of optimal assignment of autonomous vehicles in production-logistics system. Vestnik Samarskogo gosudarstvennogo tekhnicheskogo universiteta. Seriya: Tekhnicheskie nauki = Vestnik of Samara State Technical University. Technical Sciences Series. 2023;31(2):20–30. (In Russ.). https://doi.org/10.14498/tech.2023.2.2

6. Gladkov L.A., Kureichik V.V., Kureichik V.M. Geneticheskie algoritmy. Moscow: Fizmatlit; 2010. 366 p. (In Russ.).

7. Virsanski E. Hands-On Genetic Algorithms with Python. Moscow: DMK Press; 2020. 286 p. (In Russ.).

8. Saimon D. Evolutionary Optimization Algorithms. Moscow: DMK Press; 2020. 940 p. (In Russ.).

9. Zaginailo M.V., Fatkhi V.A. Geneticheskii algoritm kak effektivnyi instrument evolyutsionnykh algoritmov. Innovatsii. Nauka. Obrazovanie. 2020;(22):513–518. (In Russ.).

10. Gusev P.Yu., Gusev K.Yu., Vahmin S.Yu. Application of genetic algorithms in optimization of planning decisions of industrial divisions of machine-building enterprises. Vestnik Voronezhskogo gosudarstvennogo tekhnicheskogo universiteta = Bulletin of Voronezh State Technical University. 2019;15(2):22–28. (In Russ.). https://doi.org/10.25987/VSTU.2019.15.2.003

11. Shitov A.E., Zhuravlev I.A. Investigation of the work of the genetic algorithm in the process of industrial and economic activity. Naukosfera. 2021;(12 1):236–240. (In Russ.). https://doi.org/10.5281/zenodo.5788763

12. Skvortsov S.V., Dyakov M.S. Acceleration of genetic algorithm for transportation problem solution by means of multithreading programming. Vestnik Ryazanskogo gosudarstvennogo radiotekhnicheskogo universiteta = Vestnik of Ryazan State Radio Engineering University. 2023;(84):99–107. (In Russ.). https://doi.org/10.21667/1995-4565-2023-84-99-107

13. Altiparmak F., Gen M., Lin L., Paksoy T. A genetic algorithm approach for multi-objective optimization of supply chain networks. Computers & Industrial Engineering. 2006;51(1):196–215. https://doi.org/10.1016/j.cie.2006.07.011

14. Khalili-Damghani K., Tavana M., Santos-Arteaga F.J., Ghanbarzad-Dashti M. A customized genetic algorithm for solving multi-period cross-dock truck scheduling problems. Measurement. 2017;108:101–118. https://doi.org/10.1016/j.measurement.2017.05.027