An Exact Algorithm for the Fixed Charge Transportation Problem Based on Matching Source and Sink Patterns
提出一种新的整数规划模型，通过匹配源和汇的流量模式求解固定费用运输问题，其线性松弛下界优于现有方法，集成到分支切割定价算法后，在基准实例上比现有方法快数倍，并解决了所有未解实例。
This paper describes an exact algorithm for the fixed charge transportation problem based on a new integer programming formulation that involves two sets of variables representing flow patterns from sources to sinks and from sinks to sources. The formulation states to select a pattern for each source and each sink and to match the corresponding flows. The linear relaxation of this new formulation is enforced by adding a pseudo-polynomial number of equations that are shown to contain, as special cases, different valid inequalities recently proposed for the problem. The resulting lower bound dominates the lower bounds proposed in the literature. Such a lower bound is embedded into an exact branch-and-cut-and-price algorithm. Computational results on benchmark instances show that the proposed algorithm is several times faster than the state-of-the-art exact methods and could solve all open instances. New harder instances with up to 120 sources and 120 sinks were solved to optimality. The online appendix is available at https://doi.org/10.1287/trsc.2017.0742 .