A parametric approach to solving bicriterion shortest path problems

In this paper a new algorithm is developed to solve bicriterion shortest path problems. This algorithm first relaxes the integrality conditions and solves a simple bicriterion network problem. The bicriterion network problem is solved parametrically, exploiting properties associated with adjacent basis trees. Those Pareto-optimal paths not obtained by solving the LP relaxation are obtained using a label correcting procedure. Computational results comparing the parametric approach to the label setting approach and the K-th shortest path approach are also presented. They indicate that the parametric approach is orders of magnitude faster than the K-th shortest path approach for most problems tested. For problems with a positive correlation between the two coefficients, the parametric approach is seen to be significantly faster than the label setting approach.