Modification of the potential method for reducing computational complexity in solving large-scale transportation problems

This paper investigates the problem of increasing computational complexity of the classical potential method when solving large-scale transportation problems of linear programming. A modification of the algorithm is proposed that allows reducing computation time without losing solution accuracy. The key element of novelty is a heuristic limitation on the number of recalculated potentials within each iteration, as well as a simplified rule for selecting the variable entering the basis. Based on the formal statement of the closed transportation problem, an analysis of the traditional algorithm was conducted, and the most resourceintensive operations were identified. The software implementation of the modified algorithm was performed in C programming language. To verify the effectiveness, a series of computational experiments was organized using synthetic data with dimensions from 10×10 to 200×200. Empirical results demonstrate a 15–25% reduction in solution time for problems with dimensions exceeding 100×100. At the same time, the deviation of the obtained plan's cost from the reference solution does not exceed 0,01%. The practical significance is confirmed through modeling medication distribution in the Samara region. The scientific novelty consists in developing a heuristic that adapts the exact potential method to work with large data arrays. The results can be applied to improve information systems for managing logistics chains.

1. Balashov V.G. Linear programming and transportation problems. St. Petersburg : Piter, 2018. 352 p.

2. Goncharov E.B., Plotnikov A.V. Modern problems of modeling transport and logistics systems // Logistics and Supply Chain Management. 2022. No. 3 (104). Pp. 15–27.

3. Lotov A.V., Pospelova I.I. Heuristic methods for solving transportation problems in regional logistics. // Vestnik of Samara State University of Economics. 2022. No. 4 (194). Pp. 78–89.

4. Zhdanov S.P. Optimization Methods in Economics. Samara : Samara University, 2021. 264 p.

5. Orlin J.B. A polynomial time primal network simplex algorithm for minimum cost flows // Mathematical Programming. 2019. Vol. 154 (1-2). Pp. 47–48.

6. Gavrilov L.P., Gasanov E.E. Parallel algorithms for solving large-scale linear programming problems // Programming and Computer Software. 2022. No. 4. Pp. 45–58.

7. Kantorovich L.V. Mathematical methods of organization and production planning. Moscow : Nauka, 2019. 368 p.

8. Taha H.A. Introduction to Operations Research. 9th ed. Moscow : Williams, 2021. 912 p.

9. Strongin R.G., Barkalov K.A. Parallel algorithms for global optimization of large-scale problems // Computational Methods and Programming. 2020. Vol. 21, No. 3. Pp. 312–325.

10. Alekseev O.G. Computational complexity and algorithm optimization. Moscow : MCCME, 2019. 288 p.

11. Emelichev V.A., Kravtsov M.K. Algorithms for optimizing large-scale transportation flows // Software Products and Systems. 2021. Vol. 34, No. 2. Pp. 245–256. doi:10.15827/0236-235X.134.245-256.

12. Kratica J., Tošić D., Filipović V. An efficient implementation of the transportation simplex algorithm // Computational Optimization and Applications. 2021. Vol. 48. Pp. 227–245.