id: 04049419
dt: j
an: 04049419
au: Ahuja, R.K.
ti: Minimum cost-reliability ratio path problem.
so: Comput. Oper. Res. 15, No. 1, 83-89 (1988).
py: 1988
pu: Elsevier Science Ltd. (Pergamon), Oxford
la: EN
cc: 
ut: special ratio path problem; multicriteria shortest paths; parametric
    shortest paths; minimum cost-reliability ratio path problem; efficient
    extreme point; two-parameter shortest path problem; worst case
    computational complexity; grid networks; random networks
ci: 
li: doi:10.1016/0305-0548(88)90031-7
ab: Let $c\sb{ij}$ denote the nonnegative cost of traversing an arc (i,j)$\in
    A$ in a directed network and $r\sb{ij}$ $(0<r\sb{ij}\le 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\sb{(i,j)\in
    P}c\sb{ij}/\prod\sb{(i,j)\in P}r\sb{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\sb{ij}+μc\sb{ij}$ and increasing $μ$
    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\sb{i,j\in
    A}\{c\sb{ij}\}$. Some computational results on grid networks and random
    networks demonstrate that the algorithm can be used very well in real
    life network problems.
rv: H.Noltemeier