Modification of the potential method for reducing computational complexity in solving large-scale transportation problems
TL;DR
A modification of the algorithm is proposed that allows reducing computation time without losing solution accuracy, and a heuristic limitation on the number of recalculated potentials within each iteration is introduced.
Abstract
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.