Hybrid Two-Stage Algorithm for Solving Transportation Problem

Abstract

In this paper a hybrid two-stage algorithm is proposed to find the optimal solution for transportation problem (TP). The proposed algorithm consists of two stages: the first stage uses genetic algorithm (GA) to find an improved nonartificial feasible solution for the problem and the second stage utilizes this solution as a starting point in the RSM algorithm to find the optimal solution for the problem. The algorithm utilizes big M method to handle ? constraints and northwest corner method, minimum cost method, and Vogel's method are also used to generate the initial population for the GA. Performance of the algorithm is tested under different simulated scenarios and compared to both GA and revised simplex method (RSM). The results showed that the new hybrid algorithm performs competitively against GA and RSM. The proposed algorithm can be easily extended to cover different kinds of linear programming (LP) problems with minor changes such as inventory control, employment scheduling, personnel assignment and transshipment problems.