A new algorithm for finding optimal solutions of transportation problems

Abstract

This paper presents a computational refinement of classical optimality procedures for solving Transportation Problems (TPs). Rather than altering the underlying linear programming formulation, the method introduces a structured loop-enumeration strategy within the transportation simplex framework. Specifically, admissible improvement loops are generated from the current basis (occupied cells) and constrained to include exactly one nonbasic (unoccupied) cell, reducing redundant loop exploration. A formal analysis establishes feasibility preservation, strict descent when an improving loop exists, finite termination, and equivalence with classical optimality conditions via reduced costs. Computational experiments on benchmark problems from literature compare the new method with the Stepping–Stone and MODI methods. To evaluate computational efficiency, all computational experiments were conducted using MATLAB R2022b on a computer equipped with an Intel Core i7 processor (3.20 GHz), 16 GB RAM, running Windows 10 (64-bit), Execution time was measured using MATLAB’s built-in timing functions. Each method was run five times per dataset, and the average CPU execution time (in seconds) was recorded to ensure consistency. Results show that the new approach yields optimal solutions identical to classical methods and achieves comparable or improved performance on average runtime, with clearer benefits on medium-to-large instances where loop redundancy is more pronounced. For small instances, differences are minor and may vary due to implementation overhead. The findings position the method as a practical, verifiable computational refinement for efficient loop selection in transportation simplex implementations.