MINIMUM COST-RELIABILITY RATIO PATH PROBLEM

The minimum ratio path problem in a network is known to be a strong NP-complete problem. However its variant, the minimum cost-reliability ratio path problem, is shown to possess an entirely different structure. We observe that the optimum solution of the minimum cost-reliability ratio path problem is an efficient extreme solution of a bicriteria path problem. We employ parametric programming to enumerate these efficient extreme solutions and a sufficiency condition is used to cut down the enumeration substantially. The algorithm is shown to be pseudo-polynomial. Computational results of the algorithm on grid as well as random networks are also presented. The algorithm is able to solve problems with several thousand nodes and arcs in a few seconds.