On approximation of the fixed charge transportation problem

•In this paper we present a new approximation for computing lower bound for the fixed charge transportation problem (FCTP).•The proposed lower bound may be used as a superior initial solution with any other existing branch-and-bound method or tabu search heuristic procedure.•The initial solution enhances convergence to the optimal solution for large size problems which cannot be solved by CPLEX due to time constraints.

In this paper we present a new approximation for computing lower bound for the fixed charge transportation problem (FCTP). The lower bounds thus generated delivered 87% optimal solutions for 56 randomly generated small, up to 6×10 in size, problems in an experimental design. For somewhat larger, 10×10 and 10×15 size problems, the lower bounds delivered an average error of 5%, approximately, using a fraction of CPU times as compared to CPLEX to solve these problems. The proposed lower bound may be used as a superior initial solution with any other existing branch-and-bound method or tabu search heuristic procedure to enhance convergence to the optimal solution for large size problems which cannot be solved by CPLEX due to time constraints.