A Unified Mathematical Framework for NWC, MODI, and Stepping Stone as Foundational Models in Optimal Transport Theory
DOI:
https://doi.org/10.35335/cit.Vol17.2025.1393.pp183-195Keywords:
Optimal Transport, Transportation Problem, MODI Method, Stepping Stone Algorithm, Transportation PolytopeAbstract
This research introduces a unified mathematical framework connecting three classical transportation problem methods Northwest Corner Rule (NWC), Modified Distribution Method (MODI), and the Stepping Stone Method to the modern theory of Optimal Transport (OT). Despite their long-standing use in operations research, these classical algorithms have traditionally been treated as heuristic procedures without a formal theoretical link to the rigorous Monge Kantorovich formulation. This study demonstrates that each method corresponds directly to fundamental geometric and dual structures of the transportation polytope: NWC generates an initial extreme-point solution, MODI computes dual potentials analogous to Kantorovich potentials, and Stepping Stone identifies improvement cycles consistent with movements along polytope edges. Using formal definitions, algebraic mappings, and geometric interpretation, the research establishes a coherent connection between classical OR algorithms and OT duality theory. The results show that these methods are not isolated heuristics, but structured approximations of optimal transport processes. The unified framework improves theoretical understanding, simplifies instructional explanations, and offers methodological insights that may support future algorithmic enhancements. Limitations include scalability challenges and reduced applicability to complex continuous OT settings. Overall, this research contributes a foundational unification that bridges classical transportation algorithms with contemporary optimal transport theory, advancing both theoretical rigor and practical comprehension.
Downloads
References
O. Sun and N. Fan, “A review on optimization methods for biomass supply chain: models and algorithms, sustainable issues, and challenges and opportunities,” Process Integr. Optim. Sustain., vol. 4, no. 3, pp. 203–226, 2020.
D. A. Edwards, “A simple proof in Monge–Kantorovich duality theory,” Stud. Math., vol. 200, pp. 67–77, 2010.
U. Rude, K. Willcox, L. C. McInnes, and H. De Sterck, “Research and education in computational science and engineering,” Siam Rev., vol. 60, no. 3, pp. 707–754, 2018.
R. P. Sen, Operations Research: Algorithms And Applications: Algorithms and Applications. PHI Learning Pvt. Ltd., 2010.
P. Saraev, S. Blyumin, A. Galkin, and A. Sysoev, “Mathematical remodeling concept in simulation of complicated variable structure transportation systems,” Transp. Res. Procedia, vol. 45, pp. 475–482, 2020.
M. Bernot, V. Caselles, and J.-M. Morel, Optimal transportation networks: models and theory. Springer, 2009.
A. Makkuva, A. Taghvaei, S. Oh, and J. Lee, “Optimal transport mapping via input convex neural networks,” in International Conference on Machine Learning, PMLR, 2020, pp. 6672–6681.
D. J. Cirilo-Lombardo, “Algebraic structures, physics and geometry from a unified field theoretical framework,” Int. J. Theor. Phys., vol. 54, no. 10, pp. 3713–3727, 2015.
X. Lu, D. Clements-Croome, and M. Viljanen, “Integration of chaos theory and mathematical models in building simulation: part II: conceptual frameworks,” Autom. Constr., vol. 19, no. 4, pp. 452–457, 2010.
E. MESSELE, “BASIC SOLUTION OF TRANSPORTATION PROBLEM USING THE CONCEPT OF BEST CANDIDATE METHOD AND ITS COMPARISON WITH OTHER METHODS,” 2016.
F. T. Vitor, Two dimensional search algorithms for linear programming. Kansas State University, 2019.
V. L. Levin, “Smooth feasible solutions to a dual Monge–Kantorovich problem with applications to best approximation and utility theory in mathematical economics,” in Advances in Mathematical Economics, Springer, 2009, pp. 97–127.
N. V. C. Gudapati, “Duality and a Closer Look at Implementation of Linear Optimization Algorithms.” Lehigh University, 2017.
S. Stidham Jr, “Applied probability in operations research: a retrospective,” Univ. North Carolina, Dep. Oper. Res. Chapel Hill, NC, 2001.
N. Komodakis and J.-C. Pesquet, “Playing with duality: An overview of recent primal? dual approaches for solving large-scale optimization problems,” IEEE Signal Process. Mag., vol. 32, no. 6, pp. 31–54, 2015.
K. Deb, K. Miettinen, and S. Chaudhuri, “Toward an estimation of nadir objective vector using a hybrid of evolutionary and local search approaches,” IEEE Trans. Evol. Comput., vol. 14, no. 6, pp. 821–841, 2010.
M. R. Rogers, “Teaching approaches in music theory: An overview of pedagogical philosophies,” 2004.
C. Potts and G. K. Pullum, “Model theory and the content of OT constraints,” Phonology, vol. 19, no. 3, pp. 361–393, 2002.
H. Behbahani, S. Nazari, M. J. Kang, and T. Litman, “A conceptual framework to formulate transportation network design problem considering social equity criteria,” Transp. Res. part A policy Pract., vol. 125, pp. 171–183, 2019.
L. Fu, D. Sun, and L. R. Rilett, “Heuristic shortest path algorithms for transportation applications: State of the art,” Comput. Oper. Res., vol. 33, no. 11, pp. 3324–3343, 2006.
Y. Liu, Topological theory of graphs. Walter de Gruyter GmbH & Co KG, 2017.
F. Santambrogio, “Optimal transport for applied mathematicians,” 2015.
F. Santambrogio, “Variational problems in transportation theory with mass concentration.” Scuola Normale Superiore, 2006.
S. Vertovec, “Transnational social formations: toward conceptual cross-fertilization,” 2001.
J. A. De Loera and E. D. Kim, “Combinatorics and geometry of transportation polytopes: An update.,” Discret. Geom. Algebr. Comb., vol. 625, pp. 37–76, 2013.
O. Johansson, “Towards a model for managing uncertainty in logistics operations–A simulation modeling perspective,” 2006.
S. Ramasamy, R. Sabatini, and A. Gardi, “A unified analytical framework for aircraft separation assurance and UAS sense-and-avoid,” J. Intell. Robot. Syst., vol. 91, no. 3, pp. 735–754, 2018.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Fristi Riandari, Firta Sari Panjaitan
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
