On a multicriteria shortest path problem

Multicriteria shortest path problems have not been treated intensively in the specialized literature, despite their potential applications. In fact, a single objective function may not be sufficient to characterize a practical problem completely. For instance, in a road network several parameters (as time, cost, distance, etc.) can be assigned to each arc. Clearly, the shortest path may be too expensive to be used. Nevertheless the decision-maker must be able to choose some solution, possibly not the best for all the criteria.In this paper we present two algorithms for this problem. One of them is an immediate generalization of the multiple labelling scheme algorithm of Hansen for the bicriteria case. Based on this algorithm, it is proved that any pair of nondominated paths can be connected by nondominated paths. This result is the support of an algorithm that can be viewed as a variant of the simplex method used in continuous linear multiobjective programming. A small example is presented for both algorithms.