Minimum cost-reliability ratio path problem (Q1102209): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0305-0548(88)90031-7 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1984044902 / rank | |||
Normal rank |
Revision as of 21:41, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimum cost-reliability ratio path problem |
scientific article |
Statements
Minimum cost-reliability ratio path problem (English)
0 references
1988
0 references
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.
0 references
special ratio path problem
0 references
multicriteria shortest paths
0 references
parametric shortest paths
0 references
minimum cost-reliability ratio path problem
0 references
efficient extreme point
0 references
two-parameter shortest path problem
0 references
worst case computational complexity
0 references
grid networks
0 references
random networks
0 references