Skip to main content
SpringerLink
Log in

On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

This paper discusses simple local search approaches for approximating the efficient set of multiobjective combinatorial optimization problems. We focus on algorithms defined by a neighborhood structure and a dominance relation that iteratively improve an archive of nondominated solutions. Such methods are referred to as dominance-based multiobjective local search. We first provide a concise overview of existing algorithms, and we propose a model trying to unify them through a fine-grained decomposition. The main problem-independent search components of dominance relation, solution selection, neighborhood exploration and archiving are largely discussed. Then, a number of state-of-the-art and original strategies are experimented on solving a permutation flowshop scheduling problem and a traveling salesman problem, both on a two- and a three-objective formulation. Experimental results and a statistical comparison are reported in the paper, and some directions for future research are highlighted.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Aguirre, H., Tanaka, K.: Random bit climbers on multiobjective MNK-landscapes: effects of memory and population climbing. IEICE Trans. Fundam. 88-A(1), 334–345 (2005)

    Article  Google Scholar 

  • Angel, E., Bampis, E., Gourvés, L.: A dynasearch neighborhood for the bicriteria traveling salesman problem. In: Metaheuristics for Multiobjective Optimisation. Lecture Notes in Economics and Mathematical Systems, vol. 535, pp. 153–176. Springer, Berlin (2004), Chap. 6

    Chapter  Google Scholar 

  • Basseur, M., Seynhaeve, F., Talbi, E.G.: Design of multi-objective evolutionary algorithms: Application to the flow shop scheduling problem. In: IEEE Congress on Evolutionary Computation, CEC 2002, pp. 1151–1156. IEEE Press, Piscataway (2002)

    Google Scholar 

  • Bleuler, S., Laumanns, M., Thiele, L., Zitzler, E.: PISA—a platform and programming language independent interface for search algorithms. In: Second International Conference on Evolutionary Multi-Criterion Optimization, EMO 2003, Lecture Notes in Computer Science, vol. 2632, pp. 494–508. Springer, Faro (2003)

    Chapter  Google Scholar 

  • Brockhoff, D., Friedrich, T., Hebbinghaus, N., Klein, C., Neumann, F., Zitzler, E.: Do additional objectives make a problem harder? In: Genetic and Evolutionary Computation Conference, GECCO 2007, pp. 765–772. ACM Press, New York (2007)

    Google Scholar 

  • Coello Coello, C.A., Lamont, G.B., Van Veldhuizen, D.A.: Evolutionary Algorithms for Solving Multi-Objective Problems, 2nd edn. Genetic and Evolutionary Computation Series. Springer, New York (2007)

    MATH  Google Scholar 

  • Davis, L.: Job shop scheduling with genetic algorithms. In: First International Conference on Genetic Algorithms, ICGA 1985, pp. 136–140. L. Erlbaum, Hillsdale (1985)

    Google Scholar 

  • Deb, K.: Multi-Objective Optimization using Evolutionary Algorithms. Wiley, Chichester (2001)

    MATH  Google Scholar 

  • Deb, K., Agrawal, S., Pratap, A., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)

    Article  Google Scholar 

  • Dubois-Lacoste, J., López-Ibáñez, M., Stützle, T.: Effective hybrid stochastic local search algorithms for biobjective permutation flowshop scheduling. In: International Workshop on Hybrid Metaheuristics, HM 2009, Lecture Notes in Computer Science, vol. 5818, pp. 100–114. Springer, Berlin (2009)

    Chapter  Google Scholar 

  • Ehrgott, M., Gandibleux, X.: Approximative solution methods for multiobjective combinatorial optimization. Top 12(1), 1–89 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  • Ehrgott, M., Gandibleux, X.: Hybrid metaheuristics for multi-objective combinatorial optimization. In: Hybrid Metaheuristics: An Emerging Approach to Optimization. Studies in Computational Intelligence, vol. 114, pp. 221–259. Springer, Berlin (2008), Chap. 8

    Google Scholar 

  • Ehrgott, M., Klamroth, K.: Connectedness of efficient solutions in multiple criteria combinatorial optimization. Eur. J. Oper. Res. 97(1), 159–166 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  • Gandibleux, X., Mezdaoui, N., Fréville, A.: A tabu search procedure to solve multiobjective combinatorial optimization problems. In: Advances in Multiple Objective and Goal Programming. Lecture Notes in Economics and Mathematical Systems, vol. 455, pp. 291–300. Springer, Berlin (1997)

    Google Scholar 

  • Geiger, M.: On operators and search space topology in multi-objective flow shop scheduling. Eur. J. Oper. Res. 181(1), 195–206 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  • Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287–326 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  • Hansen, M.P.: Tabu search for multiobjective optimisation: MOTS. In: Thirteenth International Conference on Multiple Criteria Decision Making, MCDM 1997, Springer, Cape Town (1997)

    Google Scholar 

  • Ishibuchi, H., Murata, T.: A multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE Trans. Syst. Man Cybern. 28, 392–403 (1998)

    Article  Google Scholar 

  • Jaszkiewicz, A.: Genetic local search for multi-objective combinatorial optimization. Eur. J. Oper. Res. 137(1), 50–71 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  • Knowles, J., Corne, D.: Bounded Pareto archiving: theory and practice. In: Metaheuristics for Multiobjective Optimisation. Lecture Notes in Economics and Mathematical Systems, vol. 535, pp. 39–64. Springer, Berlin (2004), Chap. 2

    Chapter  Google Scholar 

  • Knowles, J., Thiele, L., Zitzler, E.: A tutorial on the performance assessment of stochastic multiobjective optimizers. TIK Report 214, Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Zurich, Switzerland (revised version) (2006)

  • Knowles, J.D., Corne, D.: Approximating the nondominated front using the Pareto archived evolution strategy. Evol. Comput. 8(2), 149–172 (2000)

    Article  Google Scholar 

  • Landa, Silva J.D., Burke, E., Petrovic, S.: An introduction to multiobjective metaheuristics for scheduling and timetabling. In: Metaheuristics for Multiobjective Optimisation. Lecture Notes in Economics and Mathematical Systems, vol. 535, pp. 91–129. Springer, Berlin (2004)

    Chapter  Google Scholar 

  • Laumanns, M., Thiele, L., Deb, K., Zitzler, E.: Combining convergence and diversity in evolutionary multi-objective optimization. Evol. Comput. 10(3), 263–282 (2002)

    Article  Google Scholar 

  • Laumanns, M., Thiele, L., Zitzler, E.: Running time analysis of evolutionary algorithms on a simplified multiobjective knapsack problem. Nat. Comput. 3(1), 37–51 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  • Liefooghe, A., Basseur, M., Jourdan, L., Talbi, E.G.: Combinatorial optimization of stochastic multi-objective problems: an application to the flow-shop scheduling problem. In: Fourth International Conference on Evolutionary Multi-criterion Optimization, EMO 2007, Lecture Notes in Computer Science, vol. 4403, pp. 457–471. Springer, Matsushima (2007)

    Chapter  Google Scholar 

  • Liefooghe, A., Jourdan, L., Legrand, T., Humeau, J., Talbi, E.G.: ParadisEO-MOEO: a software framework for evolutionary multi-objective optimization. In: Advances in Multi-Objective Nature Inspired Computing. Studies in Computational Intelligence, vol. 272, pp. 87–117. Springer, Berlin (2010), Chap. 5

    Chapter  Google Scholar 

  • Liefooghe, A., Jourdan, L., Talbi, E.G.: A software framework based on a conceptual unified model for evolutionary multiobjective optimization: Paradis EO-MOEO. Eur. J. Oper. Res. 209(2), 104–112 (2011)

    Article  MathSciNet  Google Scholar 

  • Lust, T., Jaszkiewicz, A.: Speed-up techniques for solving large-scale biobjective TSP. Comput. Oper. Res. 37(3), 521–533 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  • Lust, T., Teghem, J.: Two-phase Pareto local search for the biobjective traveling salesman problem. J. Heuristics 16(3), 475–510 (2010)

    Article  MATH  Google Scholar 

  • Miettinen, K.: Nonlinear Multiobjective Optimization. International Series in Operations Research and Management Science, vol. 12. Kluwer Academic, Boston (1999)

    MATH  Google Scholar 

  • Neumann, F., Wegener, I.: Minimum spanning trees made easier via multi-objective optimization. Nat. Comput. 5(3), 305–319 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  • Paquete, L., Stützle, T.: A two-phase local search for the biobjective traveling salesman problem. In: Second International Conference on Evolutionary Multi-Criterion Optimization, EMO 2003, Lecture Notes in Computer Science, vol. 2632, pp. 479–493. Springer, Faro (2003)

    Chapter  Google Scholar 

  • Paquete, L., Stützle, T.: A study of stochastic local search algorithms for the biobjective QAP with correlated flow matrices. Eur. J. Oper. Res. 169(3), 943–959 (2006)

    Article  MATH  Google Scholar 

  • Paquete, L., Stützle, T.: Stochastic local search algorithms for multiobjective combinatorial optimization: a review. In: Gonzalez, T.F. (ed.) Handbook of Approximation Algorithms and Metaheuristics. Computer & Information Science Series, vol. 13. Chapman & Hall/CRC, New York (2007)

    Google Scholar 

  • Paquete, L., Stützle, T.: Design and analysis of stochastic local search for the multiobjective traveling salesman problem. Comput. Oper. Res. 36(9), 2619–2631 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  • Paquete, L., Chiarandini, M., Stützle, T.: Pareto local optimum sets in the biobjective traveling salesman problem: an experimental study. In: Metaheuristics for Multiobjective Optimisation. Lecture Notes in Economics and Mathematical Systems, vol. 535, pp. 177–199. Springer, Berlin (2004), Chap. 7

    Chapter  Google Scholar 

  • Paquete, L., Schiavinotto, T., Stützle, T.: On local optima in multiobjective combinatorial optimization problems. Ann. Oper. Res. 156(1), 83–97 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  • Rudolph, G., Agapie, A.: Convergence properties of some multi-objective evolutionary algorithms. In: IEEE Congress on Evolutionary Computation, CEC 2000, pp. 1010–1016. IEEE Press, Piscataway (2000)

    Google Scholar 

  • Serafini, P.: Some considerations about computational complexity for multiobjective combinatorial problems. In: Recent Advances and Historical Development of Vector Optimization. Lecture Notes in Economics and Mathematical Systems, vol. 294, pp. 222–231. Springer, Berlin (1986)

    Chapter  Google Scholar 

  • Serafini, P.: Simulated annealing for multiobjective optimization problems. In: Tenth International Conference on Multiple Criteria Decision Making, MCDM 1992, Taipei, Taiwan, pp. 87–96 (1992)

    Google Scholar 

  • Taillard, ED: Benchmarks for basic scheduling problems. Eur. J. Oper. Res. 64, 278–285 (1993)

    Article  MATH  Google Scholar 

  • Talbi, E.G.: Metaheuristics: From Design to Implementation. Wiley, New York (2009)

    MATH  Google Scholar 

  • Talbi, E.G., Rahoual, M., Mabed, M.H., Dhaenens, C.: A hybrid evolutionary approach for multicriteria optimization problems: application to the fow shop. In: First International Conference on Evolutionary Multi-criterion Optimization, EMO 2001, Lecture Notes in Computer Science, vol. 1993, pp. 416–428. Springer, Zurich (2001)

    Chapter  Google Scholar 

  • T’Kindt, V., Billaut, J.C.: Multicriteria Scheduling: Theory, Models and Algorithms. Springer, Berlin (2002)

    MATH  Google Scholar 

  • Ulungu, E.L., Teghem, J., Fortemps, P., Tuyttens, D.: MOSA method: a tool for solving multiobjective combinatorial optimization problems. J. Multi-Criteria Decis. Anal. 8(4), 221–236 (1999)

    Article  MATH  Google Scholar 

  • Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: Improving the strength Pareto evolutionary algorithm. TIK Report 103, Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Zurich, Switzerland (2001)

  • Zitzler, E., Thiele, L., Laumanns, M., Foneseca, C.M., Grunert da Fonseca, V.: Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. Evol. Comput. 7(2), 117–132 (2003)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Laboratoire d’Informatique Fondamentale de Lille (LIFL), UMR CNRS 8022, Université Lille 1 INRIA Lille-Nord Europe, Cité scientifique, Bât. M3, 59655, Villeneuve d’Ascq cedex, France

    Arnaud Liefooghe, Laetitia Jourdan & El-Ghazali Talbi

  2. Département IA, École des Mines de Douai, 941 rue Charles Bourseul, BP 10838, 59508, Douai, France

    Jérémie Humeau

  3. Laboratoire d’Imagerie Fonctionnelle (LIF), UMR_S 678 Inserm–UPMC, CHU Pitié-Salpêtrière, 91 boulevard de l’Hôpital, 75634, Paris cedex 13, France

    Salma Mesmoudi

  4. King Saud University, Riyadh, Saudi Arabia

    El-Ghazali Talbi

Authors
  1. Arnaud Liefooghe
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jérémie Humeau
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Salma Mesmoudi
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Laetitia Jourdan
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. El-Ghazali Talbi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Arnaud Liefooghe.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Liefooghe, A., Humeau, J., Mesmoudi, S. et al. On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems. J Heuristics 18, 317–352 (2012). https://doi.org/10.1007/s10732-011-9181-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10732-011-9181-3

Keywords

Search

Navigation