Avoid maximum cost method for determining the initial basic feasible solution of the transportation problem

Abstract

The transportation problem is an optimization problem related to determining the transportation plan that will ensure the transportation of products from supply points to demand points with minimum total cost. Although this problem can be modeled as a linear programming model because of its special structure, it is usually solved in two phases: finding the initial basic solution and finding the optimal solution. Thus, finding a good initial solution is important, especially in large problems since it will reduce the number of steps required in the second phase. To date, many approaches have been developed to find the initial basic solution. In this study, a new method called avoid maximum cost method is proposed for determining the initial basic solution of the transportation problem. The advantage of this algorithm is that it is easy to understand and implement The avoid maximum cost method is applied to test problems and compared with six well-known initial solution methods. The results show that the proposed method produces a consistent and very good initial basic feasible solution. In addition, because of its simplicity, this method can be used as an alternative method for an initial basic feasible solution besides well-known methods in teaching.