An Approach for Solving Transportation Problem Using Modified Kruskal's Algorithm

This paper presents a new approach for finding a minimum feasible solution for transportation problem with different types (balanced and unbalanced). The approach is based mainly on using graph theory in general and Kruskals algorithm for finding Minimum Spanning Tree (MST) in finding out the first minimum cost between sources and demands. All the edges between sources and demands are sorted in an ascending order according to the weights (costs of unit delivery between sources and demands) in an array. Starting from the first element of the array which represents the absolute minimum cost, then delete either the source vertex with all its outgoing edges if this source is satisfied or deleting the targeted demand with all its incoming edges if this demand is satisfied or even both. Different examples are considered in this paper to study the correctness and the scalability of the proposed approach. The examples cover both balanced and unbalanced transportation models. As Kruskals algorithm works with O (E log V) time complexity, where E represents the number of edges and V is the number of vertices, however, the proposed approach tends to reduce the number of vertices and the edges after each iteration and hence it will converge faster.