FINDING MINIMAL COST-TIME RATIO CIRCUITS,
Abstract
An efficient method is given for finding minimal cost-time ratio circuits in routing problems through the use of the out-of-kilter algorithm. The problem of finding a cycle in a network having a minimal cost-to-time ratio has been considered previously, and column generators have been used to introduce, into the basis of the master problem, the solution that corresponds to this cycle. The subproblem is of independent interest and corresponds to deterministic single chain Markov renewal programming. The main difference between earlier approaches and the present one is that where others have used a shortest path method corresponding to the simplex method (except that steepest descent is not used), here the flow circulation problem for optimal cost-time tradeoff is solved parametrically by the out-of-kilter algorithm. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1968
- Accession Number
- AD0672256
Entities
People
- Bennett Fox
Organizations
- RAND Corporation