The tricriterion shortest path problem with at least two bottleneck objective functions. (English) Zbl 1163.90794
Summary: The focus of this paper is on the tricriterion shortest path problem where two objective functions are of the bottleneck type, for example MinMax or MaxMin. The third objective function may be of the same kind or we may consider, for example, MinSum or MaxProd. Let \(p(n)\) be the complexity of a classical single objective algorithm responsible for this third function, where \(n\) is the number of nodes and \(m\) be the number of arcs of the graph. An \(O(m^{2}p(n))\) algorithm is presented that can generate the minimal complete set of Pareto-optimal solutions. Finding the maximal complete set is also possible. Optimality proofs are given and extensions for several special cases are presented. Computational experience for a set of randomly generated problems is reported.
MSC:
| 90C47 | Minimax problems in mathematical programming |
References:
| [1] | Ahuja RK, Magnanti TL, Orlin JB. Network flows. New Jersey, 1993.; Ahuja RK, Magnanti TL, Orlin JB. Network flows. New Jersey, 1993. · Zbl 1201.90001 |
| [2] | Azevedo, J. A.; Martins, E. Q.V., An algorithm for the multiobjective shortest path problem on acyclic networks, Investigação Operacional, 11, 1, 52-69 (1991) |
| [3] | Batta, R.; Chiu, S. S., Optimal obnoxious paths on a network: Transportation of hazardous materials, Operations Research, 36, 84-92 (1988) |
| [4] | Bellman, R. E., On a routing problem, Quarterly of Applied Mathematics, 16, 87-90 (1958) · Zbl 0081.14403 |
| [5] | Berman, O.; Einav, D.; Handler, G., The constrained bottleneck problem in networks, Operations Research, 38, 178-181 (1990) · Zbl 0707.90095 |
| [6] | Camerini, P. M., The min-max spanning tree problem and some extensions, Information Processing Letters, 7, 10-14 (1978) · Zbl 0373.05028 |
| [7] | Clímaco, J. C.N.; Martins, E. Q.V., On the determination of the nondominated paths in a multiobjective network problem, Methods in Operations Research, 40, 255-258 (1981) · Zbl 0463.90084 |
| [8] | 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 |
| [9] | Corley, H. W.; Moon, I. D., Shortest paths in networks with vector weights, Journal of Optimization Theory and Applications, 46, 79-86 (1985) · Zbl 0542.90099 |
| [10] | Current, J. R.; Marsh, M., Multiobjective transportation network design and routing problems: Taxonomy and annotation, European Journal of Operational Research, 103, 426-438 (1993) · Zbl 0775.90150 |
| [11] | Current, J. R.; Min, H., Multiobjective design of transportation networks: Taxonomy and annotation, European Journal of Operational Research, 26, 187-201 (1986) |
| [12] | Current, J. R.; Revelle, C. S.; Cohon, J. L., The median shortest path problem: A multiobjective approach to analyze cost vs accessibility in the design of transportation networks, Transportation Science, 21, 3, 188-197 (1987) · Zbl 0626.90089 |
| [13] | Ehrgott, M.; Gandibleux, X., A survey and annotated bibliography of multiobjective combinatorial optimization, OR Spektrum, 22, 425-460 (2000) · Zbl 1017.90096 |
| [14] | Gabow, H. N.; Tarjan, R. E., Algorithms for two bottleneck optimization problems, Journal of Algorithms, 9, 411-417 (1988) · Zbl 0653.90087 |
| [15] | Gandibleux, X.; Beugnies, F.; Randriamasy, S., Martins’ algorithm revisited for multi-objective shortest path problems with a MaxMin cost function, A Quarterly Journal of Operations Research, 4, 47-59 (2006) · Zbl 1125.90405 |
| [16] | Gondran, M.; Minoux, M., Graphs and Algorithms (1986), John Wiley · Zbl 1117.06010 |
| [17] | Guerriero, F.; Musmanno, R., Label correcting methods to solve multicriteria shortest path problems, Journal of Optimization Theory and Applications, 111, 3, 589-613 (2001) · Zbl 0984.90050 |
| [18] | Hansen, P., Bicriterion path problems, (Fandel, G.; Gal, T., Multicriteria decision making: Theory and applications. Lecture Notes in Economics and Mathematical Systems, vol. 177 (1980), Springer), 109-127 · Zbl 0444.90098 |
| [19] | Koopmans, T. C., Activity analysis of production and allocation (1951), John Wiley & Sons · Zbl 0045.09503 |
| [20] | Martins, E. Q.V., On a multicriteria shortest path problem, European Journal of Operational Research, 16, 236-245 (1984) · Zbl 0533.90090 |
| [21] | Martins, E. Q.V., On a special class of bicriterion path problems, European Journal of Operational Research, 17, 85-94 (1984) · Zbl 0538.90086 |
| [22] | Pareto, V., Course d’economic politique (1896), Lausanne: Lausanne Rouge |
| [23] | Pinto, L.L., Bornstein, C.T., 2006a. Software CamOtim. <http://www.cos.ufrj.br/camotim>; Pinto, L.L., Bornstein, C.T., 2006a. Software CamOtim. <http://www.cos.ufrj.br/camotim> |
| [24] | Pinto, L.L., Bornstein, C.T., 2006b. Algoritmos para problemas de caminho ótimo em grafos (Algorithms for optimal path problems in graphs). In: Proceedings of the XXXVIII Brazilian Symposium on Operations Research. Goiânia-GO, pp. 2418-2419.; Pinto, L.L., Bornstein, C.T., 2006b. Algoritmos para problemas de caminho ótimo em grafos (Algorithms for optimal path problems in graphs). In: Proceedings of the XXXVIII Brazilian Symposium on Operations Research. Goiânia-GO, pp. 2418-2419. |
| [25] | Sastry, V. N.; Janakiraman, T. N.; Mohideen, S. I., New algorithms for multi objective shortest path problem, Opsearch, 40, 278-298 (2003) · Zbl 1210.90169 |
| [26] | Sastry, V. N.; Janakiraman, T. N.; Mohideen, S. I., New polynomial time algorithms to compute a set of Pareto optimal paths for multi-objective shortest path problems, International Journal of Computer Mathematics, 82, 289-300 (2005) · Zbl 1079.90146 |
| [27] | Tung, C. T.; Chew, K. L., A bicriterion Pareto-optimal path algorithm, Asia-Pacific Journal of Operational Research, 5, 166-172 (1988) · Zbl 0715.90093 |
| [28] | Tung, C. T.; Chew, K. L., A multicriteria Pareto-optimal path algorithm, European Journal of Operational Research, 62, 203-209 (1992) · Zbl 0769.90079 |
| [29] | Zeleny, M., Linear Multiobjective Programming, Lecture Notes in Economics and Mathematical Systems, vol. 95 (1974), Springer · 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.
