分数惩罚Vogel逼近法：一种用于运输问题初始基本可行解的尺度不变改进方法

《AppliedMath》：A New Algorithm for Finding Initial Basic Feasible Solutions of Transportation Problems Douglas Kwasi Boah, Suleman Abudu Fiele and Christian John Etwire

为解决经典Vogel逼近法（VAM）在运输问题中对成本差异的敏感性不足问题，本研究提出了一种基于乘法对比率的分数惩罚改进方法。该研究在34个基准及大规模算例上验证了方法的有效性，结果显示其平均最优性间隙仅为2.78%，显著优于传统VAM（5.22%）、最小成本法（14.97%）和西北角法（45.78%）。该方法在保持计算效率的同时，提高了初始解的质量与鲁棒性，为运输问题的求解提供了一种更为精确的启发式策略。

　　

在供应链管理与物流规划中，运输问题（Transportation Problem, TP）作为线性规划的经典模型，其高效求解一直是运筹学领域的研究热点。求解运输问题通常分为两步：首先找到一个初始基本可行解（Initial Basic Feasible Solution, IBFS），然后通过如踏脚石法（Stepping-Stone）或MODI法（Modified Distribution Method）等优化过程逐步逼近最优解。一个高质量的IBFS能有效减少后续优化所需的迭代次数，从而提升整体求解效率。然而，现有主流IBFS生成方法，如西北角法（Northwest Corner Method, NWCM）、最小成本法（Least Cost Method, LCM）和Vogel逼近法（Vogel’s Approximation Method, VAM），各有优劣。其中，VAM因其引入了基于行或列中两个最小可接受成本之差的“惩罚”机制，被广泛认为能产生质量较高的初始解。尽管如此，传统VAM所使用的加法惩罚对成本的绝对规模和尺度变换敏感，在成本结构异质性较强的环境中，可能无法充分捕捉不同分配选项之间的比例差异。这一局限促使研究人员探索在保留VAM基本框架的前提下，对惩罚机制进行理论驱动的改进。

为此，Douglas Kwasi Boah, Suleman Abudu Fiele 和 Christian John Etwire 在《AppliedMath》上发表了他们的研究成果。他们提出了一种对Vogel逼近法的确定性分数惩罚改进。该方法的核心创新在于，将传统的加法遗憾（即成本差）替换为乘法对比比率，即用各行/列中第二小可接受成本除以最小可接受成本。这种分数惩罚机制强调成本间的比例对比，并且具有尺度不变性，即对成本进行统一的正数缩放不会改变惩罚值的相对大小。研究旨在通过这种修改，提升初始解的质量和稳定性，而非改变VAM的分配结构本身。

为验证该方法，研究人员主要采用了计算实验与统计验证相结合的技术路径。他们在34个运输问题算例（包括文献中的基准算例和自行构造的大规模实例，最大规模达10×20）上进行了测试。通过比较由改进方法、经典VAM、LCM和NWCM生成的IBFS与通过踏脚石法和MODI法求得的最优解之间的百分比最优性间隙，来评估各方法的性能。此外，还运用了配对t检验和Wilcoxon符号秩检验对改进方法相对于经典VAM的性能提升进行了统计显著性分析。

研究结果

3.1 符号与通用步骤

研究首先明确了运输问题的标准数学模型，定义了成本矩阵C = (c_ij)、供给a_i和需求b_j，并阐述了问题平衡化（通过添加零成本虚拟行/列）以及生成IBFS的通用步骤，包括确定的平局打破规则和退化预防机制（确保解中恰有m + n - 1个基本变量）。

3.2 性能评估

计算实验显示，所提出的分数惩罚VAM在所有测试算例上取得了最佳的平均性能。其平均最优性间隙为2.78%，而经典VAM、LCM和NWCM的平均间隙分别为5.22%、14.97%和45.78%。这一结果直观表明改进方法能产生更接近最优解的初始解。

3.3 统计验证

统计分析为性能提升提供了统计依据。配对t检验结果为t = -3.17 (p = 0.00163, 单侧)，Wilcoxon符号秩检验结果为p = 6.10 × 10^-5。这些极低的p值（远小于0.05的常见显著性水平）强有力地支持了改进方法在减少最优性间隙方面显著优于经典VAM的结论。

3.4 鲁棒性与效率

研究还指出，改进方法产生的最优性间隙分布更为集中，表明其在不同成本结构的问题中具有更好的鲁棒性。同时，计算实验证实，该改进并未增加相对于经典IBFS程序（如VAM、LCM）的运行时间，保持了计算上的简洁性。

结论与讨论

本研究引入了一种基于乘法对比率的分数惩罚机制，对经典的Vogel逼近法进行了结构化增强。该改进方法在保留VAM原有分配逻辑和计算效率的前提下，通过一种尺度不变的惩罚计算方式，增强了对相对成本差异的敏感性。在大量基准和大规模运输问题上的测试表明，该方法能系统性地产出质量更高、更稳定的初始基本可行解，且其优越性得到了严格的统计检验支持。

这项工作的意义在于，它为解决运输问题提供了一个计算高效且易于实现的增强型启发式算法。对于物流、供应链优化等实际应用场景，一个更好的初始解意味着后续优化过程可能更快收敛，从而节省计算资源与时间。该方法是对经典运筹学教学与实践内容的一项有价值的补充与精炼，展示了通过深入理论分析对成熟算法进行微调以获得实质性性能增益的可能性。