Minimum cost-reliability ratio path problem (Q1102209)

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.