Application of Kruskal’s algorithm in finding basic feasible solutions for transportation problems
Date
2024-11-01
Authors
Ekanayake, E. M. T. D. K.
Ekanayake, E. M. U. S. B. K.
Rodrigo, W. N. P.
Journal Title
Journal ISSN
Volume Title
Publisher
Postgraduate Institute of Science (PGIS), University of Peradeniya, Sri Lanka
Abstract
Transportation problems (TPs) are prevalent in logistics and operational research optimization challenges. The structure of the transportation problem consists of multiple shipping routes connecting various sources to different destinations, with the objective of minimizing the overall transportation cost. The literature describes the development of many traditional methods to address transportation problems. Some methods, such as the Stepping Stone Method and the Modified Distribution Method (MODI), are intended to find an optimal solution to TP, while the Northwest, Least Cost, and Vogel’s Approximation techniques are concentrated on identifying a basic feasible solution. The proposed algorithm was based on a graphical method and has proven to provide initial basic feasible solutions to a reasonable degree of satisfaction, regardless of the scale of TPs. The modified Kruskal’s algorithm was adjusted to select edges that minimize transportation costs, subject to the constraints imposed by the demands and supply chains. This includes sorting the edges in ascending order of their cost and adding them to the solution iteratively until all nodes are connected and the constraints are satisfied. This study suggested an algorithmic approach simpler than the well-known heuristic algorithms.
Description
Keywords
Initial basic feasible solution , Kruskal’s algorithm , Minimum spanning tree , Transportation problems
Citation
Proceedings of the Postgraduate Institute of Science Research Congress (RESCON) -2024, University of Peradeniya, P. 76