Title: New heuristic to generate an initial basic feasible solution for the balanced transportation problem

Authors: Youssef Harrath; Jihene Kaabi

Addresses: College of Information Technology, University of Bahrain, P.O. Box 32038, Kingdom of Bahrain ' College of Information Technology, University of Bahrain, P.O. Box 32038, Kingdom of Bahrain

Abstract: This paper studied the balanced transportation problem. Many algorithms were developed to solve optimally this problem. The most commonly used method is the modified distribution method (MODI). The MODI algorithm starts by generating an initial basic feasible solution using the northwest corner method (NCM). In general, the cost of the initial basic feasible solution generated by NCM is too high and far away from the optimal cost. For this reason, we propose in this paper a new method to generate an initial basic feasible solution to the balanced transportation problem to solve this issue. This method, named Global Minimum Method (GMM), was tested and compared with the NCM, the minimum cost method (MCM), the Vogel's approximation method (VAM), and the optimal cost obtained by MODI. The computational results proved that the new heuristic is promising for small size instances and outperforms all other methods for big size problems.

Keywords: linear programming; LP; transportation problem; basic feasible solution.

DOI: 10.1504/IJISE.2018.094842

International Journal of Industrial and Systems Engineering, 2018 Vol.30 No.2, pp.193 - 204

Received: 26 Apr 2016
Accepted: 15 Oct 2016
Published online: 25 Sep 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article