New Loop-Tracing Algorithm Speeds Up Optimal Solutions to Transportation Problems

Researchers at the heart of operations research have long relied on two-phase procedures to solve transportation problems, the linear programming workhorses behind logistics, supply chain management, production planning and network optimization. A newly published study in Discover Analytics introduces a computational refinement of the second, optimality phase, one that leaves the underlying mathematics untouched but changes how improving routes through the solution table are found. The result, according to the authors, is an algorithm that reaches exactly the same optimal solutions as classical methods while running faster on medium-to-large instances, where redundant searching has historically been the bottleneck.

The transportation problem asks how to ship goods from a set of supply sources to a set of demand destinations at minimum total cost, subject to supply and demand constraints. Because of its special linear programming structure, the problem has been studied intensively since the foundational work of Hitchcock and Dantzig, and a family of efficient solution procedures has grown up around it. Classical approaches typically begin by constructing an Initial Basic Feasible Solution using heuristics such as the Northwest Corner Method, the Least Cost Method or Vogel’s Approximation Method. That initial solution is then driven to optimality by procedures such as the Stepping-Stone Method of Charnes and Cooper or the Modified Distribution Method, known as MODI.

These classical optimality procedures are theoretically sound and guarantee convergence, but the new study argues that they carry a practical inefficiency. Loop tracing, the mechanism by which the algorithm searches for cost-reducing adjustments, traditionally starts from unoccupied cells in the transportation tableau. In large-scale or degenerate problems, this can generate many admissible loops that are redundant or structurally similar, forcing the solver to evaluate equivalent or non-improving paths repeatedly. Existing research has largely focused on better initial solutions or hybrid heuristics, leaving the loop-construction burden in the optimality phase comparatively unexamined.

The proposed method, developed by Douglas Kwasi Boah, Suleman Abudu Fiele and Christian John Etwire, does not alter the linear programming formulation or the theoretical guarantees of the transportation simplex framework. Instead, it imposes a structured restriction on loop enumeration: admissible improvement loops are generated from the occupied cells of the current basis, and each loop must pass through exactly one nonbasic, or unoccupied, cell. Right-angle turns are permitted only at occupied cells, and the search stops once every unoccupied cell has been considered. This constraint-driven rule directly reduces the number of candidate loops evaluated at each iteration while, the authors show, preserving feasibility, convergence and optimality.

The mechanics follow the familiar simplex logic. For any traced loop, corner cells are marked alternately with plus and minus signs, beginning with a plus at the loop’s unique unoccupied cell. The loop’s net cost change is computed as the sum of costs at plus corners minus the sum of costs at minus corners. If this quantity is negative, an improvement is possible: the step size is set to the smallest allocation among the minus positions, allocations are updated accordingly, and the unoccupied cell enters the basis while feasibility is maintained. If several loops through an occupied cell show negative net cost, the algorithm selects the loop with the most negative value. Iteration continues until no admissible loop yields a negative net cost change.

The paper backs this procedure with formal proofs. Proposition 1 establishes that the loop update preserves feasibility, because each affected row and column contains either zero or exactly two loop corners, one plus and one minus, so row and column sums change by a net zero and nonnegativity holds since the step size never exceeds any decreased allocation. Proposition 2 proves strict descent: when a loop’s net cost change is negative, the objective value strictly decreases by the step size multiplied by that negative quantity. Proposition 3 establishes finite termination, noting that the transportation problem has only finitely many basic feasible solutions and that each improving iteration moves to a new one with a strictly lower cost, so no basis can be revisited. Proposition 4 connects the termination condition to classical reduced costs, showing that when no admissible loop has negative net cost, all reduced costs are nonnegative, which is necessary and sufficient for optimality.

Degeneracy, a well-known complication in transportation simplex implementations, is handled explicitly. Degeneracy arises when the number of positive basic allocations falls below the required count of rows plus columns minus one. The authors show that zero-valued basic variables can be introduced to complete a spanning-tree basis without changing the objective value, and they prove that under this completed basis, adding any nonbasic cell creates a unique fundamental cycle, hence a unique admissible loop containing that cell as its only nonbasic corner. A further proposition demonstrates that degeneracy does not cause stalling under the loop update: the step size guarantees that at least one basic variable on a minus position drops to zero, so a valid pivot exchange always occurs.

To test the method, the authors first demonstrated it on a benchmark transportation tableau from a cement company dataset drawn from the literature. Starting from a nondegenerate initial basic feasible solution with an initial transportation cost of 2,785 in unit cost terms, the algorithm traced admissible loops and identified a single negative net cost of minus 3 associated with an unoccupied cell of unit cost 22. Applying an adjustment of 10 along the identified loop and re-evaluating all loop net costs yielded only nonnegative values, terminating the search. The final allocations produced an optimal cost of 2,755, illustrating the strict cost reduction the theory predicts.

The computational comparison then covered thirty benchmark problems from the literature and four problems constructed by the authors, with the new algorithm pitted against the Stepping-Stone and MODI methods on both solution quality and execution time. All experiments were run in MATLAB R2022b on a computer with an Intel Core i7 processor at 3.20 GHz, 16 GB of RAM and Windows 10 64-bit, with timing performed using MATLAB’s built-in timing functions. Each method was run five times per dataset and average CPU execution times in seconds were recorded. Across the benchmarks, the new approach yielded optimal solutions identical to those of the classical methods and achieved comparable or improved average runtime, with clearer benefits on medium-to-large instances where loop redundancy is more pronounced. For small instances, the differences were minor and could vary due to implementation overhead.

The authors are careful about the limits of the contribution. Because the underlying linear programming structure is unchanged, the method does not reduce the worst-case complexity of the transportation problem, and the study does not aim to compete with general-purpose network optimization solvers such as the Network Simplex or interior-point methods, which address broader problem classes with fundamentally different paradigms. What the refinement offers instead is a transparent, verifiable improvement in the efficiency of the optimality phase, achieved by systematically shrinking the loop search space. The authors suggest that future work could extend the approach to related network optimization problems and integrate it with advanced initialization techniques, positioning the method as a practical upgrade for transportation simplex implementations in applied and educational settings.

Subject of Research: A computational refinement of loop tracing in transportation simplex methods that preserves optimality guarantees while reducing redundant loop enumeration.

Article Title: A new algorithm for finding optimal solutions of transportation problems

Article References: Boah, D. K., Fiele, S. A., & Etwire, C. J. (2026). A new algorithm for finding optimal solutions of transportation problems. Discover Analytics, 4(1), Article 30. https://doi.org/10.1007/s44257-026-00074-5

Image Credits: AI Generated

DOI: 10.1007/s44257-026-00074-5

Keywords: transportation problem, operations research, linear programming, optimization algorithm, transportation simplex, Stepping-Stone method, MODI, loop tracing, degeneracy, computational efficiency, benchmark experiments, MATLAB