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

A. Sedeño-Noda and C. González-Martín
Additional contact information
A. Sedeño-Noda: Departamento de Estadística, Investigación Operativa y Computación (DEIOC), Universidad de La Laguna, 38205- La Laguna, Tenerife (España), Spain
C. González-Martín: Departamento de Estadística, Investigación Operativa y Computación (DEIOC), Universidad de La Laguna, 38205- La Laguna, Tenerife (España), Spain

Asia-Pacific Journal of Operational Research (APJOR), 2010, vol. 27, issue 06, 677-691

Abstract: This paper introduces a newmultiple pivotshortest 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 requiresO(n)multiple pivots and its running time isO(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.

Keywords: Shortest path problem; simplex shortest path algorithms; multiple pivot rule; experimental analysis (search for similar items in EconPapers)
Date: 2010
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595910002946
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:27:y:2010:i:06:n:s0217595910002946

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595910002946

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().