A New Algorithm For Solving Transportation Problem With Network Connected Sources
DOI:
https://doi.org/10.31642/JoKMC/2018/020308Keywords:
Algorithm, Graph, Transportation Problem, Sorting, Kruskal’s Algorithm.Abstract
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.Downloads
References
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
Zrinka Lukač, Dubravko Hunjet, Luka Neralić, SOLVING THE PRODUCTION-TRANSPORTATION PROBLEM IN THE PETROLEUM INDUSTRY, REVISTA INVESTIGACIÓN OPERACIONAL Vol., 29 , No 1, pp63-70 , 2008.
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
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Kadhim B. S. Aljanabi, Anwar Nsaif Jasim
This work is licensed under a Creative Commons Attribution 4.0 International License.
which allows users to copy, create extracts, abstracts, and new works from the Article, alter and revise the Article, and make commercial use of the Article (including reuse and/or resale of the Article by commercial entities), provided the user gives appropriate credit (with a link to the formal publication through the relevant DOI), provides a link to the license, indicates if changes were made and the licensor is not represented as endorsing the use made of the work.