Efficient solution generation for the bicriterion shortest path problems

In this paper, we present an algorithm to compute the set of all efficient extreme solutions in the objective space for the biobjective shortest path problem (BSPP). A simplex-based algorithm that generates all the efficient extreme points and edges in the objective space rather than the decision space is developed. Since not every extreme point of the decision space corresponds to an extreme point of the objective space, the number of these efficient extreme points in the objective space cannot exceed that of the decision space. Since the coefficient matrix associated with the flow conservation equations is totally unimodular for the BSPP, the efficient frontier is the non-dominated set of its continuous relaxation.