Solving the Linear Programming Model of Large-Scale Transportation and Assignment Problems using the Column Generation Technique

Abstract

The aim of this study was to solve the transportation problems (TPs) and assignment problems (APs) involved with too many decision variables when using a regular state-of-the-art linear programming (LP) software. To overcome its limitations, a column generation method was developed and used to solve both problems with large-scale sizes.  The method was coded using MATLAB 2010b and was used to compute experimentally as compared to the use of the regular LP-solving toolbox “linprog.”. The results of this experiment revealed that the largest sizes for the column generation method to solve both TP and AP were 16,333 customers x 100 plants/warehouses and 12,900 tasks x 12,900 assignees, respectively, while the largest sizes for the “linprog” to solve both were limited to 11,062 customers x 100 plants and 7,400 tasks x 7,400 assignees respectively using the same hardware. The average computational time of the column generation method was greater in small-size problems; nevertheless, the difference between the computing times consumed by both methods reduced significantly when the number of variables was increased. This experiment revealed that the computation time of the TP was related directly to the number of new columns generated. Also, the large number of constraints of the TP model for the column generation technique can be more influential on computation time performances than the large number of variables.