Two Metaheuristics for Multiobjective Stochastic Combinatorial Optimization

  • Walter J. Gutjahr
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3777)


Two general-purpose metaheuristic algorithms for solving multiobjective stochastic combinatorial optimization problems are introduced: SP-ACO (based on the Ant Colony Optimization paradigm) which combines the previously developed algorithms S-ACO and P-ACO, and SPSA, which extends Pareto Simulated Annealing to the stochastic case. Both approaches are tested on random instances of a TSP with time windows and stochastic service times.


Ant colony optimization combinatorial optimization multiobjective decision analysis simulated annealing stochastic optimization 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Baesler, F.F., Sepúlveda, J.A.: Multi-objective simulation optimization for a cancer treatment center. In: Proc. WSC 2001, pp. 1405–1411 (2001)Google Scholar
  2. 2.
    Czyzak, P., Jaszkiewicz, A.: Pareto simulated annealing — a metaheuristic technique for multiple-objective combinatorial optimization. J. of Multi-Criteria Decision Analysis 7, 34–47 (1998)zbMATHCrossRefGoogle Scholar
  3. 3.
    Doerner, K., Gutjahr, W.J., Hartl, R.F., Strauss, C., Stummer, C.: Ant Colony Optimization in Multiobjective Portfolio Selection. In: Proc. 4th Metaheuristics International Conference, pp. 243–248 (2001)Google Scholar
  4. 4.
    Doerner, K., Gutjahr, W.J., Hartl, R.F., Strauss, C., Stummer, C.: Pareto Ant Colony Optimization: A metaheuristic approach to multiobjective portfolio selection. Annals of Operations Research 131, 79–99 (2004)zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    Dorigo, M., Stützle, T.: Ant Colony Optimization. MIT Press, Cambridge (2004)zbMATHCrossRefGoogle Scholar
  6. 6.
    Ehrgott, M., Gandibleux, X.: A Survey and Annotated Bibliography of Multiobjective Combinatorial Optimization. OR Spektrum 22, 425–460 (2000)zbMATHMathSciNetGoogle Scholar
  7. 7.
    Fu, M.C.: Optimization for simulation: theory vs. practice. INFORMS J. on Computing 14, 192–215 (2002)CrossRefGoogle Scholar
  8. 8.
    Gandibleu, X., Sevaux, M., Sörensen, K., T’kindt, V. (eds.): Metaheuristics for Multiobjective Optimization. Springer, Heidelberg (2004)Google Scholar
  9. 9.
    Gutjahr, W.J.: A converging ACO algorithm for stochastic combinatorial optimization. In: Albrecht, A.A., Steinhöfel, K. (eds.) SAGA 2003. LNCS, vol. 2827, pp. 10–25. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  10. 10.
    Gutjahr, W.J.: S-ACO: An ant-based approach to combinatorial optimization under uncertainty. In: Dorigo, M., Birattari, M., Blum, C., Gambardella, L.M., Mondada, F., Stützle, T. (eds.) ANTS 2004. LNCS, vol. 3172, pp. 238–249. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  11. 11.
    Hughes, E.J.: Evolutionary Multi-objective Ranking with Uncertainty and Noise. In: Zitzler, E., Deb, K., Thiele, L., Coello Coello, C.A., Corne, D.W. (eds.) EMO 2001. LNCS, vol. 1993, pp. 329–343. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  12. 12.
    Jaszkiewicz, A.: Evaluation of multiple objective metaheuristics. In: Gandibleu, X., Sevaux, M., Sörensen, K., T’kindt, V. (eds.) Metaheuristics for Multiobjective Optimization, pp. 65–89. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  13. 13.
    Ulugu, E.L., Teghem, J., Fortemps, P., Tuyttens, D.: MOSA method: a tool for solving multiobjective combinatorial optimization problems. J. of Multi-Criteria Decision Analysis 8, 221–236 (1999)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Walter J. Gutjahr
    • 1
  1. 1.Dept. of Statistics and Decision Support SystemsUniversity of Vienna 

Personalised recommendations