×

An interactive procedure using domination cones for bicriterion shortest path problems. (English) Zbl 0790.90074

Summary: An interactive procedure is developed for the bicriterion shortest path problem. It is assumed that the decision maker’s inherant utility function is quasi-concave and non-increasing, and that the network consists of non-negative, integer valued arc lengths. The proposed procedure uses the concept of domination cones, which it develops from pairwise comparisons of alternatives. These domination cones are used to fathom a large number of Pareto-optimal solutions. Extensive computational testing was performed on large grid networks, simulating the decision maker’s response using polynomial utility functions. The results indicate that our proposed procedure is able to converge to the optimal solution in a reasonably small number of pairwise comparisons, even for those problems with a large number of Pareto-optimal solutions.

MSC:

90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Benayoun, R.; DeMontegolfier, J.; Tergny, J.; Larichev, O., Linear Programming with multiple objective functions: Step Method (STEM), Mathematical Programming, 1, 3, 366-375 (1971) · Zbl 0242.90026
[2] Dial, R.; Glover, F.; Karney, D.; Klingman, D., A computational study of alternative algorithms and labeling techniques for finding shortest path trees, Networks, 9, 215-248 (1979) · Zbl 0414.68035
[3] Geoffrion, A. M.; Dyer, J. S.; Feinberg, A., An interactive approach for multicriterion optimization with an application to the operations of an academic department, Management Science, 19, 357-368 (1972) · Zbl 0247.90069
[4] Hansen, P., Bicriterion path problems, (Fandel, G.; Gal, T., Multiple Criteria Decision Making: Theory and Applications (1980), Springer-Verlag: Springer-Verlag Heidelberg), 109-127
[5] Henig, M. I., The shortest path problem with two objectives, European Journal of Operational Research, 25, 281-291 (1985) · Zbl 0594.90087
[6] Intrigilator, M. D., Mathematical Optimization and Economic Theory (1971), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[7] Korhonen, P.; Wallenius, J.; Zionts, S., Solving the discrete multiple criteria problem using convex cones, Management Science, 30, 11, 1336-1345 (1984) · Zbl 0557.90090
[8] Marcotte, O.; Soland, R. M., An interactive branch-and-bound algorithm for multiple criteria optimization, Management Science, 32, 1, 61-75 (1986) · Zbl 0592.90057
[9] Mote, J.; Murthy, I.; Olson, D., An empirical investigation of the number of Pareto-optimal paths obtained for bicriterion shortest path problems (1987), Louisiana State University, Working Paper
[10] Ramesh, R.; Karwan, M. H.; Zionts, S., Preference structure representation using convex cones in multicriteria integer programming, Management Science, 35, 9, 1092-1105 (1989) · Zbl 0683.90089
[11] Sadagopan, S.; Ravindran, A., Interactive solution of bicriteria mathematical programs, Naval Research Logistics Quarterly, 29, 3, 443-459 (1982) · Zbl 0504.90071
[12] Soland, R. M., Multicriteria optimization: A general characterization of efficient solutions, Decision Sciences, 10, 26-38 (1979)
[13] Warburton, A., Approximation of Pareto-optima in multiple objective, shortest-path problems, Operations Research, 35, 1, 70-79 (1987) · Zbl 0623.90084
[14] White, D. J., The set of efficient solutions for multiple objective shortest path problems, Computers & Operations Research, 9, 101-107 (1982)
[15] Yu, P. L., Multipl-Criteria Decision Making: Concepts, Techniques, and Extensions (1985), Plenum Press: Plenum Press New York
[16] Yu, P. L.; Leitmann, G., Compromise solutions, domination structures, and Salukvadze’s solution, Journal of Optimization Theory and Applications, 13, 3, 362-378 (1974) · Zbl 0362.90111
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.