Multiloop transportation simplex algorithm


Bulut H.

OPTIMIZATION METHODS & SOFTWARE, cilt.32, ss.1206-1217, 2017 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 32
  • Basım Tarihi: 2017
  • Doi Numarası: 10.1080/10556788.2016.1260568
  • Dergi Adı: OPTIMIZATION METHODS & SOFTWARE
  • Sayfa Sayıları: ss.1206-1217

Özet

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.