A New Algorithm for Finding Initial Basic Feasible Solutions of Transportation Problems

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.