본문 바로가기
  • Home

The Assignment-Swap Algorithm for Large-scale Transportation Problem with Incomplete Cost Lists

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2015, 20(6), pp.51-58
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Sang-Un, Lee 1

1강릉원주대학교

Accredited

ABSTRACT

This paper suggests assignment-swap algorithm with time complexity O(mn) to obtain the optimal solution for large-scale of transportation problem (TP) with incomplete cost lists. Generally, the TP with complete cost lists can be solved with TSM (Transportation Simplex Method). But, we can't be solved for large-scale of TP with TSM. Especially. It is hard to solve for large-scale TP with incomplete cost lists using TSM. Therefore, experts simply using commercial linear programming package. Firstly, the proposed algorithm applies assignment strategy of transportation quantity to ascending order of transportation cost. Then, we reassign from surplus of supply to shortage of demand. Secondly, we perform the 2-opt and 1-opt swap optimization to obtain the optimal solution. Upon application to 31 × 15 incomplete cost matrix problem, the proposed assignment-swap algorithm more improves the solution than LINGO of commercial linear programming.

Citation status

* References for papers published after 2022 are currently being built.