Multiloop transportation simplex algorithm. (2nd November 2017)

• Record Type: Journal Article
• Authors: Bulut, Hasan
• Is Part Of: Optimization methods and software. Volume 32:Number 6(2017)
• Page Start: 1206
• Page End: 1217
• Publication Date: 2017-11-02
• Subjects: transportation problem -- transportation simplex algorithm -- linear programming -- computational experiments; 90C05 -- 90C08 -- 90C10;·68U01 -- 68W01; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2016.1260568
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : In large-scale transportation problems (TPs), various methods have been developed to obtain an optimal solution. One of the methods is the transportation simplex algorithm (TSA), which obtains an optimal solution for TP. Various heuristic methods have been developed to find an initial basic feasible solution for transportation algorithms. These methods differ in terms of computational cost and finding good initial solution. In TSA, the better the basic feasible solution, the less the number of iterations the algorithm will run. At each step, it uses pivoting operation, where a loop involving the nonbasic variable with the largest cost reduction is determined. Then, it eliminates the entering basic variable. However, for large-scale problems, even the best basic feasible solution may result in high number of iterations. In this paper, we present a novel algorithm called multiloop transportation simplex algorithm which finds multiple independent loops during pivoting operation. This causes larger cost reductions in every iteration. We experimentally show that the average number of iterations and runtime to solve the TP are dramatically reduced.