TITLE:
A Unified Modified Vogel Framework for Transportation, Transshipment, ATSP and Capacitated Flows: Duality Certificates, Algorithmic Extensions and a Scalability Study
AUTHORS:
Oumar Koné, Pawoumodom Matthias Takouda, Youssou Gningue
KEYWORDS:
Transportation Problem, Modified Vogel Method, VAM, Transshipment, Floyd-Warshall, Asymmetric TSP, Nearest Neighbour, Capacitated Flows, Linear Programming Duality, Complementary Slackness, Scalability, Computational Study
JOURNAL NAME:
Open Journal of Applied Sciences,
Vol.16 No.10,
October
15,
2026
ABSTRACT: We develop a unified algorithmic and theoretical framework centred on the Modified Vogel Method (MVM) [1]. The framework covers five closely related models arising in logistics and combinatorial optimization: 1) balanced linear transportation problems (LTPs); 2) unbalanced LTPs with dummy-aware reduction; 3) transshipment networks compressed by Floyd minimum-cost paths into small equivalent transportation problems; 4) asymmetric travelling salesman problems (ATSPs) via an MVM-improved nearest-neighbour heuristic (MVM-NNA); and 5) capacitated (bounded) transportation problems through a VAM-B allocation rule with box complementary-slackness certificates. Building on a duality-based reframing, we interpret row/column reduction as the construction of dual-feasible potentials—the same mechanism that underlies the first phase of the Hungarian algorithm—and we state optimality certificates for both the unbounded and capacitated settings. We then present a carefully engineered, reproducible computational study comprising 1401 scalability runs plus a companion small-scale battery designed to reconnect with [1]. Reading the evidence by scale recovers that chapter’s qualitative message at sizes
n∈{
3,⋯,15 }
(MVM matches or beats VAM on 92.6% of a chapter-like schedule, with mean LP gaps at 3.96% versus 7.35%), while the large schedule (
n
up to 1000) shows the natural evolution and nuance: pathwise dominance softens to 63.6% overall, yet mean gaps remain favourable (20.01% versus 28.63% on LP-checked sizes). Floyd compression shrinks equivalent TPs by a mean factor of 6.4; MVM-NNA improves tours by 15.71% on average against fixed-start NNA; capacitated VAM-B recovers the technical note’s 2 × 2 optimum and attains a mean LP gap of 21.37%. We discuss certificates, open structural questions, and a MODI-style correction paired with VAM-B.