×

An empirical investigation of some bicriterion shortest path algorithms. (English) Zbl 0681.90081

Summary: 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.

MSC:

90C35 Programming involving graphs or networks
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bellman, R., On a routing problem, Quart. Applied Math., 16, 87-90 (1958) · Zbl 0081.14403
[2] Clímaco, J. C.N.; Martins, E. Q.V., A bicriterion shortest path algorithm, European Journal of Operational Research, 11, 399-404 (1982) · Zbl 0488.90068
[3] Current, J.; Re Velle, C.; Cohon, J., The shortest covering path problem: An application of locational constraints to network design, Journal of Regional Science, 24, 161-183 (1984)
[4] Dial, R.; Glover, F.; Karney, D.; Klingman, D., A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees, Networks, 9, 215-248 (1979) · Zbl 0414.68035
[5] Hansen, P., Bicriterion path problems, (Fandel, G.; Gal, T., Multiple Criteria Decision Making: Theory and Application, Lecture Notes in Economics and Mathematical Systems 177 (1980), Springer-Verlag: Springer-Verlag Berlin), 109-127
[6] Henig, M., The shortest path problem with two objective functions, European Journal of Operational Research, 25, 281-291 (1986) · Zbl 0594.90087
[7] Hu, T. C., Integer Programming and Network Flows (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0197.45701
[8] Knuth, D. E., (Fundamental Algorithms, Vol. 3 (1973), Addison-Wesley: Addison-Wesley Reading, MA)
[9] Loui, R., Optimal paths in graphs with stochastic or multidimensional weights, Comm. ACM, 26, 670-676 (1983) · Zbl 0526.90085
[10] Marchet, J. C.; Siskos, J., Aide à la décision en matière d’environnement: Application au choix de tracé autoroutier, (Rapport LAMSADE, 23-1979 (1979), Université de Paris Dauphine)
[11] Martins, E. Q.V., On a multicriteria shortest path problem, European Journal of Operational Research, 16, 236-245 (1984) · Zbl 0533.90090
[12] Pape, U., Implementation and efficiency of Moore-algorithms for the shortest route problem, Mathematical Programming, 7, 212-222 (1974) · Zbl 0288.90080
[13] Randolph, P.; Ringeisen, R., Shortest paths through multiple criteria networks, (Report ERI-76073 (1975), Engineering Research Institute, Iowa State University)
[14] Thuente, D., Two algorithms for shortest paths through multiple criteria networks (1979), Mathematics Dept., Indiana-Purdue University: Mathematics Dept., Indiana-Purdue University Fort Wayne, Indiana
[15] Vincke, P., Problèmes multicritères, Cahiers du Centre D’Etudes de Recherche Opérationnelle, 16, 425-439 (1974) · Zbl 0305.90045
[16] Warburton, A., Approximation of Pareto optima in multiple-objective, shortest-path problems, Operations Research, 35, 70-79 (1987) · Zbl 0623.90084
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.