Main Article Content


Purpose: Transportation problem plays an important role in operations research. The more generalized cases of transportation problems are trans-shipment problems. Further, the trans-shipment problems may have a set of trans-shipment nodes, or the source/destination nodes themselves act as the trans-shipment nodes. The study of the trans-shipment problems and their solution methodology is the goal of this paper.

Methodology: The solution of a trans-shipment problem could be done by transferring it to a transportation problem. Further, there exist various conventional methods for solving the transportation problem. The present paper discusses about the scope of application of an existing heuristic algorithm directly over the trans-shipment problem. The heuristic is based on the minimum spanning tree approach. We implement the algorithm over a test problem and further compare its performance by the performance of the corresponding algorithm Vogel’s Approximation Method.

Main findings: The spanning tree approach gives a better solution or almost the nearby solution as compared to the solution obtained by Vogel’s Approximation Method.

Implications: The solution obtained by the spanning-tree approach takes lesser computational effort to reach a better feasible solution.

The novelty of study: The algorithm to deal with the trans-shipment problem i.e. for finding the feasible solution of the trans-shipment problem is the main focus of this paper.Transportation Problem


Transportation Problem Trans-shipment Problem Vogel’s Approximation Method (VAM) Kruskal’s Algorithm Minimum Spanning Tree

Article Details

How to Cite
Prajapati, R., Dubey, O. P., & Pradhan, R. (2020). SOLUTION AND PERFORMANCE EVALUATION OF TRANS-SHIPMENT PROBLEM USING A MINIMUM SPANNING TREE APPROACH. International Journal of Students’ Research in Technology & Management, 8(3), 09-13.


  1. Agadaga, G. O. & Akpan, N. P. (2017). Trans-shipment Problem and Its Variants: A Review. Mathematical Theory and Modeling, 7(2), pp.19-32.
  2. Akpan, N. P. & Iwok, I. A. (2017). A minimum spanning tree approach of solving a transportation problem. International Journal of Mathematics and Statistics Invention, 5(3), pp.09-18.
  3. Aljanabi, K. B. & Jasim, A. N. (2015). An Approach for Solving Transportation Problem Using Modified Kruskal’s Algorithm. International Journal of Science and Research (IJSR), 4(7), pp.2426-2429.
  4. Antoš, K. (2016). The Use of Minimal Spanning Tree for Optimizing Ship Transportation. NAŠE MORE: znanstveno-stručničasopisza more i pomorstvo, 63(3 Special Issue), pp.81-85.
  5. Dubey, O. P., Deep, K. & Nagar, A. (2014). Goal Programming Approach To Trans-Shipment Problem, B. V. Babu (Eds.): Proceedings of the Second International Conference on Soft Computing for Problem Solving (SocProS-2012), Advances in Intelligent and Soft Computing (AISC), Springer, India, ISSN 2194-5357, Vol. 236, Page: 337-343.
  6. Gen, M., Li, Y. & Ida, K. (1999). Solving multi-objective transportation problem by spanning tree-based genetic algorithm. IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, 82(12), pp.2802-2810.
  7. Greenberg, H. J. (1998). Greedy algorithms for minimum spanning tree. University of Colorado at Denver.
  8. Jo, J. B., Li, Y. & Gen, M. (2007). Nonlinear fixed charge transportation problem by spanning tree-based genetic algorithm. Computers & Industrial Engineering, 53(2), pp.290-298.
  9. Kruskal, J. B., (1956). On the shortest spanning sub-tree of a graph and the travelling salesman problem. Proceedings of the American Mathematical society, 7(1), pp.48-50.
  10. Molla, A. Z. S., Sanei, M., Soltani, R. & Mahmoodirad, A. (2014). Solving a step fixed charge transportation problem by a spanning tree-based memetic algorithm.