Let \(c_{ij}\) denote the nonnegative cost of traversing an arc (i,j)\(\in A\) in a directed network and \(r_{ij}\) \((0<r_{ij}\leq 1)\) its reliability, then the minimum cost-reliability ratio path problem (MCRRPP) is to find a directed path from a source node s to a sink node t in this network with minimal ratio \[ \sum_{(i,j)\in P}c_{ij}/\prod_{(i,j)\in P}r_{ij} \] among all such paths. The author shows that the optimum solution of this problem is an efficient extreme point of a bicriteria path problem. Thus the enumeration of all efficient extreme points of the two-parameter shortest path problem yields a first step to get the optimal solution. These paths can be enumerated by performing parametric analysis of the shortest path problem with arc lengths as \(d_{ij}+\mu c_{ij}\) and increasing \(\mu\) from 0 to a large number. As the efficient frontier of each solution is a piecewise linear convex function the author gives two criteria which allow to shorten the enumeration process. The whole algorithm can be formulated very elegantly. The worst case computational complexity of the algorithm is of order O(mnD log m), where m and n denote the number of arcs respectively vertices of the network and \(D=\max_{i,j\in A}\{c_{ij}\}\). Some computational results on grid networks and random networks demonstrate that the algorithm can be used very well in real life network problems.
- Augmented Threaded Index Method For Network Optimization
- Combinatorial Optimization with Rational Objective Functions
- scientific article; zbMATH DE number 3819489 (Why is no real title available?)
- scientific article; zbMATH DE number 3918092 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- scientific article; zbMATH DE number 3302125 (Why is no real title available?)
- scientific article; zbMATH DE number 3313421 (Why is no real title available?)
- Linear multiobjective programming
- Minimal Cost-Reliability Ratio Spanning Tree
- Minimal ratio spanning trees
- Optimal expansion of capacitated transshipment networks
- Ratio dynamic programs
- Time version of the shortest path problem in a stochastic-flow network
- A fully polynomial time approximation scheme for minimum cost-reliability ratio problems
- Algorithms for the quickest path problem and the enumeration of quickest paths
- On the quickest path problem
- Algorithms for the constrained quickest path problem and the enumeration of quickest paths
- The most critical path in a PERT network: A heuristic approach
- Paths with minimum range and ratio of arc lengths
- Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network
- Constrained balanced optimization problems
- Expanding maximum capacity path under weighted sum-type distances
- Bi-criteria path problem with minimum length and maximum survival probability
- Maximum probabilistic all-or-nothing paths
- The quadratic balanced optimization problem
- Reliability evaluation of a multistate network subject to time constraint under routing policy
- scientific article; zbMATH DE number 4202051 (Why is no real title available?)
- A Fourth bibliography of fractional programming
- The multichannel quickest-path problem
- Multicriteria path and tree problems: discussion on exact algorithms and applications
- Spare routing problem with p minimal paths for time-based stochastic flow networks
- The balanced traveling salesman problem
- A method to evaluate routing policy through \(p\) minimal paths for stochastic case
- System reliability for quickest path problems under time threshold and budget
- Stochastic flow networks via multiple paths under time threshold and budget constraint
- Minimum cost path problems with relays
- The quickest path problem
- Optimal paths in bi-attribute networks with fractional cost functions
- On transmission time through \(k\) minimal paths of a capacitated-flow network
This page was built for publication: Minimum cost-reliability ratio path problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1102209)
