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 |
Keywords:
spanning tree; Multicriteria shortest path problems; algorithms; multiple labelling scheme; 444.90098; non-dominated pathsCitations:
Zbl 0444.90098References:
[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 · Zbl 0444.90098 |
[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.