A NETWORK AUGMENTING PATH BASIS ALGORITHM FOR TRANSSHIPMENT PROBLEMS
The purpose of this paper is to present a new simplex algorithm for solving capacitated transshipment network problems which both circumvents and exploits the pervasive degeneracy in such problems. This generalized alternating path algorithm is based on the characterization of a special subset of the bases that are capable of leading to an optimal solution. With consideration restricted to these bases, fewer alternative representations of a given extreme point are inspected. The impact on the number of degenerate pivots and problem solution times is demonstrated by computational testing and comparison with other approaches. (Author)
- Revision of report dated Aug 77. Prepared in cooperation with Decision Analysis and Research Inst., Austin, TX, Contract no. N00014-76-C-0383.
University of Texas, AustinCenter for Cybernetic Studies
Austin, TX United States 78712
- BARR, R
- Elam, J
- Glover, F
- Klingman, D
- Publication Date: 1978-3
- Pagination: 35 p.
- TRT Terms: Algorithms; Combinatorial analysis; Decision theory; Network analysis (Planning); Operations; Optimization; Physical distribution; Planning; Shipping; Simplex method; Traffic managers
- Uncontrolled Terms: Shippers
- Old TRIS Terms: Operations planning
- Subject Areas: Administration and Management; Freight Transportation; Marine Transportation; Planning and Forecasting; Railroads;
- Accession Number: 00185508
- Record Type: Publication
- Source Agency: National Technical Information Service
- Report/Paper Numbers: CCS-272 Res Rpt.
- Contract Numbers: N00014-75-C-0569, N00014-75-C-0616
- Files: TRIS
- Created Date: Dec 29 1979 12:00AM