Obtaining a good primal solution to the uncapacitated transportation problem

Sharma and Sharma have given a new procedure to solve the dual of the well-known uncapacitated transportation problem. This is expected to enhance the performance of dual based optimizing algorithms for solving the transportation problems. In this paper we give a heuristic that obtains a very good starting solution (with a duality gap of less than 2%) for the primal transportation problem in O(n³) time, and this is expected to enhance the performance of network simplex algorithm that obtains the optimal solution and runs in O(n³log(n)) time. Empirical investigation revealed that our heuristic gave significantly better solutions than the well-known Vogel's approximation method that runs in O(n²) time.