An empirical investigation of some bicriterion shortest path algorithms

Several applications involve finding shortest paths in bicriterion networks: those in which each arc possesses two characteristics (such as time and cost). In these circumstances, it is appropriate to find efficient (Pareto optimal) paths between various points in the network. That is, paths are sought for which no alternative path has a smaller value for the first characteristic without a larger value for the second. In this paper, several implementations of a general label correcting algorithm are discussed for bicriterion networks. These implementations are then compared on networks of varying size and having varying degrees of correlation between the two criteria. The empirical findings shed some light on the ability to solve bicriterion problems in practice and on those factors that significantly influence the computational effort.