×

On a multicriteria shortest path problem. (English) Zbl 0533.90090

Summary: 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 P. Hansen [Lect. Notes Econ. Math. Syst. 177, 109-127 (1980; Zbl 0444.90098)] for the bicriteria case. Based on this algorithm, it is proved that any pair of non-dominated 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.

MSC:

90C35 Programming involving graphs or networks
65K05 Numerical mathematical programming methods
90B10 Deterministic network models in operations research
90C31 Sensitivity, stability, parametric optimization

Citations:

Zbl 0444.90098
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Climaco, J. C.N.; Martins, E. Q.V., On the determination of the nondominated paths in a multiobjective network problem, (Proc. V. Symposium über Operations Research. Proc. V. Symposium über Operations Research, Köln, 1980. Proc. V. Symposium über Operations Research. Proc. V. Symposium über Operations Research, Köln, 1980, Methods in Operations Research, 40 (1981), Anton Hain: Anton Hain Königstein), 255-258 · Zbl 0463.90084
[2] Clímaco, J. C.N.; Martins, E. Q.V., A bicriterion shortest path algorithm, European J. Operational Res., 11, 399-404 (1982) · Zbl 0488.90068
[3] Cunningham, W. H., A network simplex method, Math. Programming, 11, 2, 105-116 (1976) · Zbl 0352.90039
[4] Fox, B. L., Data structures and computer science techniques in operations research, Operations Res., 26, 5, 686-717 (1978) · Zbl 0395.90026
[5] Hansen, P., Bicriterion path problems, (Fandel, G.; Gal, T., Multiple Criteria Decision Making: Theory and Applications. Multiple Criteria Decision Making: Theory and Applications, Lectures Notes in Economics and in Mathematical Systems, 177 (1980), Springer: Springer Heidelberg), 109-127
[6] Lawler, E. L., Combinatorial Optimization: Networks and Matroids (1976), Holt Rinehart and Winston: Holt Rinehart and Winston New York · Zbl 0358.68059
[7] Vincke, P., Problemes multicritères, Cahiers Centre Etudes Recherche Opérationnelle, 16, 425-439 (1974) · Zbl 0305.90045
[8] Yu, P. L.; Zeleny, M., The techniques of linear multiobjective programming, RAIRO, 8, V-3, 51-71 (1974) · Zbl 0309.90028
[9] Zeleny, M., Linear Multiobjective Programming (1974), Springer: Springer Berlin · Zbl 0325.90033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.