Abstract
Very large-scale neighborhood search (VLSNS) is a technique intensively used in single-objective optimization. However, there is almost no study of VLSNS for multiobjective optimization. We show in this paper that this technique is very efficient for the resolution of multiobjective combinatorial optimization problems. Two problems are considered: the multiobjective multidimensional knapsack problem and the multiobjective set covering problem. VLSNS are proposed for these two problems and are integrated into the two-phase Pareto local search. The results obtained on biobjective instances outperform the state-of-the-art results for various indicators.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ahuja, R.K., Ergun, Ö., Orlin, J.B., Punnen, A.P.: A survey of very large-scale neighborhood search techniques. Discrete Appl. Math. 123(1-3), 75–102 (2002)
Alsheddy, A., Tsang, E.P.K.: Guided Pareto local search and its application to the 0/1 multi-objective knapsack problems. In: Proceedings of the Eighth Metaheuristic International Conference (MIC 2009), Hamburg (2009)
Alsheddy, A., Tsang, E.P.K.: Guided Pareto local search based frameworks for Pareto optimization. In: Proceedings of the WCCCI IEEE World Congress on Computational Intelligence, Barcelona (2010)
Alves, M.J., Almeida, M.: MOTGA: A multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem. Computers & Operations Research 34, 3458–3470 (2007)
Aneja, Y.P., Nair, K.P.K.: Bicriteria transportation problem. Management Science 25, 73–78 (1979)
Angel, E., Bampis, E., Gourvés, L.: A dynasearch neighborhood for the bicriteria traveling salesman problem. In: Gandibleux, X., Sevaux, M., Sörensen, K., T’kindt, V. (eds.) Metaheuristics for Multiobjective Optimisation. Lecture Notes in Economics and Mathematical Systems, vol. 535, pp. 153–176. Springer, Berlin (2004)
Barichard, V., Hao, J.K.: An empirical study of tabu search for the MOKP. In: Proceedings of the First International Workshop on Heuristics, China. Series of Information & Management Sciences, vol. 4, pp. 47–56 (2002)
Beausoleil, R.P., Baldoquin, G., Montejo, R.A.: Multi-start and path relinking methods to deal with multiobjective knapsack problems. Annals of Operations Research 157, 105–133 (2008)
Coello Coello, C.A., Van Veldhuizen, D.A., Lamont, G.B.: Evolutionary Algorithms for Solving Multi-Objective Problems. Kluwer Academic Publishers, New York (2002)
Czyzak, P., Jaszkiewicz, A.: Pareto simulated annealing—a metaheuristic technique for multiple-objective combinatorial optimization. Journal of Multi-Criteria Decision Analysis 7, 34–47 (1998)
Gomes da Silva, C., Clímaco, J., Figueira, J.R.: Scatter search method for the bi-criteria multi-dimensional {0,1}-knapsack problem using surrogate relaxation. Journal of Mathematical Modelling and Algorithms 3(3), 183–208 (2004)
Deb, K.: Multi-objective optimization using evolutionary algorithms. Wiley, New York (2001)
Ehrgott, M., Gandibleux, X.: Multiobjective combinatorial optimization. In: Ehrgott, M., Gandibleux, X. (eds.) Multiple Criteria Optimization – State of the Art Annotated Bibliographic Surveys, vol. 52, pp. 369–444. Kluwer Academic Publishers, Boston (2002)
Gandibleux, X., Vancoppenolle, D., Tuyttens, D.: A first making use of GRASP for solving MOCO problems. In: 14th International Conference in Multiple Criteria Decision-Making, Charlottesville (1998)
Glover, F., Kochenberger, G.: Handbook of Metaheuristics. Kluwer, Boston (2003)
Hansen, P., Mladenovic, N.: Variable neighborhood search: Principles and applications. European Journal of Operational Research 130(3), 449–467 (2001)
Ishibuchi, H., Murada, T.: A multi-objective genetic local search algorithm and its application to flow shop scheduling. IEEE Transactions on Systems, Man, and Cybernetics - Part C: Applications and Reviews 28(3), 392–403 (1998)
Jaszkiewicz, A.: Experiments done with the MOMHLIB: Technical report, Institute of Computing Science, Poznań University of Technology (2000), http://www-idss.cs.put.poznan.pl/jaszkiewicz/momhlib/
Jaszkiewicz, A.: On the Performance of Multiple-Objective Genetic Local Search on the 0/1 Knapsack Problem—A Comparative Experiment. Technical Report RA-002/2000, Institute of Computing Science, Poznań University of Technology, Poznań, Poland (July 2000)
Jaszkiewicz, A.: A comparative study of multiple-objective metaheuristics on the bi-objective set covering problem and the Pareto memetic algorithm. Technical Report RA-003/01, Institute of Computing Science, Poznań University of Technology, Poznań, Poland (2001)
Jaszkiewicz, A.: On the Performance of Multiple-Objective Genetic Local Search on the 0/1 Knapsack Problem—A Comparative Experiment. IEEE Transactions on Evolutionary Computation 6(4), 402–412 (2002)
Jaszkiewicz, A.: On the Computational Efficiency of Multiple Objective Metaheuristics. The Knapsack Problem Case Study. European Journal of Operational Research 158(2), 418–433 (2004)
Lan, G., DePuy, G.W., Whitehouse, G.E.: An effective and simple heuristic for the set covering problem. European Journal of Operational Research 176(3), 1387–1403 (2007)
Laumanns, M., Thiele, L., Zitzler, E.: An adaptative scheme to generate the Pareto front based on the epsilon-constraint method. Technical Report 199, Technischer Bericht, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology, ETH (2004)
Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling-salesman problem. Operations Research 21, 498–516 (1973)
Lust, T., Teghem, J.: Memots: a memetic algorithm integrating tabu search for combinatorial multiobjective optimization. RAIRO: Operations Research 42(1), 3–33 (2008)
Lust, T., Teghem, J.: The multiobjective multidimensionnal knapsack problem: a survey and a new approach. Technical Report arXiv:1007.4063v1, arXiv (2010)
Lust, T., Teghem, J.: Two-phase Pareto local search for the biobjective traveling salesman problem. Journal of Heuristics 16(3), 475–510 (2010)
Mavrotas, G., Figueira, J.R., Florios, K.: Solving the bi-objective multi-dimensional knapsack problem exploiting the concept of core. Applied Mathematics and Computation 215(7), 2502–2514 (2009)
Michalewicz, Z., Arabas, J.: Genetic algorithms for the 0/1 knapsack problem. In: Raś, Z.W., Zemankova, M. (eds.) ISMIS 1994. LNCS, vol. 869, pp. 134–143. Springer, Heidelberg (1994)
Paquete, L., Chiarandini, M., Stützle, T.: Pareto Local Optimum Sets in the Biobjective Traveling Salesman Problem: An Experimental Study. In: Gandibleux, X., Sevaux, M., Sörensen, K., T’kindt, V. (eds.) Metaheuristics for Multiobjective Optimisation. Lecture Notes in Economics and Mathematical Systems, vol. 535, pp. 177–199. Springer, Berlin (2004)
Prins, C., Prodhon, C., Wolfler Calvo, R.: Two-phase method and lagrangian relaxation to solve the bi-objective set covering problem. Annals OR 147(1), 23–41 (2006)
Ulungu, E.L., Teghem, J.: Multiobjective combinatorial optimization problems: A survey. Journal of Multi-Criteria Decision Analysis 3, 83–104 (1994)
Vianna, D.S., Arroyo, J.E.C.: A GRASP algorithm for the multi-objective knapsack problem. In: QEST 2004: Proceedings of the The Quantitative Evaluation of Systems, First International Conference, pp. 69–75. IEEE Computer Society, Washington, DC (2004)
Zitzler, E.: Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. PhD thesis, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland (November 1999)
Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Technical Report 103, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich, Gloriastrasse 35, CH-8092 Zurich, Switzerland (May 2001)
Zitzler, E., Thiele, L.: Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. IEEE Transactions on Evolutionary Computation 3(4), 257–271 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lust, T., Teghem, J., Tuyttens, D. (2011). Very Large-Scale Neighborhood Search for Solving Multiobjective Combinatorial Optimization Problems. In: Takahashi, R.H.C., Deb, K., Wanner, E.F., Greco, S. (eds) Evolutionary Multi-Criterion Optimization. EMO 2011. Lecture Notes in Computer Science, vol 6576. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19893-9_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-19893-9_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-19892-2
Online ISBN: 978-3-642-19893-9
eBook Packages: Computer ScienceComputer Science (R0)