A New Algorithm For Solving Transportation Problem With Network Connected Sources


  • Kadhim B. S. Aljanabi University of Kufa
  • Anwar Nsaif Jasim University of Kufa




Algorithm, Graph, Transportation Problem, Sorting, Kruskal’s Algorithm.


Solving transportation problems where products to be supplied from one side(sources) to another (demands) with a goal to minimize the overall transportation cost represents an activity of great importance. Most of the works done in the field deals with the problem as two-sided model (Sources such as factories and Demands such as warehouses) with no connections between sources or demands. However, real world transportation problems may come in another model where sources are connected in a network like graph in which each source may supply other sources in a specific cost. The work in this paper suggests an algorithm and a graph model with mathematical solution for finding the minimum feasible solution for such widely used transportation problems. In this work, the graph representing the problem in which all sources are connected together in a network model with specific cost on each edge is converted into a new graph where additional virtual sources representing supplies between sources are added to the graph , new costs between the added sources and the demands are also calculated, and then modified Kruskal’s algorithm is applied to get the minimum feasible solution. The proposed solution is a straight forward model with strong mathematical and graph models. It can be widely used for solving real world transportation problems with feasible time and space complexity where time complexity of O(E2 + V2) is required, where E represents the number of edges and V represents the number of vertices. Different numerical examples were used to study the effectiveness and correctness of the proposed algorithm.


Download data is not yet available.


Hamdy A. Taha, Operations Research: An Introduction ,9th Edition,2013, ISBN-13: 978 0132555937.

Douglas B. West, Introduction to Graph Theory, 2nd Edition, PHI NewDElhi,2009.

S. Kumaraguru, B. Satheesh Kumar, M. Revathy, Comparitive Study of Various Methods for Solving Transportation Problem, IJSR–I INTERNATIONAL JOURNAL OF SCIENTIFIC RESEARCH Vol.1, Issue : 9, ISSN No 2277 – 8179, September 2014.

Nigus Girmay, Tripti Sharma, Balance An Unbalanced Transportation Problem By A Heuristic approach, International Journal of Mathematics And Its Applications, Vol.1, No.1, pp 12-18, 2013.

Ilija NIKOLIĆ, TOTAL TIME MINIMIZING TRANSPORTATION PROBLEM, Yugoslav Journal of Operations Research, 17 (2007), No.1, pp125-133, DOI: 10.2298/YUJOR0701125N. DOI: https://doi.org/10.2298/YJOR0701125N


Mohammad Kamrul Hasan, Direct Methods for Finding Optimal Solution of aTransportation Problem are not Always Reliable, International Refereed Journal of Engineering and Science (IRJES) ISSN (Online) 2319- 183X, (Print) 2319-1821 Volume 1, Issue 2 (October 2012), PP.46-52.

Jose E. Florez et al., Planning Multi-Modal Transportation Problems, Proceedings of the Twenty-First International Conference on Automated Planning and Scheduling, Association for the Advancement of Artificial Intelligence (www.aaai.org), 2011. DOI: https://doi.org/10.1609/icaps.v21i1.13466

Gaurav Sharma, S. H. Abbas and Vijay Kumar Gupt, SOLVING TRANSPORTATION PROBLEM WITH THE VARIOUS METHOD OF LINEAR PROGRAMMING PROBLEM, Asian Journal of Current Engineering and Maths1: 3 May – June (2012) 81 – 83.

M. A. Hakim, An Alternative Method to Find Initial Basic Feasible Solution of a Transportation Problem, Annals of Pure and Applied Mathematics, Vol. 1, No. 2, 2012, 203-209, ISSN: 2279-087X (P), 2279- 0888(online), Published on 16 November 2012.

Abdallah A. Hlayel, Mohammad A. Alia, SOLVING TRANSPORTATION PROBLEMSUSING THE BEST CANDIDATES METHOD, Computer Science & Engineering: An International Journal (CSEIJ), Vol.2, No.5, October 2012, DOI :10.5121/cseij.2012.2503 23. DOI: https://doi.org/10.5121/cseij.2012.2503

Hlayel Abdallah Ahmad, The Best Candidates Method for Solving Optimization Problems, Journal of Computer Science 8 (5): 711-715, 2012,ISSN 1549-3636, 2012 Science Publications. DOI: https://doi.org/10.3844/jcssp.2012.711.715

Kadhim B. S. Aljanabi, Anwar Nsaif Jasim, An Approach for Solving Transportation Problem Using Modified Kruskal’s Algorithm, International Journal of Science and Research (IJSR), Volume 4 Issue 7, July 2015, pp 2426-2429.

Abdul Sattar S., Gurudeo A. T., Ghulam M., A comparative study of initial basic feasible solution methods for transportation problems, Mathematical Theory and

Modeling ISSN 2224-5804 (Paper) ISSN 2225-0522 (Online) Vol.4, No.1, 2014




How to Cite

S. Aljanabi, K. B., & Jasim, A. N. (2015). A New Algorithm For Solving Transportation Problem With Network Connected Sources. Journal of Kufa for Mathematics and Computer, 2(3), 85–92. https://doi.org/10.31642/JoKMC/2018/020308

Similar Articles

1 2 3 4 5 6 > >> 

You may also start an advanced similarity search for this article.