A new algorithm for solving transportation problem with network connected sources

الملخص EN

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