×

Multiobjective combinatorial optimization problems with a cost and several bottleneck objective functions: an algorithm with reoptimization. (English) Zbl 1251.90312

Summary: This paper addresses multicriteria combinatorial optimization problems involving one cost and several bottleneck objective functions. An algorithm is developed which generates the minimal complete set of Pareto-optimal solutions. This algorithm runs in polynomial time as long as the single objective problem considering only the cost function can be solved polynomially. A reoptimization procedure is used to accelerate the convergence of the algorithm. Applications are given. Computational results on randomly generated instances and planar grid graphs concerning the minimum cost spanning tree and the shortest path problem are presented.

MSC:

90C27 Combinatorial optimization
90C29 Multi-objective and goal programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Batta, R.; Chiu, S. S., Optimal obnoxious paths on a network: transportation of hazardous materials, Operations Research, 36, 84-92 (1988)
[2] Berman, O.; Einav, D.; Handler, G., The constrained bottleneck problem in networks, Operations Research, 38, 178-181 (1990) · Zbl 0707.90095
[3] Current, J. R.; Min, H., Multiobjective design of transportation networks: taxonomy and annotation, European Journal of Operational Research, 26, 187-201 (1986)
[4] 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
[5] Dijkstra, E., A note on two problems in connection with graphs, Numerical Mathematics, 1, 395-412 (1959)
[6] Ehrgott, M., Multiple criteria optimization—classification and methodology (1997), Shaker Verlag: Shaker Verlag Aachen, Germany
[7] Ehrgott, M.; Gandibleux, X., Multiple criteria optimization. State of the art annotated bibliographic surveys (2002), Kluwer Academic: Kluwer Academic Dordrecht · Zbl 1024.00020
[8] Gabow, H., Two algorithms for generating weighted spanning trees in order, SIAM Journal on Computing, 6, 139-150 (1977) · Zbl 0346.68021
[9] Gandibleux, X.; Beugnies, F.; Randriamasy, S., Multi-objective Shortest Path Problems with a maxmin cost function, 4OR - Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 4, 47-59 (2006) · Zbl 1125.90405
[10] Gorski J, Klamroth K, Ruzika S. Generalized multiple objective bottleneck problems. Report in Wirtschaftsmathematik, Nr. 131, Department of Mathematics, Technical University of Kaiserslautern; 2010.; Gorski J, Klamroth K, Ruzika S. Generalized multiple objective bottleneck problems. Report in Wirtschaftsmathematik, Nr. 131, Department of Mathematics, Technical University of Kaiserslautern; 2010. · Zbl 1247.90223
[11] Hansen, P., Bicriterion path problems, (Fandel, G.; Gal, T., Multiple criteria decision making: theory and applications (Lectures notes in economics and mathematical systems), vol. 177 (1980), Springer: Springer Heidelberg), 109-127 · Zbl 0444.90098
[12] Kruskal, J., On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical Society, 7, 48-50 (1956) · Zbl 0070.18404
[13] Martins, E. Q.V., On a special class of bicriterion path problems, European Journal of Operational Research, 17, 85-94 (1984) · Zbl 0538.90086
[14] Pallottino, S.; Scutellà, M. G., A new algorithm for reoptimizing shortest paths when the arc costs change, Operations Research Letters, 31, 149-160 (2003) · Zbl 1041.90062
[15] Pinto, L. L.; Bornstein, C. T.; Maculan, N., The tricriterion shortest path problem with at least two bottleneck objective functions, European Journal of Operational Research, 198, 387-391 (2009) · Zbl 1163.90794
[16] Pinto, L. L.; Laporte, G., An efficient algorithm for the Steiner tree problem with revenue, bottleneck and hop objective functions, European Journal of Operational Research, 207, 45-49 (2010) · Zbl 1205.90068
[17] Pinto, L. L.; Pascoal, M., On algorithms for the tricriteria shortest path problem with two bottleneck objective functions, Computers & Operations Research, 37, 1774-1779 (2010) · Zbl 1188.90246
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.