Keywords
metaheuristics
tabu sea
múltiples objetivos
metaheurísticas
búsqueda tabú
How to Cite
Abstract
In this work we present a domain-independent Tabu Search approach for multiobjective optimization with mixed-integer variables. In this we investigate two aspects: domain-independence and applicability in optimization practice and focus our attention in problems that appear frequently in the real world, like logistic network (for example: multi-stage distribution networks problems, location-allocation problems, time-tabling problems); however, other classical problems were investigated, like: coverage set problem, partitioning set problem, multidimentional knapsack problem and shortest path problem. All these problems belong to the NP-hard class, with a great number of decision variables, containing a great number of heterogeneous constrains, presenting a challenge to find feasible solutions.
References
Balas, E.; Padberg, M. (1976) “Set partitioning: a survey´´, SIAM Review 18(4): 710–760.
Beausoleil, R.P. (2014) “Interactive multiobjective tabu/scatter search based on reference point´´, Revista de Matemática : Teoría y Aplicaciones 21(2): 261–282.
Campos, V.; Laguna, M.; Martí, R. (2005) “Context-independent scatter and tabu search for permutation problems´´, INFORMS Journal on Computing 17(1): 111–122.
Davis, E.W.; Patterson, J.H. (1975) “A comparison of heuristic and optimum solutions in resource constrained project scheduling´´, Management Science 21(8): 944–955.
Deb, K.; Sundar, J.; Bhaskara, U.; Chaudhuri, S. (2006) “Reference point based multi-objective optimization using evolutionary algorithms´´, Inter- national Journal of Computational Intelligence Research (IJCIR) 2(3): 273–286.
Elmaghraby, S.E.; Moder, J.J. (1977) Handbook of Operations Research.
Geoffrion, A.M.; Graves, G.W. (1974) “Multicommodity distribution system design by benders decomposition´´, Management Science 20(5): 822– 844.
Glover, F.; Laguna, M. (1997) “General purpose heuristics for integer programming part I", Journal of Heuristics 2(4): 343–358.
Greenwood, G.W.; Hu, X.S.; D’Ambrosio, J.G. (1997) “Fitness functions for multiple objective optimization problems: combining preferences with Pareto rankings", in: R.K. Belew & M.D. Vose (Eds.) Foundations of Genetic Algorithms, San Francisco: 437–455.
Hitchcock, F.L. (1941) “The distribution of a product from several sources to numerous localities", Studies in Applied Mathematics 20(1-4): 224–230.
Jaskiewicz, A. (2004) “A comparative study of multiple-objective metaheuristics on the bi-objective set covering problem and the pareto memetic algorithm", Annals of Operation Research 131(1-4): 135–158.
Kelly, J.P.; Xu, J. (1999) “A set-partitioning-based heuristic for the vehicle routing problem", INFORMS Journal on Computing 11(2): 161–172.
Laguna, M.; Gortázar F.; Gallego, M.; Martí, R. (2014) “A black-box scatter search for optimization problems with integer variables", Journal of Global Optimization 58(3): 497–516.
Laguna, M.; Martí, R. (2003) The OptQuest Callable Library, in: S. Voss & D.L. Woodruff (Eds.) Optimization Software Class Libraries, Kluwer Academic Publishers, Boston: 193–218.
Michalewicz, Z. (1995) “A survey of constraint handling techniques in evolutionary computation methods", in: Proceedings of the 4th Annual Conference on Evolutionary Programming, MIT Press Cambridge MA, Estados Unidos: 135–155.
Mitsuo, G.; Runwei, G.; Lin, L. (2008) Network Models and Optimization: Multiobjective Genetic Algorithms Approach. Springer-Verlag Lon- don, Reino Unido.
Samed, M.M.A.; Ravagnani, M.A. da S.S. (2008) “Coevolutionary genetic algorithm to solve economic dispatch", in: P. Siarry & Z. Michalewicz (Eds.) Advances in Metaheuristics for Hard Optimization, Natural Computing Series, Springer Berlin Heidelberg: 317–327.
Smith, B.; Brailsford, S.; Hubbard, P.; Williams, H. (1996) “The progressive party problem: Integer linear programming and constraint programming compared", Constraints 1(1-2): 119–138.
Walser J.P. (1999) Integer Optimization by Local Search: A Domain-Independent Approach. Springer-Verlag Berlin Heidelberg, Alemania.
Wierzbicki, A.P. (1982) “A mathematical basis for satisficing decision making", Mathematical Modelling 3(5): 391–405.
Zitzler, E.; Laumanns, M. (2001) “Test problems for multiobjective optimizers“. Institute TIK, Swiss Federal Institute of Technology (ETH) Zurich, Switzerland.
Zitzler E.; Thiele, L. (1999) “Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach", IEEE Transactions on Evolutionary Computation 3(4): 257–271.