Multiloop transportation simplex algorithm

Bulut H.

OPTIMIZATION METHODS & SOFTWARE, vol.32, pp.1206-1217, 2017 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 32
  • Publication Date: 2017
  • Doi Number: 10.1080/10556788.2016.1260568
  • Page Numbers: pp.1206-1217


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.