A New Algorithm for Finding Initial Basic Feasible Solutions of Transportation Problems
AppliedMath · 09.04.2026 · 6 (4) · 58
DOI: 10.3390/appliedmath6040058 ↗Kurz gefasst
Fachartikel in der Zeitschrift AppliedMath, online erschienen am 09.04.2026. Verfasst von Douglas Kwasi Boah und 2 weiteren Autor:innen. Die Arbeit nennt 32 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
This study introduces a deterministic fractional-penalty refinement of Vogel’s Approximation Method (VAM) for generating high-quality initial basic feasible solutions (IBFS) in classical transportation problems. Unlike the traditional additive regret measure employed in VAM, the proposed method uses a multiplicative contrast ratio between the two smallest admissible costs in each row and column. This modification preserves the allocation structure of VAM while introducing scale-invariant prioritization that improves sensitivity to relative cost differences.The method was evaluated on thirty-four benchmark transportation problems drawn from the literature and self-constructed large-scale instances (up to 10×20). Performance was assessed using percentage optimality gaps relative to optimal solutions obtained via the Stepping–Stone and MODI procedures. Across all instances, the proposed approach achieved a mean optimality gap of 2.78%, compared to 5.22% for classical VAM, 14.97% for the Least Cost Method (LCM), and 45.78% for the Northwest Corner Method (NWCM). Dispersion of deviations was also reduced, indicating improved robustness across heterogeneous cost structures Statistical validation confirms the improvement over VAM: the paired t-test yielded t=−3.17 (p=0.00163, one-sided), and the Wilcoxon signed-rank test produced p=6.10×10−5. Computational experiments further show that the refinement does not increase runtime relative to classical IBFS procedures.The proposed method therefore constitutes a structured enhancement of VAM that improves initial solution quality while maintaining computational simplicity.
Zitieren
APA
Boah, D. K., Fiele, S. A., & Etwire, C. J. (2026). A New Algorithm for Finding Initial Basic Feasible Solutions of Transportation Problems. AppliedMath, 6(4), 58. https://doi.org/10.3390/appliedmath6040058
Vancouver
Boah DK, Fiele SA, Etwire CJ. A New Algorithm for Finding Initial Basic Feasible Solutions of Transportation Problems. AppliedMath. 2026;6(4):58. doi:10.3390/appliedmath6040058
BibTeX
@article{Boah2026,
author = {Boah, Douglas Kwasi and Fiele, Suleman Abudu and Etwire, Christian John},
title = {A New Algorithm for Finding Initial Basic Feasible Solutions of Transportation Problems},
journal = {AppliedMath},
year = {2026},
volume = {6},
number = {4},
pages = {58},
doi = {10.3390/appliedmath6040058}
}
EUVIMED