SHORTEST PATH SIMPLEX ALGORITHM WITH A MULTIPLE PIVOT RULE: A COMPARATIVE STUDY

This paper introduces a new multiple pivot shortest path simplex method by choosing a subset of non-basic arcs to simultaneously enter into the basis. It is shown that the proposed shortest path simplex method requires O(n) multiple pivots and its running time is O(nm). Results from a computational study comparing the proposed method from previously known methods are reported. The experimental show that the proposed rule is more efficient than the considered shortest path simplex pivot rules.